Homework Assignments
- Due 10/1
- 1.3-3, p. 15
- 1-1, p. 17
- 2.1-4, p. 31
- 2-2, p. 38
- 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
- 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
- Due 10/22
- 5.1-4, p. 81
- 5.2-3, p. 83
- 5.4-4, p. 90
- 7.4-2, p. 149
- Due 11/5
- 7.5-4, p. 151
- 8.2-1, p. 160
- 8.3-2, p. 163
- 8-3, p. 169
- 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].
- 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
- 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