CS254 (Automata and Computability)
Spring 2008, Carleton College
Basic information:
- Instructor: David
Liben-Nowell
- Lecture: 2a (MW 9:50--11:00a, F 9:40--10:40a), CMC 319.
- Office Hours: see my homepage.
Always feel free to email for an appointment if the scheduled times
aren't good for you.
- Official catalogue description:
An introduction to the theory of computation, emphasizing an
understanding of what problems can and cannot be solved by
computers. Topics include formal models of computation, including
finite-state automata, pushdown automata, and Turing machines; formal
languages, including regular expressions and context-free grammars;
and computability and uncomputability. Time permitting, we will
discuss computational and mathematical applications, like parsing and
Godel's incompleteness theorem. Prerequisites: Computer Science 111;
and either CS 202 or Mathematics 236.
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.
- 31 March 2008 (M): history of computing (600 BCE ff.), strings,
languages.
Reading: L01, L02
- 2 April 2008 (W): intro to DFAs
Reading: L02, L03
- 4 April 2008 (F): product construction; closure properties of
the regular languages.
Reading: L03, L04
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.
- 7 April 2008 (M): nondeterminisism and NFAs
Reading: L05, L06
- 9 April 2008 (W): subset construction; closure properties
Reading: L05, L06
- 11 April 2008 (F): patterns and regular expressions
Reading: L07, L08
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.
- 14 April 2008 (M): equivalence of regular expresions and DFAs.
Reading: L08, L09
- 16 April 2008 (W): nonregular languages and the pumping lemma.
Reading: L11, L12
- 18 April 2008 (F): pumping lemma; state miniminization
Reading: L13, L14
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.
- 5 May 2008 (M): midterm break!
- 7 May 2008 (W): NPDAs, CFGs and NPDAs, and the pumping lemma for
context-free languages.
Reading: L22, L26, L27
- 9 May 2008 (F): CFL wrapup; intro to Turing machines.
Reading: L28, L29
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.
- 12 May 2008 (M): more on Turing machines.
Reading: L29, L30
- 14 May 2008 (W): other Turing-machine-like models.
Reading: L30
- 16 May 2008 (F): more on enumeration machines; encoding TMs via
binary strings; decidability and undecidability.
Reading: L31, L32
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.
- 19 May 2008 (M): universal Turing machines and the halting problem.
Reading: L31, L32
- 21 May 2008 (W): reductions.
Reading: L32, L33
- 23 May 2008 (F): reductions and Rice's Theorem.
Reading: L34
Week 9: midterm #2 and Ron Rivest.
- 26 May 2008 (M): midterm #2
- 28 May 2008 (W): Ron Rivest: public-key cryptography and
zero-knowledge proofs.
- 30 May 2008 (F): class cancelled! Go to
Ron Rivest's talks instead.
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.
- 2 June 2008 (M): VALCOMPs and undecidable problems about CFLs.
Reading: L35
- 4 June 2008 (W): Gödel's incompleteness theorem and course wrapup.
Reading: L38, L39, LK.
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.