# Homework Assignments

1. Due 9/30
• 1.3-3, p. 15
• 1-1, p. 17
• 2.1-4, p. 31
• 2-2, p. 38

2. Due 10/7
• Express (z + z^3 + z^5 + z^7 + ...) with |z|<1, in closed form
• 3.2-4, p. 52
• 3-1 b, p. 52
• Express Sum_{k=0 to n} log ( (n^2)/(2^k) ) in a closed form

3. Due 10/14
• Use iteration to solve T(n)=2T(n/3) + n^2, with T(1)=1
• 4-1 c, p. 72
• 4-4 a, p. 73
• 4-4 c, p.73
• Find a closed form for T(n)= ((log n)/(log (n-1))) T(n-1) + n log n, with T(2)=1

4. Due 10/21
• 7.4-1, p. 149
• 7.4-2, p. 149
• 5.1-4, p. 81
• 5.2-3, p. 83

5. Due 11/4
• 8.1-2, p. 155
• 8.2-1, p. 160
• 8.3-2, p. 163
• 8-3, p. 169

6. Due 11/11
• 16.1-1, p. 308
• Explain why (including finding counter-example) the following algorithm for the matrix chain problem does not work: Suppose n>2 and that p_i is smallest of p_1 .. p_n-1. Break the product after A_i, and recursively apply this procedure to the products A_1..A_i and A_i+1..A_n.
• 16.2-3, p. 314
• 16.3-1, p. 319
• 16-2, p. 325

7. Due 11/18
• 17.1-3, p. 333
• 17.2-5, p. 337
• 17.3-2, p. 344
• 5.4-4, p. 90

8. Due 11/25
• 23.1-3, p. 468
• 23.3-6, p. 484
• 23.4-1, p. 487
• 24.2-4, p. 510
• 24.2-5, p. 510