CS237 (Theory of Computation)
Spring 2006, Carleton College

[Jump to current week]

Basic information:

Instructor: David Liben-Nowell
Lecture: 4a (MW 12:30p–1:40p, F 1:10p–2:10p), CMC 319.
Office Hours: M 2:00–3:00p, T 2:30p–4:00p, F 12:00–1:00p.
Always feel free to email for an appointment if the scheduled times aren't good for you.
Official catalogue description: All about computing machines: abstract automata, especially finite state machines, push-down automata, and Turing machines. Formal languages, especially context-free languages. The relationship between automata and languages. Computability and solvability. Prerequisites: Computer Science 127; Computer Science 177 or 223 or Mathematics 236 or consent of the instructor.

Announcements:

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 Carleton Sentinel is the mailing list of the CS community here at Carleton. We'll use it to send occasional updates on things that might be of interest. Sign up here!

Overly Ambitious Estimated Rough Tentative Schedule (subject to change):

Week #1: overview, intro to DFAs, induction review (L1-3).
Week #2: DFAs, NFAs (L4-6).
Week #3: regular expressions, non-regular languages (L7-9,11,12).
Week #4: DFA state minimization, CFGs/CFLs. (L13, 19-21).
Week #5: non-CF languages, PDAs (L22-23). Midterm exam!
Week #6: PDAs, parsing (L24-26). Midterm break!
Week #7: CKY algorithm, Turing machines (L27-30).
Week #8: Decidability and undecidability (L31-33).
Week #9: Undecidability, λ-calculus (L34,35,37).
Week #10: Gödel's theorem (L38-39). Midterm exam!

Course Materials:

Week 0 (Big Bang through 26 March 2006):

There is a form for office-hours scheduling available. Please fill it out by Wednesday, 22 March 2006, and I'll schedule office hours on Thursday or Friday. (Be sure to include your email address!)

Office hours are now scheduled: M 2:00–3:00p, T 2:30p–4:00p, and F 12:00–1:00p.

Week 1 (27 March through 2 April 2006):

Class is cancelled on Friday for the campus-wide Katrina event. There will be a make-up class on Thursday evening at 7:00p in CMC 319.

The survey distributed in class on Monday is due at the beginning of class on Wednesday.

27 March 2006 (M): course overview and a boatload of definitions (Kozen L1, L2).
29 March 2006 (W): intro to DFAs (Kozen L3).
30 March 2006 (R), 7:00p (Make-up for Friday): more DFAs; closure properties for regular languages (Kozen L3, L4).

Week 2 (3 April 2006 through 9 April 2006):

PS1, distributed in class on Monday, 27 March 2006, is due at the beginning of class on Monday.

A note on problem sets: you may use (without reproving) anything that I proved in class or that is proved in the book.

3 April 2006 (M): product construction concluded; intro NFAs (Kozen L4, L5, L6).
5 April 2006 (W): subset construction; ε-transitions (Kozen L5, L6).
7 April 2006 (F): regular expressions (Kozen L7, L8; Wikipedia structural induction).

Week 3 (10 April 2006 through 16 April 2006):

PS2, distributed in class on Monday, 3 April 2006, is due at the beginning of class on Monday.

As per your request, I'll put a copy of problem sets on the mathcs machines (in /Accounts/courses/cs237/dlibenno). Let me know if you notice that I've forgotten to put a particular assignment there.

10 April 2006 (M): regular expressions, patterns, and regular languages (Kozen L8, L9).
12 April 2006 (W): nonregular languages and the pumping lemma (Kozen L11, L12).
14 April 2006 (F): proofs of nonregularity, intro to DFA minimization (Kozen L12, L13).

Week 4 (17 April 2006 through 23 April 2006):

PS3, distributed in class on Monday, 10 April 2006, is due at the beginning of class on Monday.

The first midterm of the course has been scheduled (by a bitterly divided electorate) for next Wednesday, 26 April 2006. You may bring one 8.5"-by-11" sheet of paper containing handwritten notes. You can 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.
Update: coverage is through the end of class on Wednesday (i.e., everything about regular languages), and thus anything up to and including Lecture 18 in the book.

17 April 2006 (M): DFA state minimization (Kozen L13, L14).
19 April 2006 (W): regular-language miscellanea (Kozen L10, L12, L15, L16, L17, L18).
21 April 2006 (F): many hints on PS4#1, CFGs, CFLs (Kozen L19).

Week 5 (24 April 2006 through 30 April 2006):

PS4, distributed in class on Monday, 17 April 2006, is due at the beginning of class on Monday.

Midterm #1 is scheduled for Wednesday.

24 April 2006 (M): balanced parentheses and CFL closure properties (Kozen L20, L27).
26 April 2006 (W): midterm exam.
28 April 2006 (F): CFG normal forms, CKY algorithm (Kozen L21, L27).

Week 6 (1 May 2006 through 7 May 2006):

Midterm break is on Monday—enjoy!

PS5, distributed in class on Friday, 28 April 2006, is due at the beginning of class on Wednesday.

3 May 2006 (W): pumping lemma, non-closure properties for CFLs (Kozen L22, L27; NYT, Nature on ornithological CFGs).
5 May 2006 (F): CFL pumping lemma concluded, PDAs (Kozen L22, L23).

Week 7 (8 May 2006 through 14 May 2006):

PS6, distributed in class on Wednesday, 3 May 2006, is due at the beginning of class on Monday.

8 May 2006 (M): NPDAs, NPDAs and CFGs (Kozen L23, L24, L25, Supplementary Lecture E).
10 May 2006 (W): parsing (Kozen L26).
12 May 2006 (F): Turing machines (Kozen L28, L29).

Week 8 (15 May 2006 through 21 May 2006):

PS7, distributed in class on Monday, 8 May 2006, is due at the beginning of class on Monday.

15 May 2006 (M): more on Turing machines (Kozen L29).
17 May 2006 (W): other TM-like models, diagonalization (Kozen L30, L31).
19 May 2006 (F): diagonalization, undecidability (Kozen L31, L32).

Week 9 (22 May 2006 through 28 May 2006):

PS8, distributed in class on Monday, 15 May 2006, is due at the beginning of class on Monday.
Update! Because I didn't get as far in class on the 19th as I'd hoped, question #5 from PS8 has been deferred to PS9.

22 May 2006 (M): undecidability (Kozen L32, L33).
24 May 2006 (W): reduction, Rice's Theorem (Kozen L33, L34).
26 May 2006 (F): Rice's Theorem, VALCOMPs and undecidable problems about CFLs (Kozen L34, L35).

Week 10 (29 May 2006 through 31 May 2006):

PS9, distributed in class on Monday, 22 May 2006, is due at the beginning of class on Monday.

Midterm #2 is Wednesday. You may bring two 8.5"-by-11" sheets of paper containing notes. You can 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 sheets with your exam. Coverage for the exam is anything and everything that we have discussed in the course. Here are some practice problems, a practice final, and a practice midterm from a similar course taught elsewhere.

29 May 2006 (M): VALCOMPs concluded, Gödel's incompleteness theorem (Kozen L38, L39).
31 May 2006 (W): midterm exam.

Finals Period (1 June 2006 through 7 June 2006):

The final exam, a take home distributed during class on 31 May 2006, is due on Wednesday, 5:00p.

CS237 (Theory of Computation) Spring 2006, Carleton College