Description

• 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.
• The implementations of algorithms has to be done using C, C++, Python or Java.
Problem 4.1 Merge Sort (12 points)
(a) (4 points) 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 subsequences.
(b) (3 points) 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.
(c) (3 points) 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 Course: CH-231-A
(d) (2 points) Based on the results from (b) and (c), how would you choose k in practice? Briefly explain.
Problem 4.2 Recurrences (10 points)
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.
(a) (2 points) T(n) = 36T(n/6) + 2n,
(b) (2 points) T(n) = 5T(n/3) + 17n1.2,
(c) (2 points) T(n) = 12T(n/2) + n2 lgn,
(d) (2 points) T(n) = 3T(n/5) + T(n/2) + 2n,
(e) (2 points) T(n) = T(2n/5) + T(3n/5) + Θ(n).
How to submit your solutions