• Read chapter 1 by Thursday Jan 25.
• Written solutions to problems 1.2.3, 1.2.4, 1.4.2, and 1.5.2 are due at the beginning of class Tuesday Jan 30.

• Written solutions to problem 2.1.3 and three of the following six problems: 1.7.2, 1.8.3, 2.1.2, 2.1.7, 2.2.2, 2.2.6 (a and b), are due at the beginning of class Tuesday Feb 6.

• Written solutions to problem 2.4.4 and three of the following problems: 2.4.1, 2.4.2, 2.4.3a-c, 2.4.3d-f, 2.4.5, 2.4.6, 2.4.12, and 2.5.1a)i-iii+b)i-iii are due at the beginning of class Thursday Feb 15.

• Written solutions to problem 3.1.3, 3.3.2a,b and two of the following problems: 3.1.4 (Pi!), 3.1.5, 3.1.9abc, 3.1.10, and 3.2.2 are due at the beginning of class Tuesday Feb 20.

• Written solutions to problem 3.5.2bc, and three of the following problems: 2.3.3, 3.5.1, 3.5.8 (you do not need to solve 3.5.7, just use the result), 3.5.10, and 3.5.15 are due at the beginning of class Tuesday Feb 27.

• Written solutions to problems 4.1.1, 4.1.4 (check both odd and even n) and two of the following are due by Saturday 10 March 2007: 4.1.6, 4.1.7, 4.1.10, and example 4.1.9. For example 4.1.9, so that the example in the textbook is incorrect, and that the machine does not perform a right shift as indicated. Then fix the machine. For 4.1.6, the problem lists configurations as ordered 4-tuples, while the book says valid configurations are either ordered 3-tuples, or ordered pairs. For the purposes of this problem consider the ordered 4-tuple to have the following interpretation: The tuple (q,w,a,u) means the machine is in state q, w is to the left of the read/write head, a is at the read/write head, and u is to the right of the read/write head. Under this interpretation, finish the problem.

• Written solutions to problem 4.2.2, and three of the following problems: 4.2.1, 4.2.3, 4.3.1a, 4.3.4, 4.3.5, 4.3.6, and 4.4.3 are due at the beginning of class Tuesday April 3.

• Written solutions four of the following problems: 4.5.1b, 4.5.3, 4.6.2b, 4.6.2c, 4.7.2abc are due at the beginning of class Tuesday April 10.

• Written solutions to 5.2.1, 5.3.1, 5.4.1, and 5.4.2abde are due at the beginning of class Thursday April 19.

• Written solutions to four of 2.6.2, 5.7.8, 6.1.1, 6.1.2, and 6.4.2 are due at the beginning of class Thursday April 26.

• Written solutions to 6.3.3, 6.4.4, 7.1.1, and 7.2.2ab are due by 5pm Friday 4 May.

Home Page

Last updated: Tuesday, September 22, 2020 at 01:07:44 PM