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

Introduction

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

See also the general rules about assignments in this course.

DUE: 2016-09-29, 16:30 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.

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

3 Consider merging k sorted arrays, each of size n