CS 332 - Theory of Computation

Fall 2009

An index page for various class resources

last modified 11/19/2009

Syllabus

Announcements

• The midterm examination is a one-week take-home exam.  It will be given out in class on Tuesday, November 10 and due back in class on Tuesday, November 17.

Assignments

• p. 182-3, 4.1, 4.3, 4.4, 4.12, due Tuesday, November 24
• Program #4 - Turing Machine, due Thursday, December 3, - portion due Friday November 20.  [This also covers homework that would have been due on November 19.]
• <no homework due Tuesday, November 17; BUT if you wish, you may turn in the Nov. 12 work that day provided that you email me before class on the 12 and tell me that that is your intention>
• p. 160-162, 3.6, 3.15e, 3.22, due Thursday, November 12
• p. 159-160, 3.1, 3.2, 3.8b, due Tuesday, November 10
• p. 128, 131, 2.2, 2.30ab, due Thursday, November 5
• p. 130, 2.18, 2.27a, due Tuesday, November 3
• p. 129, 2.11, 2.12, 1.14, due Thursday, October 29
• p. 128-9, put grammar of 2.3 into Chomsky Normal Form, 2.5 bce, 2.10, due Tuesday, October 27
• p. 128-129 2.4d-f, 2.8, 2.9, due Thursday, October 22.  PLUS, interpreted by the book's definition of PDA, what is the actual language accepted by the machine drawn on the blackboard claiming to be for 0ⁿ1ⁿ?
• p. 128, 2.1, 2.3, 2.4abc, due Tuesday, October 20.
• p.  87, 91, 1.24, 1.53, due Thursday, October 15.  (Note: 1.53 can be easy if you think about it properly!)
• Program #3, - DFA, due Tuesday, October 20 - portion due Thursday, October 8
• p. 86, 88, 1.20, 1.28, 1,29a, due Thursday, October 8
• p. 86, 1.16b, 1.17a, 1.19b, 1.21a, due Tuesday, October 6
• p. 84-85, 1.7, 1.12, due Thursday, October 1 - plus
  • Explain what happens if you apply the minimization algorithm to a DFA and then take the machine that results and apply it again.
• p. 84, 1.5 efgh, 1.6hijklmn, due Tuesday, September 29 plus
  • Give a regular expression for a word in which all (six) vowels appear in alphabetical order - as described in class
• p. 84, 1.5abcd, 1.6abcdefg, due Tuesday, September 22
• p. 83, 1.1-1.3,1.4abcd, due Thursday, September 17
• p. 27, either 0.10 or 0.11 (or both if you want) AND 0.12, due Tuesday, September 15
• p. 26, 0.6-0.9, due Thursday, September 10
• Program #2 - A Nine-point-five?, due Thursday, September 10
• p. 25-26, 0.1-0.5, due Tuesday, September 8
•  Program #1 - Almost a Ten!, due Thursday, September 3

Readings

• Sipser, Chapter 4, 11/12
• Sipser, Chapter 3, 11/3
• Sipser, Chapter 2, 10/7
• Sipser, Chapter 1, remainder; 9/22
• Sipser, Chapter 1, Sections 1 and 2; 9/10
• Sipser, Chapter 0; 9/1