Problem 12. (Difficulty 2) Bubblesort and oblivious merge-sort each give a sequence of compare-exchange operations which sorts any array A[0..3]. Write down both sequences.
Problem 13. (Difficulty 4) For n distinct elements x1, x2, . . . , xn with positive weights w1, w2, . . . , wn such that ni=1 wi = 1, define the weighted median to be an index k sat- isfying i:xi
Problem 14. (Difficulty 3) Suppose we are given k sorted lists, each consisting of n elements. The multimerge problem is to merge the k lists into a single sorted list of length nk. Design an efficient algorithm for the multimerge problem. Analyze the running time of your algorithm. The more efficient your algorithm is in terms of its worst-case running time, the more credit you will get.
2 Homework 1
Problem 15. (Difficulty 3) Return a list of the following functions separated by the symbol ≡or≪,wheref ≡gmeansf =Θ(g)andf ≪gmeansf =O(g). Youdonotneed to justify your answer. For example, if the functions are log n, n, 5n, 2n a correct answer is log n ≪ n ≡ 5n ≪ 2n. All logarithms are in base 2. One point for each correct symbol.
11. nlog 5 12. 25n
13. 5n 14. 2log n
15. 5n
16. 5 log(n)
17. 25 log log n 18. 5log n
19. 25 log n
20. n55
Problem 16. (Difficulty 3) Solve the following recurrences. Give both O(.) and Ω(.).
T(n) = 4T(n/3) + n, T(n) = 3T(n/4) + n, T(n) = 3T(n/4) + n2.
5
1. 1/5
2. log(n)+5
3. (logn!)5
4. log(n5)
5. n1/5
6. (logn)5
7. n 8. 2n5
9. 1 10. n5
Problem 17. (Difficulty 2) Execute the Quick-Sort algorithm on the following array [5,2,6,1,3,4,7]
using the last element of the array as a pivot element. Show the contents of the array after each pass of partition.
Problem 18. (Difficulty 3) Give an algorithm running in time O(n) and space O(1) which sorts an array of n elements in the range {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. Note that you cannot use another array of length n for the output because you are only allowed space O(1).
Problem 19. (Difficulty 3) You are given as input an array A[1..n] containing integer numbers from 1 to n10. Give an O(n)-time algorithm to determine if there are two numbers which sum to 0.
6