Submit one ZIP file per homework sheet which contains one PDF file (including pictures,computations, formulas, explanations, etc.) and your source code file(s) with one makefile and without adding executable, object or temporary files.
Problem 4.1 Merge Sort
Implement a variant of Merge Sort that does not divide the problem all the waydown to subproblems of size 1. Instead, when reaching subsequences of length k it applies Insertion Sort on these n/k
Apply it to the different sequences which satisfy best case, worst case and averagecase for different values of k. Plot the execution times for different values of k.
How do the different values of k change the best-, average-, and worst-case asymptotic time complexities for this variant? Explain/prove your answer.
Algorithms and Data Structures
(2 points) Based on the results from (b) and (c), how would you choose k in practice? Briefly explain.
Problem 4.2 Recurrences
Use the substitution method, the recursion tree, or the master theorem method to derive upper and lower bounds for T(n) in each of the following recurrences. Make the bounds as tight as possible. Assume that T(n) is constant for n≤ 2.
(2 points) T(n) = 36T(n/6) + 2n,
(2 points) T(n) = 5T(n/3) + 17n1.2,
(2 points) T(n) = 12T(n/2) + n2 lgn,
(2 points) T(n) = 3T(n/5) + T(n/2) + 2n,
(2 points) T(n) = T(2n/5) + T(3n/5) + Θ(n).
