CS 332 - Theory of Computation
Fall 2001
An index page for various class resources
last modified 10/03/2002
Final Grades are now available; contact
Professor Levine
Syllabus
Announcements
You must attend one of the Friday talks and write a
reaction paper as discussed in class. Anne Foerst will be talking Thursday
night in Murphy auditorium at 7:00 p.m. Although not specifically a CS
talk, it may serve to complete this requirement. Also, Ed Hayes will be
presenting another talk in the
"internship series" Friday at 2:30 in DLR 4.
Assignments
- Program 1 - Almost a Nine! due 8/29/2001
- p. 25-26: 0.1-0.5, due 8/31/2001
- p. 26-27: 0.6-0.9, due 9/5/2001
- Program 2 - Nine Point Five?, due 9/5/2001
- p. 27: 0.10, due 9/7/2001
- p. 27: 0.11, due 9/10/2001
- Consider the "nine" machine from Program 2. Describe the "words" that may have been processed if you are in State 0. ALSO due 9/10/2001
- p. 83-4: 1.1-1.3, 1.4abcd, due 9/14/01
- p. 84: 1.4e-n, due 9/17/01
- p. 84: 1.5, due 9/19/01
- p. 85: 1.12, due 9/21/01
- Program 3 - A DFA Simulator, due 9/28/01; portion due 9/21/01 at 8 a.m.!
- p. 84: 1.6, due 9/24/01
- File format for machine M2, p. 83, due 9/24/01, at 8 a.m.!
- p. 84-86: 1.7-1.9 due 9/26/01
- p. 86: 1.13a-g, 1.15, due 9/28/01
- p. 86: 1.13h-n, 1.14, due 10/3/01; since this assignment was not announced in class, it is due on Wednesday of next week. However, a 10% bonus will be given for those who turn it in on Monday
- p. 86: 1.16, due 10/3/01
- p. 86: 1.17, 1.18, due 10/10/01
- p. 88: 1.23ab, due 10/12/01
- p. 119-120: 2.1, 2.3, 2.4ab, due 10/15/01
- p. 120: 2.4c-g, due 10/17/01
- put the grammar of problem 2.3 into Chomsky Normal form; also, pp. 120-121: 2.8, due 10/22/01
- p. 120-121: 2.5, 2.9, due 10/24/01
- p. 121: 2.11, 2.12, due 10/29/01
- show how to convert a DFA (directly) into a CFG, due 11/2/01
- send a trivial message from the Suns to dlevine@cs.sbu.edu indicating that you have logged on successfully, due 11/7/01
- Program 4 - A Simple Lexer (or two), due 11/26/01
- p. 147: 3.1, 3.2, due 11/14/01
- p. 148: 3.5, 3.8a, due 11/16/01
- p. 148: 3,7, 3.8bc, TM with infinite loop, due 11/26/01
- Program 5 - A Turing Machine Simulator, due 12/7/01; portion due 11/30/01 at 8 a.m.!
- p. 148-149: 3.9, 3.19, due 11/30/01
- p. 168-169: 4.1, due 12/3/01
- p. 169: 4.2-4.4, due 12/05/01
- p. 169: 4.5, 4.6, 4.10, due 12/07/01
-
Readings
- Sipser, Chapter 0; 8/27
- Sipser, Chapter 1; 9/10
- Sipser, Chapter 2; 10/10
- Sipser, Chapter 3; 11/12
- Sipser, Chapter 4; 11/28
-
Fun links