Introduction: Objective of this homework is to further enhance the understanding of the SELECT, min-max finding algorithm, and the application of SELECT algorithm in the Quick-Sort
Also, this an individual submission and no-collaboration expected.
- [Optimal Max and Min Finding – 15 Pts] In the max and min finding algorithms that we have discussed, we need n-1 comparisons. According to our textbook, however, at most 3*n/2 comparisons suffice to find both the minimum and maximum (page 214 -215):
Basic Strategy: Maintain the minimum and maximum of elements seen so far. Don’t compare each element to the minimum and maximum separately. Process elements in pairs. Compare the elements of a pair to each other. Then compare the larger element to the maximum so far, and compare the smaller element to the minimum so far. This leads to only 3 comparisons for every 2 elements.
Setting up the initial values for the min and max depends on whether n is odd or even.
If n is even, compare the first two elements and assign the larger to max and the smaller to min. Then process the rest of the elements in pairs. If n is odd, set both min and max to the first element. Then process the rest of the elements in pairs.
- Write the above description in algorithmic form. Follow the notations that we have discussed in the class (see minimum finding algorithm presented in page 214)
- Show that your algorithm need at most 3*n/2
- [Random Pivot Selection – 30 Pts] In the algorithm SELECT that we have discussed in chapter 9, input elements are divided into groups of 5.
- a) Will the algorithm works if they are divided into groups of 7? Using the substitution method prove your claim by arriving at the running time similar to the recurrence we got for group size 5 during the lecture
b)Show that SELECT does not run in linear time if groups of 3 are used using the substitution method
(Note: Substitution method is discussed in week 3 Lecture 2)
- [Random Pivot and Quick Sort -15 Pts] Show that quick sort can be made to run O(n log
n)time in the worst-case. Assume that all elements are distinct.
- Write your algorithm that run quick sort can be made to run O(n log n)time
- Write the recurrence that shows the running time of your algorithm in (a) above
- Briefly explain (no need to prove) how your recurrence records O(n log n)time in worst-case
