Introduction

This assignment covers material related to divide and conquer algorithms, mainly recursion

See also the general rules about assignments in this course.

DUE: 2018-01-24, 09:15 in the assignment box.

Questions

1 For each of the following recursion relations, if it can be solved by the master theorem, solve it, otherwise explain why the master theorem can not be used.

• T(n) = 2T(n/3) + 1
• T(n) = 1.5T(n/3) + sqrt(n)
• T(n) = T(log(n)) + 1
• T(n) = 8T(n/2) + n³ +101n² - 3n

2 Solve the recurrence T(n)=T(sqrt(n))+1.

3 Consider merging k sorted arrays, each of size n

• Give an efficient divide and conquer algorithm for this problem.
• Give a recurrence relation for the worst case running time of your algorithm.
• Solve the recurrence.
• k should be considered a constant in your analysis