Math 29, Spring 2009: Homework Assignments
Assignment 1, due Monday, April 6: 3.1.1 and 3.1.2 (p. 33), 2.4.9 (p. 25), 3.2.3 (p. 35).
Assignment 2, due Monday, April 13: 4.1.2, 4.1.3, and 4.1.4 (p. 47), 4.1.5 (p. 48).
Assignment 3, due Monday, April 20: 4.3.1 and 4.4.2 (p. 51), 4.5.5, 4.5.6, and 4.5.8 (p. 53).
Assignment 4, due Monday, April 27: 4.6.5, 4.6.6, and 4.6.7 (p. 57), 4.6.9 (p. 58)
Assignment 5, due Monday, May 4 (pdf)
Assignment 6, due Monday, May 11: 5.1.8 (p. 65), 5.1.9, 5.1.10, 5.1.11, and 5.1.14 (p. 66).
Note the reference to the next section in 5.1.14 is really a reference to dovetailing, as that's the first place it appears formally in the notes.
Assignment 7, due Monday, May 18: 2.3.6 and 2.3.9 (p. 18), 2.3.13 (p. 19), 7.1.1 (p. 79), and the following:
∗ Given e, write an oracle algorithm φX that is total when X = We and partial otherwise.
Recall that by the bijectivity and computability of the pairing function, any natural number may be thought of as <n, s>. It is not necessary but may be easier to define φX on inputs of that form (i.e., define φX(<n, s>)).
Assignment 8, due Wednesday, May 27: 7.1.3 (p. 79), 7.1.5 and 7.2.2 (p. 80), 8.3.4 and 8.3.6 (p. 90), and ∗ Prove that =* is an equivalence relation.
Assignment 9, due Monday, June 1: last assignment; extra credit only. Give me suggestions for improving the course (organization and format, topic selection, more or less coverage of certain topics, etc) or advertising it effectively next time it is scheduled. Each thoughtful suggestion gets a point (regardless of whether I think it's a good idea!) up to a maximum of 5.
Last modified May 28, 2009