CMSC351 (Kruskal) Homework 6 Due: Friday, March 29, 2019
1. Use the integral method to get upper and lower bounds for n j=0
have exactly the same high order term. Show your work.
√j. The two values should
2. Consider an array of size nine with the numbers 30, 10, 80, 40, 20, 90, 70, 60, 50. Assume you execute quicksort using the version of partition from CLRS. Note that in this algorithm an element might exchange with itself (which counts as one exchange).
(a) Show the array after the first partition. How many comparisons and exchanges are used? (b) How many comparisons and exchanges are used for the entire quicksort?
3. The standard partition algorithm in Quicksort has one pivot and two groups of elements (the small elements and the large elements). We are going to investigate Quicksort when the par- tition algorithm has more than one pivot. In general, if there are k − 1 pivots there will be k groups of elements. We will estimate the average number of moves as a function of n and k.
We do not care about the programming details here. You will worry about that in the pro- gramming assignment.
When you do partition, the k − 1 pivot elements will be sorted using Insertion Sort. For simplicity, assume that this takes exactly k2/4 moves on average. As you process the elements, there will be k groups. Each of the n − k + 1 non-pivot elements is processed to determine which group it belongs in. For simplicity assume that this takes exactly k/2 moves on average for each element. Finally, assume that it takes k2/4 moves to insert all k − 1 pivots.
The recursion ends when the list has size less than k. At that point, the list is sorted using Insertion Sort. For simplicity, again assume that this takes exactly n2/4 moves on average, where n ≤ k is the size of the list.
The average case number of moves seems hard to solve analytically. In the programming project, we will estimate it experimentally. Here we find a lower bound for the true average case.
(a) Write a recurrence for the average number of moves, under the simplifying assumption that each group has exactly the same size. Fix k (and let n be asymptotically large).
(b) Solve the recurrence using constructive induction. Get the exact high order term (as a function of k and n). For simplicity, drop any terms that are linear in k when solving the recurrence.
(c) What is the optimal value of k?
(d) What is the exact asymptotic number of moves for this value of k?