Computer Science
Dartmouth College
|
Computer Science Dartmouth College |
Computer Science 39 |
Winter 2005 |
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.
| Lectures |
Sudikoff 214 | 2 hour | MWF 13:45-14:50, X-hr Th 13:00-13:50 |
| Instructor |
Amit Chakrabarti | Sudikoff 107 | 6-1710 | Office hours: MW 11:30-12:30 and 15:00-16:00; also by appointment |
| Teaching Assistant |
Chien-Chung Huang | Sudikoff 221 | 6-8753 | Office hours: TTh 16:00-18:00 or by appointment |
| 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 |
| Jan 5 | — | — | Welcome, administrivia, overview; Mathematical notation (slides) |
| Jan 6 (X-hr) | 0.1, 0.2, 0.3 | — | Types of proof: by construction, by contradiction, by induction (slides) |
| Jan 7 | 0.4 | — | Strings and languages; Finite automata introduced (slides) |
| Jan 8 (Sat) | 1.1 up to p34 | — | Examples of DFAs; formal definition as (Q,Σ,δ,q0,F) |
| Jan 10 | 1.1 up to p40 | — | Formal definition of DFA recap; More examples of DFAs; NFA introduced |
| Jan 12 | 1.1 | — | Formal definition of NFA; DFA and NFA computation formalized |
| Jan 13 (X-hr) | 1.2 up to p54 | — | Designing NFAs; Union of two regular languages is regular |
| Jan 14 | — | HW1 | Concatenation of languages; Kleene star; regular expressions and examples |
| Jan 17 | No lecture; Martin Luther King Jr. day | ||
| Jan 19 | 1.3 up to p69 | — | Equivalence of DFAs, NFAs and regular expressions, I |
| Jan 20 (X-hr) | — | — | Equivalence of DFAs, NFAs and regular expressions, II (lecture notes) |
| Jan 21 | Notes | HW2 | Example of DFA to RegExp conversion; The pumping lemma |
| Jan 24 | 1.4 up to 79 | — | Applications of the pumping lemma; Closure properties of regular languages |
| Jan 26 | — | 1.4 | Wrap-up of regular language theory; Pushdown automata |
| Jan 27 (X-hr) | — | — | Quiz 1: closed-notes, in-class |
| Jan 28 | 1.4 | HW3 | More examples of PDAs; closure under union |
| Jan 31 | 2.2 up to p106 | — | Closure of PDA-recognizable languages under concatenation and Kleene star |
| Feb 2 | — | — | Closure under intersection with a regular language; PDA for not-ww |
| Feb 3 (X-hr) | — | — | Context-free grammars; Examples |
| Feb 4 | — | HW4 | More examples of CFGs: palindromes; {0n1n}; equally many 0s and 1s |
| Feb 7 | 2.1 up to p98 | — | Ambiguity; leftmost deriviations; informal description of CFG to PDA conversion |
| Feb 9 | — | — | Equivalence of CFGs and PDAs, I (CFG to PDA) |
| Feb 10 (X-hr) | — | — | Equivalence of CFGs and PDAs, II (PDA to CFG) -- lecture by Chien-Chung |
| Feb 11 | No lecture; Carnival holiday | ||
| Feb 14 | 2.2 | Midterm | Pumping lemma for context-free languages: applications |
| Feb 16 | 2.3 | — | Chomsky normal form; proof of CFL pumping lemma |
| Feb 17 (X-hr) | Chapter 2 | — | Turing machines; Informal description and simple examples |
| Feb 18 | 3.1 | HW5 | TM formalized; Configurations, deciders/recognizers, multi-tape TMs (slides) |
| Feb 21 | 3.2 up to p138 | — | Closure properties of decidable languages; Nondeterministic TMs (slides) |
| Feb 23 | 3.2 | — | Church-Turing Thesis; Enumerator TMs |
| Feb 24 (X-hr) | — | — | Quiz 2: closed-notes, in-class |
| Feb 25 | Chapter 3 | HW6 | Decision problems for the major language classes: ADFA, ACFG and ATM |
| Feb 28 | — | — | Decidability of EDFA, ECFG, ALLDFA, EQDFA; Undecidability of ATM and the halting problem |
| Mar 2 | Chapter 4 | — | Undecidability of ETM; unrecognizability of ATM |
| Mar 3 (X-hr) | 5.1 up to p176; 5.3 | — | Time complexity, P and NP |
| Mar 4 | — | HW7 | NP-completeness and polynomial time reductions (slides) |
| Mar 7 | — | — | |
| Mar 9 | — | HW8 | |
| Mar 15 | Take-home 48-hour final exam, due at 6:00pm sharp | ||
If you are a registered student, you may verify your grades as entered in our database using the form below.
