CS237 (Theory of Computation)
Spring 2007, Carleton College


[Jump to current week]

Basic information:

Announcements:

Course Materials:

Week 0:
There is a form for office-hours scheduling available. Please fill it out by Tuesday, 20 March 2007, and I'll schedule office hours soon thereafter. (Be sure to include your email address!)
Week 1: course overview; DFAs
Week 2: NFAs, closure properties of the regular languages, regular expressions
Problem Set #1 is due on Monday and Wednesday.
Week 3: non-regular languages
Problem Set #2 is due on Monday and Wednesday.
Week 4: regular language miscellanea
Problem Set #3 is due on Monday and Wednesday.
Our first midterm is scheduled for Monday, 23 April 2007, in class. You may bring one 8.5"-by-11" crib sheet containing notes that you have handwritten or typed yourself (no photocopying). You may write on both sides of the paper, but don't staple/tape/superglue/attach anything to the paper. You will be asked to hand in your crib sheet with your exam. Any material related to regular languages is fair game for the exam.
Week 5: context-free languages
Problem Set #4 is due on Wednesday.
Week 6: non-context-free languages, PDAs, closure properties
Problem Set #5 is due on Wednesday.
Week 7: CFL miscellanea, Turing machines
Problem Set #6 is due on Wednesday.
Our second midterm is Friday, 11 May 2007, in class. You may bring one 8.5"-by-11" crib sheet containing notes that you have handwritten or typed yourself (no photocopying). You may write on both sides of the paper, but don't staple/tape/superglue/attach anything to the paper. You will be asked to hand in your crib sheet with your exam. Any material related to context-free or regular languages is fair game for the exam.
Week 8: Turing machines, computability
Problem Set #7 is due on Wednesday and Friday.
Week 9: decidability and undecidability
Problem Set #8 is due on Wednesday and Friday. (Update: skip #5; only 2 questions are due Wednesday.)
Week 10: undecidable problems, Gödel's Incompleteness Theorem
Problem Set #9 is due on Wednesday.
Finals Period:
Resources/clarifications for the final: