Homework Assignments

1. Due 10/1
   • 1.3-3, p. 15
   • 1-1, p. 17
   • 2.1-4, p. 31
   • 2-2, p. 38
   
   
2. Due 10/8
   • 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/15
   • 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/22
   • 5.1-4, p. 81
   • 5.2-3, p. 83
   • 5.4-4, p. 90
   • 7.4-2, p. 149
   
   
5. Due 11/5
   • 7.5-4, p. 151
   • 8.2-1, p. 160
   • 8.3-2, p. 163
   • 8-3, p. 169
   
   
6. Due 11/12
   • 16.1-1, p. 308
   • 16.2-3, p. 314
   • 16.3-1, p. 319
   • 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.
   • Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time during which 1 US dollar buys 0.75 British pounds, 1 British pound buys 2 Australian dollars, and 1 Australian dollar buys 0.70 US dollars. Then, a smart trader can trade one US dollar and end up with 0.75*2*0.7 = 1.05 US dollars, a profit of 5%. Suppose there are n currencies c_1,..,c_n and an nXn table R of exchange rates, such that one unit of currency c_i buys R[i,j] units of currency c_j. Devise and analyze a dynamic programming algorithm to determine the maximum value of R[c1,ci1]*R[ci1,ci2]*...*R[ci(k-1),cik]*R[cik,c1].
   
   
7. Due 11/19
   • 17.1-3, p. 333
   • 17.3-2, p. 344
   • 23.1-3, p. 468
   • 23.2-3, p. 476
   • 23.3-6, p. 484
   
   
8. Due 11/26
   • 23.4-1, p. 487
   • 23.4-3, p. 488
   • 24.2-4, p. 510
   • 24.2-5, p. 510
   • 25.2-2, p. 531