1. Given T(n) = 16T(n/4) + n2 .
(a) Use master theorem to find out its asymptotic bounds.
(b) Use substitution method to prove its asymptotic bounds.
2. Given T(n) = T(3n/19)+5n. Use master theorem to find out its asymptotic bounds.
3. Assuming you have a task to sort the telephone numbers of a major carrier. What sorting algorithm will you use? Please justify your answers.
4. You are asked to modify the textbook version of Merge-Sort on page 31 into a new algorithm of Merge-Triplet-Sort. In Merge-Triplet-Sort, an input array A into three new arrays L, M, and R that stands for left, middle, and right. Assume the input array A always has a size of n = 3k, and you can divide A into three equal-sized new arrays.
(a) Please revise the textbook pseudo codes of Merge-Sort() and Merge() functions for your Merge-Triplet-Sort algorithm.
(b) Please find the asymptotic bounds for running time of Merge-Triplet Sort. You must show your procedure.
5. Please modify the pseudo code of Count-Sort algorithm on page 195 in the textbook such that an input array of numbers in the rage of [-n, n] can be sorted.
6. Modify Bucket-Sort pseudo code on page 201 in the textbook such that it can sort floating number in the rage of [-50, 50).
Textbook - Introduction to Algorithms, Third Edition by THOMAS H. CORMEN, CHARLES E. LEISERSON, RONALD L. RIVEST and CLIFFORD STEIN.