Teaching     Home
Dartmouth Logo
Computer Science
Dartmouth College

Computer Science 39
Theory of Computation

Amit Chakrabarti

Winter 2005

[ Announcements | Administrative Basics | Schedule and Homeworks | Solutions | Grades Database ]

Course Description

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.


Administrative Basics

Important! Please also read and familiarize yourself with the administrative details not covered in the outline below. Pay special attention to the section that describes how the honor code applies to this course; violations of the honor code will be treated seriously.


Sudikoff 214 | 2 hour | MWF 13:45-14:50, X-hr Th 13:00-13:50

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

   "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.


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


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.

Schedule and Homeworks

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.


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

Solutions to Homework and Exam Problems

Grades Database

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

Your name, without initials or suffixes:
Your CS 39 password:

Teaching     Home