Homework 4

Written assignment (assigned October 17, due November 5)

This homework covers the material in chapter 8 of the textbook.

Please note: your solutions should be readable, and justifications should be given for steps in the proofs. Elegance counts!

1. Do exercise 8.2-2 on page 160. (10 points)

2. Do exercise 8.2-3 on page 160. (10 points)

3. Do exercise 8.4-1 on page 167. (10 points)

4. Do problem 8-3, parts b and c, on page 169. (Each part is worth 5 points.)

5. Consider the following recurrences:
   
   • T(n) = T(n/20) + T(n/5) + T(n/2) + cn for n > 20;
     T(n) =< 20 for n =< 20.
     Prove that T(n) is Theta(n). You may assume that n is a multiple of 20. (5 points)

   • T(n) = T(a₁n) + T(a₂n) + ... + T(a_kn) + cn for n > 1;
     T(n) = 1 for n = 1,
     where a₁ + a₂ + ... + a_k = B < 1 and all the a_i's > 0.
     Prove that T(n) is Theta(n). (5 points)

Challenge Problems (optional)

• Do problem 8.4-4 on page 167. (10 points)
• Do problem 8-2 on pages 168-169. (10 points)

Gerry Brady
Thu Oct 18 08:02:10 CDT 2001