Computer Science Dartmouth College |
## Computer Science 39 |
## Fall 2004 |

This course serves as an introduction to formal models of languages and computation. Topics covered include finite automata, regular languages, context-free languages, pushdown automata, Turing machines, computability, and NP-completeness.

It is expected that a student who enrols for this course *already
knows how to write mathematical proofs* and is generally
mathematically mature. If a student passes this basic criterion and is
interested in thinking philosophically about what a computer can or
cannot do, then this course should be great fun.

- [Nov 30]
**The final exam is ready!**Click here to access the exam. There are general instructions on page 1 which you may look at before you are ready to start. But once you look at page 2, your time has started and you must turn in the exam within 48 hours.**Please turn in the exam into Chakrabarti's mailbox**and not Huang's. - [Nov 22] For those who stuck around after today's class to muse about programs that print themselves out, here is an excellent writeup about such programs and how they work.
- [Nov 12] The two Turing Machine applets shown in class on Nov 9 are here and here.
- [Oct 24] Some explanations and examples have been added to HW4 that should answer some basic questions you may have about equivalence classes.
- [Oct 5] The administrative details page has a new section titled "challenge problems" which talks about certain extra credit problems that will show up on the homeworks from time to time. Please read that section carefully.
- [Oct 1] The slides used for the first three lectures are now up on the website; see the schedule table.
- [Sep 28] Homeowrk 1 is ready and is due on Oct 6 at the
*start*of class. To get to the homework, click the link in the schedule table. If you are unable to view or print the homework, let the instructor know right away. Please review the guidelines for homeworks on the administrative details page. - [Sep 22] Please send a blitz to the instructor with your name (only first and last name, no initials) and a password for accessing your grades in the grades database.

Lectures |
Sudikoff 115 | 12 hour | MWF 12:30-13:35, X-hr T 13:00-13:50 |

Instructor |
Amit Chakrabarti | Sudikoff 107 | 6-1710 | Office hours: MF 10:00-11:30 or by appointment |

Teaching Assistant |
Chien-Chung Huang | Sudikoff 221 | 6-8753 | Office hours: TTh 16:15-18:15 |

Textbook |
Required: "Introduction to the Theory of Computation." Michael Sipser. Suggested additional reading (not required): "Introduction to Automata Theory, Languages and Computation." J. E. Hopcroft and J. D. Ullman. |

Prerequisites |
CS 25, or a strong mathematics backround and permission of the
instructor |

Work |
One homework per week. [35 points] Two in-class quizzes. [15 points] One take-home midterm. [20 points] One take-home final exam. [30 points] Please take note of the late homework policy. |

This schedule will be updated frequently. Please check back often, and please remember to hit the RELOAD button to get the latest schedule.

For now, the dates in the table below are totally inaccurate, as should be obvious.

Date |
Reading Due |
Homework Due |
Class Topic |

Sep 22 | — | — | Welcome, administrivia, overview; Mathematical notation (slides) |

Sep 24 | 0.1, 0.2, 0.3 | — | Types of proof: by construction, by contradiction, by induction (slides) |

Sep 27 | 0.4 | — | Strings and languages; Finite automata introduced (slides) |

Sep 28 (X-hr) | 1.1 up to p34 | — | More on (deterministic) finite automata; Understanding the behavior of specific DFAs |

Sep 29 | 1.1 | — | Designing DFAs; Formal definition of a DFA |

Oct 1 | — | — | Formal definition of DFA recap; DFA computation formalized; NFA introduced |

Oct 4 | — | — | Designing NFAs; Union of two regular languages is regular |

Oct 5 (X-hr) | — | — | The concatenation of two regular languages is regular; Kleene star defined |

Oct 6 | — | HW1 | Regular expressions; Equivalence of DFAs, NFAs and regular expressions, I |

Oct 8 | 1.2 | — | Equivalence of DFAs, NFAs and regular expressions, II |

Oct 11 | 1.3 | — | Equivalence of DFAs, NFAs and regular expressions, III (lecture notes) |

Oct 12 (X-hr) | — | — | Example of DFA to RegExp conversion; The pumping lemma |

Oct 13 | — | HW2 | Applications of the pumping lemma; Closure properties of regular languages |

Oct 15 | 1.4 | — | Problem solving session, led by Chien-Chung Huang |

Oct 18 | Chapter 1 | — | Quiz 1: closed-notes, in-class |

Oct 19 (X-hr) | No lecture today | ||

Oct 20 | — | HW3 | Pushdown automata (guest lecture by Srdjan Petrovic) |

Oct 22 | 2.2 | — | More examples of PDAs; Closure (or not) properties |

Oct 25 | 2.2 (reread) | — | Closure and non-closure properties continued; PDA for
not-ww |

Oct 26 (X-hr) | — | — | Context-free grammars; Examples |

Oct 27 | — | HW4 | Equivalence of CFGs and PDAs, I (CFG to PDA, informal) |

Oct 29 | — | — | Equivalence of CFGs and PDAs, II (CFG to PDA, formal; PDA to CFG, idea) |

Nov 1 | 2.1 | — | Equivalence of CFGs and PDAs, III (PDA to CFG, almost formal) |

Nov 2 (X-hr) | No lecture today | ||

Nov 3 | — | Midterm |
Chomsky normal form; Pumping lemma for context-free languages |

Nov 5 | 2.3 | — | Proof and applications of the pumping lemma for CFLs |

Nov 8 | Chapter 2 | — | Turing machines; Informal description and simple examples |

Nov 9 (X-hr) | 3.1 up to p133 | — | Formal definition of TMs; A TM solution for
{0^{n}1^{n}2^{n}: n ≥ 0} |

Nov 10 | — | HW5 | Configurations, deciders/recognizers, multi-tape TMs (slides) |

Nov 12 | — | — | Closure properties of decidable languages; Nondeterministic TMs (slides) |

Nov 15 | — | — | Church-Turing Thesis; Enumerator TMs |

Nov 16 (X-hr) | — | — | Quiz 2: closed-notes, in-class |

Nov 17 | Chapter 3 | HW6 | Decision problems for the major language classes:
A_{DFA}, A_{CFG} and A_{TM} |

Nov 19 | 4.1 (and 4.2 ?) | — | Undecidability of A_{TM} and the halting problem;
E_{DFA}, E_{CFG} and E_{TM};
A_{TM} |

Nov 22 | 4.2 | — | Reduction from A_{TM} to E_{TM}; Undecidability
of ALL_{CFG} |

Nov 23 (X-hr) | — | HW7 | More undecidable CFG problems; time complexity, P and NP |

Nov 29 | — | — | NP-completeness and polynomial time reductions (slides) |

Nov 30 (X-hr) | 7.5 | — | The Cook-Levin theorem |

Dec 1 | 7.4 | HW8 (optional) | Wrap up |

Dec 7 | Take-home 48-hour final exam, due at 6:00pm sharp |

- Solutions to HW1
- Solutions to HW2
- Solutions to HW3
- Solutions to HW4
- Solutions to HW5
- Solutions to HW6
- Solutions to HW7
- Solutions to HW8
- Solutions to Quiz 1
- Solutions to Quiz 2
- Solutions to Midterm Exam

If you are a registered student, you may verify your grades as entered in our database using the form below.