Teaching     Home
Dartmouth Logo
Computer Science
Dartmouth College

Computer Science 39
Theory of Computation

Amit Chakrabarti

Winter 2009

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

This course has substantial mathematical content. 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.


Kemeny 008 | 11 hour | Mon-Wed-Fri 11:15-12:20, X-hr Tue 12:00-12:50

Amit Chakrabarti | Sudikoff 107 | 6-1710 | Office hours: Mon 18:00-20:00, Fri 15:00-16:30, or by appointment
Teaching Assistants

Qi (Tracy) Gu | Sudikoff 220 | 6-8752 | Office hours: Fri 16:00-18:00
Grace Moy | Sudikoff 114 | 440-554-0373 | Office hours: Sun 16:00-18:00
William Henderson-Frost | Sudikoff 114 | 817-701-6019 | Office hours: Mon 16:00-18:00


   "Introduction to the Theory of Computation," Second Edition.   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. It will be enforced, strictly.

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.

Any part of the schedule that is greyed out is tentative and subject to change.

Lecture Number
and Date

Reading Due
Before Class


Topics Covered in
This Lecture

1 Jan 5 Welcome, administrivia, overview; Mathematical notation (slides)
2 Jan 6 (X-hr) 0.1, 0.2, 0.3 Types of proof: by construction, by contradiction, by induction (slides)
3 Jan 7 0.4 Strings and languages; Finite automata; DFA examples (slides)
4 Jan 9 1.1 up to p34
Formal definition of DFA as (Q,Σ,δ,q0,F); More DFA examples
5 Jan 12 1.1
NFA introduced; Examples; Formalization of NFAs and DFA/NFA computation
6 Jan 13 (X-hr)
More on NFAs; The union, concatenation and Kleene star operations
7 Jan 14 HW1
Regular expressions, examples, conversion to NFA (lecture notes)
8 Jan 16 1.3 up to p69
Equivalence of DFAs, NFAs and regular expressions, I
  Jan 19
No lecture: MLK Day
9 Jan 20 (X-hr) 1.2
Equivalence of DFAs, NFAs and regular expressions, II (lecture notes)
10 Jan 21 1.3 HW2
The pumping lemma and proofs of non-regularity
11 Jan 23 1.4
More proofs of non-regularity; Proof of the pumping lemma
12 Jan 26
Closure properties of regular languages (guest lecture)
  Jan 27 (X-hr) Chapter 1
Open/Review session with TAs
  Jan 28 HW3
Quiz 1: closed-notes, in-class
13 Jan 30
Pushdown automata; Examples of PDAs
14 Feb 2
Formal definition of a PDA; More examples
15 Feb 3 (X-hr) 2.2 up to p115
Closure under union, concatenation and Kleene star; Context-Free Grammars (CFGs); Basic examples
16 Feb 4 2.1 up to p105 HW4
More advanced CFGs: N0 = N1 and non-xx strings (lecture notes)
17 Feb 6
Equivalence of CFGs and PDAs, I: PDA to CFG
18 Feb 9
Equivalence of CFGs and PDAs, II: CFG to PDA (lecture notes)
  Feb 10 (X-hr) 2.2
Open/Review session with TAs
19 Feb 11 Midterm
Chomsky Normal Form; Conversion Algorithm; Pumping lemma for CFLs (guest lecture)
  Feb 13
No lecture: Winter Carnival
20 Feb 16 2.3
Applications of CFL pumping lemma; Closure properties
21 Feb 17 (X-hr) Chapter 2
Turing machines; formal description; demos (palindromes, adder)
22 Feb 18 3.1
Deciders/recognizers; Multi-tape TMs and their equivalence with TMs (slides)
23 Feb 20 HW5
Nondeterministic TMs; the RAM model; Church-Turing Thesis (slides)
24 Feb 23 3.2 up to p150
Enumerator TMs; Decision problems for the major language classes: ADFA, ACFG and ATM
25 Feb 24 (X-hr) Chapter 3
Decidability of ADFA, ACFG; Recognizability of ATM; Undecidability of ATM; Unrecognizability of ATM
26 Feb 25 4.1 HW6
Reductions; Decidability of EDFA, ALLDFA, EQDFA, ECFG; Unrecognizability of ETM
  Feb 27 Chapter 4
Quiz 2: closed-notes, in-class
27 Mar 2 5.1 up to p192; 5.3
Time complexity, P and NP
28 Mar 3 (X-hr) 7.1
NP-completeness and polynomial time reductions (slides)
29 Mar 4 7.1 – 7.3 HW7
More NP-completeness proofs
30 Mar 6
Computation tableaux; The Cook-Levin theorem
31 Mar 9
Cook-Levin theorem continued; Unrecognizability of ALLCFG
32 Mar 10 (X-hr) 7.4 up to p276; 7.5 HW8 (optional)
Mar 16 Take-home 48-hour final exam, due at 6:00pm sharp
The final exam webpage is now closed.

Solutions to Homework and Exam Problems

These will be provided in class, when graded homeworks are given out. Hard-copy only.

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