Spring 2007, Carleton College

- Instructor: David Liben-Nowell
- Lecture: 2a (MW 9:50--11:00p, F 9:40--10:40a), CMC 210.
- 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:
*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 Mathematics 236 or consent of the instructor.*

- 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!

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!)

- 26 March 2007 (M): history of computing (600 BCE ff.), strings, languages. Reading: L01, L02.
- 28 March 2007 (W): more on strings and sets, DFAs. Reading: L02, L03.
- 30 March 2007 (F): more regular languages, closure of regular languages under complement. Reading: L03, L04.

Problem Set #1 is due on Monday and Wednesday.

- 2 April 2007 (M): product construction, nondeterminism and NFAs. Reading: L04, L05, L06.
- 4 April 2007 (W): subset construction. Reading: L05, L06.
- 6 April 2007 (F): patterns and regular expressions. Reading: L07, L08, L09.

Problem Set #2 is due on Monday and Wednesday.

- 9 April 2007 (M): equivalence of regular expressions and DFAs. Reading: L08, L09.
- 11 April 2007 (W): non-regular languages and the pumping lemma. Reading: L11, L12.
- 13 April 2007 (F): DFA state minimization. Reading: L13, L14.

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.

- 16 April 2007 (M): DFA state minimization, homomorphisms. Reading: L14, L10, L12.
- 18 April 2007 (W): homomorphisms, ultimate periodicity, Myhill–Nerode relations. Reading: L10, L12, L15–18.
- 20 April 2007 (F): context-free languages and grammars. Reading: L19.

Problem Set #4 is due on Wednesday.

- 23 April 2007 (M): midterm #1
- 25 April 2007 (W): balanced parentheses, normal forms. Reading: L20, L21, L27.
- 27 April 2007 (F): CFL closure properties and the CKY algorithm. Reading: L27.

Problem Set #5 is due on Wednesday.

- 30 April 2007 (M): midterm break!
- 2 May 2007 (W): pushdown automata. Reading: L23; skim LE, L24, L25 (at least for the results).
- 4 May 2007 (F): non-context-free languages. Reading: L22, L27.

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.

- 7 May 2007 (M):
*class cancelled!*Find a nice tree and read L26 and the parsing handout under it. - 9 May 2007 (W): CFL wrapup, intro to Turing machines. Reading: L28, L29.
- 11 May 2007 (F): midterm #2

Problem Set #7 is due on Wednesday and Friday.

- 14 May 2007 (M): more on Turing machines. Reading: L29, L30.
- 16 May 2007 (W): some TM-like models. Reading: L30, L31.
- 18 May 2007 (F): uncomputability and diagonalization. Reading: L31, L32.

Problem Set #8 is due on Wednesday and Friday.
(Update: skip #5; only 2 questions are due Wednesday.)

- 21 May 2007 (M): the halting problem, more on undecidability. Reading: L31, L32, L33.
- 23 May 2007 (W): reductions and more undecidable problems. Reading: L33, L34.
- 25 May 2007 (F): Rice's Theorem. Reading: L34.

Problem Set #9 is due on Wednesday.

- 28 May 2007 (M): VALCOMPs and undecidable problems about CFLs. Reading: L35.
- 30 May 2007 (W): Gödel's incompleteness theorem. Reading: L38, L39, LK.

- If you'd like to use LaTeX to type your solutions, you should take
a look at this tutorial.
LaTeX is installed on the CS machines, and you can use it by typing
`latex exam.tex`(or whatever). - If you want to use a completely obvious fact in your solutions, you can assert that fact without proof. Use common sense regarding what is or is not completely obvious.