MA314 Algorithms and Programming LT 2018
Homework 3
Instructions: For questions that are marked with (?) you do not need to hand in anything.
For all other questions, please hand in your solutions on paper (you can combine print outs
with handwritten notes) by Monday Jan 29, 2018 at 4pm. Either by dropping them into
the pigeon hole of your seminar teacher, located on the ground oor of Columbia House, or by
handing them to your lecturer at the beginning of the lecture. Please write your name, student
ID, and which group you are in on top of the rst page. In addition, please send all programs
that you wrote as a zip le named \yourlastname-hw2.zip" to . The
subject of your email should be \HW 3 - Grp X - yourlastname", where X is the number of the
group you are in.
Exercise 3.1: InsertionSort, recursively
We can express the sorting algorithm InsertionSort as a recursive procedure as follows. In order
to sort A = [A[0];:::;A[n 1]] we recursively sort [A[0];:::;A[n 2]] and then insert A[n 1]
into the sorted array [A[0];:::;A[n 2]] by going through the sorted array from right to left and
inserting A[n 1] after the rst element that is smaller or equal to it.
(a) Complete the following implementation of this recursive version of InsertionSort by adding
the respective functionality at the indicated place. Your implementation of the algorithm need
not be \in place."
Hint: To insert the current element in the result of the recursive call you may nd it helpful
to rst append an entry None to the list or use the function insert(index, obj). For example, to
append None to C = [1;5;6] use D.append(None) and to add current after the rst element use
D.insert(1,current).
(b) The worst-case running time for inserting an element A[n 1] in an already sorted list
of size n 1 is (n). Hence the running time of the recursive version of InsertionSort can be
understood through the following recurrence relation:
T(1) = a;and
T(n) = T(n 1) + a n for n 2;
where a > 0 is some positive constant. Use mathematical induction to show that the solution
to this recurrence relation is
T(n) = 12 n2 a + 12 n a:
(c) Show that T(n) = (n2):
1
Exercise 3.2: MergeSort
In the lecture we showed that there exists constants a > 0;b such that for the worst-case running
time T(n) for MergeSort on lists of length n we have
T(n) a n ld(n) + (2n 1) b:
Show that
T(n) a n ld(n) + (2n 1) b = O(n ld(n)):
Hint: Consider c = 3 a, and use that for b > 0 we have (2n 1)b 0 is a positive constant. Use mathematical induction or a recursion tree to show that
the solution to this recurrence is:
T(n) = (log3(n) + 1) a n:
Hint: Use that 1 = log3(3) and log3(n) + log3(3) = log(3n).
(d) Show that T(n) = (n ld(n)).
Hint: Recall the formula for converting logs in di erent bases according to which logb(x) =
logd(x)=logd(b).