There are total 4 questions. Please answer all question correctly by using write

Question

There are total 4 questions. Please answer all question correctly by using write pattern.

Suppose quick sort always partition the array in 60% and 40% sub partitions. Find the complexity using a recurrence tree. Consider the Hire Assistant problem. We interview n candidates and always hire the best qualified so far. Let n = 15 for our example. Find the probabilities that we hire exactly 1 time, 2 times, 3 times, 4 times and 5 times. Define the probabilities as Pr(h=i), where i= 1... 15 A machine is reading repeated temperature values from different sensors. Every time the machine read the temperature, it sort them and then returns the median temperature in the sorted values. Which sorting algorithm would you use to sort the readings and explain why would you use that algorithm (explain in just two lines maximum). Write a high level description of your efficient algorithm, if you are asked to sort an array containing 1 million items between 0-130. Write the memory usage and time complexity of your algorithm.

Explanation / Answer

1) Answer:

  Best Case Quicksort: In the best case, everything will be exactly halved at each stage, giving a recurrence of:

  T(n) = 2 T(n/2) + (n)

Worst Case Quicksort: In the worst case, each partition has just the pivot, with everything else on one side of the other. This worst case is encountered using the book's (non-randomized) algorithm working on an array that is already sorted. Here the recurrence will be:

  T(n) = T(n - 1) + T(0)+ (n), and
  T(0) = (1)

3) Answer:   

4) Answer :

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---