CS254 (Automata and Computability)
Spring 2008, Carleton College


[Jump to current week]

Basic information:

Course Materials:

Week 0:
There is an anonymous feedback form available for any comments that you have about the course. If you have any suggestions or comments on the class (style, content, workload, etc.), please feel free to use this form to let me know.
The CS department has an email newsletter, the Carleton Sentinel, that we use for occasional updates on things that might be of interest. Sign up here!
There is a form for office-hours scheduling available. Please fill it out by the Thursday before the first day of classes and I'll schedule office hours soon thereafter. (Be sure to include your email address!)
Week 1: course overview; DFAs.
PS0 is due on Wednesday.
One question from PS1 is due on Friday.
Week 2: NFAs, closure properties of the regular languages, regular expressions.
Two questions from PS1 are due on Monday.
Two questions from PS1 are due on Wednesday.
Two questions from PS2 are due on Friday.
Week 3: non-regular languages.
Two questions from PS2 are due on Monday.
Two questions from PS2 are due on Wednesday.
Two questions from PS3 are due on Friday.
Week 4: context-free languages.
Two questions from PS3 are due on Monday.
Two questions from PS4 are due on Wednesday.
One or two questions from PS4 are due on Friday. In total, you must complete both #1 and #2, plus one of #3 and #4. If you do the other of #3 and #4 (completely optional ...), you can replace your lowest homework grade to date with your score on that optional problem.
Our first midterm is scheduled for Monday, 28 April 2008, 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 history and regular languages (so up to and including class on 21 April 2008, Problem Set 4, and Lectures 1–18 in Kozen) is fair game for the exam.
Week 5: PDAs, closure properties.
My office hours on Wednesday, 30 April, are rescheduled. They will be held 3:30–5:00p.
Two questions from PS5 are due on Wednesday.
Two questions from PS5 are due on Friday.
Week 6: non-context-free languages, Turing machines.
Two questions from PS6 are due on Friday.
Week 7: Turing machines and computability.
Instead of my usual office hours on Tuesday, 13 May 2008, I'll have office hours from 3:00p to 4:00p on Monday, 12 May 2008, and from 9:45a to 10:45a on Teusday, 13 May 2008.
Two questions from PS6 are due on Monday.
One question from PS7 is due on Wednesday.
Two questions from PS7 are due on Friday.
Week 8: decidability and undecidability.
Two questions from PS7 are due on Monday.
Two questions from PS8 are due on Wednesday.
Two questions from PS8 are due on Friday. Also the optional Question #5 is optionally due as optional extra credit on Friday.
Our second midterm is scheduled for Monday, 26 May 2008, 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 up to and including class on 23 May 2008, Problem Set 8, and Lectures 1–34 in Kozen is fair game for the exam.
Week 9: midterm #2 and Ron Rivest.
Week 10: undecidable problems and Gödel's Incompleteness Theorem
Two questions from PS9 are due on Monday.
Two questions from PS9 are due on Wednesday.
Finals Period:
Our finals slot is scheduled for Saturday, 7 June 2008, 3:30–6:00p.
The final will be a take-home exam distributed on the last day of class and due on the last day of the finals period.