MATH 1P67: Mathematics for Computer Science Spring 2016 Assignment 3: Recursions and Complexity Due: Wednesday, June 29, at 19:00 (7:00 pm) 1. Double Tower of Hanoi contains 2n disks of n different sizes, with two disks of each size. You must move all 2n disks from one peg to another, but you may move only one disk at a time, without putting a larger disk over a smaller one. How many moves does it take to transfer a double tower from one peg to another if disks of equal size are indistinguishable from one another? Find a recurrence relation for the number of moves. Then, solve the recurrence relation. 2. Below is pseudocode for a modified merge sort algorithm. This new algorithm partitions the list into four sublists instead of the \u0001 usual two: procedure newmergesort a[1, ..., n] input: output: if n > 1 then\u0010 \u0001 \u0001\u0011 L1 = merge newmergesort a[ 1, ..., bn/4c ] , newmergesort a[ bn/4c + 1, ..., bn/2c ] \u0010 \u0001 \u0001\u0011 L1 = merge newmergesort a[ bn/2c + 1, ..., b3n/4c ] , newmergesort a[ b3n/4c + 1, ..., n ] \u0001 merge L1 , L2 Complete the following two problems to determine if it is possible to improve the complexity of merge sort by partitioning the list into more than two lists of smaller sizes. a) Analyze the worst-case runtime of the new merge sort (you may make reasonable assumptions about the length of the list). b) Compare the complexity of the original merge sort with the complexity of the new merge sort. 3. Solve the following recurrences: a) T (n) = 7T (n 1) 10T (n 2) for n 2, T (0) = 2 and T (1) = 1. b) T (n) = 6T (n 1) 8T (n 2) for n 2, T (0) = 4 and T (1) = 10. c) T (n) = T (n 2) for n 2, T (0) = 5 and T (1) = 1. d) T (n) = 4T (n 1) + 5T (n 2) for n 2, T (0) = 2 and T (1) = 8