Problem 4.1 Merge Sort (12 points)
(a) (4 points) Implement a variant of Merge Sort that does not divide the problem all the way down 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 average case 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.
(d) Bonus (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 lg n,
(d) (2 points) T (n) = 3T (n=5) + T (n=2) + 2n,
(e) Bonus (2 points) T (n) = T (2n=5) + T (3n=5) + (n).
How to submit your solutions
You can submit your solutions via Grader at https://grader.eecs.jacobs-university.de as a generated PDF file and/or source code files.
If there are problems with Grader (but only then), you can submit the file by sending mail to k.lipskoch@jacobs-university.de with a subject line that starts with CH-231-A.
Please note, that after the deadline it will not be possible to submit solutions. It is useless to send solutions by mail, because they will not be graded.
This homework is due by Monday, March 2nd, 23:00.
