Due: Tue Sept 29 11:30 am

To understand Recursion Trees (as a time analysis technique) and to develop skills in the design of recursive divide-and-conquer algorithms.

Task

1. (10 marks) Text Chapter 1 Question 8 part (p).
2. (10 marks) Text Chapter 1 Question 9 part (a).
3. (10 marks) Text Chapter 1 Question 13.
4. (10 marks) Text Chapter 1 Question 21 parts (a) and (b) (think about (c)!).
5. (10 marks) Text Chapter 1 Question 22 part (a). You must provide the Recursion Tree analysis. Indicate the base case of your recursive algorithm, and the height of the recursion tree when it peters out to constants at the leaves. Use this to prove your running-time claim by indicating whethere the tree is "all levels equal" or "decaying exponentially", or "growing exponentially".

Previous Assignment            Next Assignment