UNB/ CS/ David Bremner/ teaching/ cs3383/ assignments/ CS3383 Assignment 2


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.


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.

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

3 Consider merging k sorted arrays, each of size n