Teaching     Home
Dartmouth Logo
Computer Science
Dartmouth College

Computer Science 39
Theory of Computation

Amit Chakrabarti

Fall 2006

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


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

Amit Chakrabarti | Sudikoff 107 | 6-1710 | Office hours: Mon & Fri 10:00-11:30 or by appointment
Teaching Assistants

Vibhor Bhatt | Sudikoff 221 | 6-8753 | Office hours: Tue 15:00-17:00, Sun 18:00-19:00 or by appointment
Hong Lu | Sudikoff 062 | 6-???? | Office hours: Mon 19:00-21:00, Sun 19:00-20:00 or by appointment


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



Reading Due

Homework Due

Class Topic

1 Sep 20 Welcome, administrivia, overview; Mathematical notation (slides)
2 Sep 22 0.1, 0.2, 0.3 Types of proof: by construction, by contradiction, by induction (slides)
3 Sep 25 0.4 Strings and languages; Finite automata introduced (slides)
4 Sep 26 (X-hr) 1.1 up to p34
More on (deterministic) finite automata; examples of DFAs; third-last-char challenge
5 Sep 27 1.1
Formal definition of DFA as (Q,Σ,δ,q0,F); DFA computation formalized
6 Sep 29
NFA introduced; Examples; Formalization of NFAs and NFA computation
7 Oct 2
Designing NFAs; Union and concatenation of two regular languages is regular
8 Oct 3 (X-hr)
Kleene star; Regular expressions and examples
9 Oct 4 1.3 up to p66 HW1
Equivalence of DFAs, NFAs and regular expressions, I
10 Oct 6 1.2
Equivalence of DFAs, NFAs and regular expressions, II
11 Oct 9 1.3
Equivalence of DFAs, NFAs and regular expressions, III (lecture notes)
12 Oct 10 (X-hr)
Example of DFA to RegExp conversion; The pumping lemma
13 Oct 11 HW2
Proof and applications of the pumping lemma
  Oct 13 No lecture; homecoming
14 Oct 16 Chapter 1
Closure properties of regular languages
  Oct 17 (X-hr)
Quiz 1: closed-notes, in-class
15 Oct 18 HW3
Pushdown automata (PDAs); Examples
  Oct 20
More examples of PDAs and a formal definition
16 Oct 23 2.2
Closure of context-free languages under union, concatenation and Kleene star (Vibhor)
17 Oct 24 (X-hr)
Closure and non-closure properties; a PDA for not-ww (Vibhor)
18 Oct 25 HW4
Context-free grammars; Simple examples
19 Oct 27
CFGs formalized; a CFG for equally many 0s and 1s (lecture notes)
20 Oct 30 2.1
Equivalence of CFGs and PDAs, I: PDA to CFG
21 Oct 31 (X-hr)
Equivalence of CFGs and PDAs, II: CFG to PDA (lecture notes)
22 Nov 1 2.2 (again) Midterm
Pumping lemma for context-free languages; Applications
23 Nov 3 2.3
Chomsky Normal Form; Proof of the pumping lemma for CFLs
24 Nov 6 Chapter 2
Turing machines; Informal description and simple examples
25 Nov 7 (X-hr) 3.1
Two TM applets; formal definition of a TM
26 Nov 8 HW5
Deciders/recognizers; Multi-tape TMs and their equivalence with TMs (slides)
27 Nov 10 3.2 up to p138
Nondeterministic TMs; the RAM model; Church-Turing Thesis (slides)
28 Nov 13 Chapter 3
Enumerator TMs; Decision problems for the major language classes: ADFA, ACFG and ATM
  Nov 14 (X-hr)
Quiz 2: closed-notes, in-class
29 Nov 15 4.1 HW6
Decidability of ADFA, ACFG; Recognizability of ATM; Undecidability of ATM and the halting problem
30 Nov 17 4.2 up to p180
Decidability of EDFA, ALLDFA, EQDFA, ECFG; Unrecognizability of ATM and ETM
31 Nov 20 Chapter 4; 5.1 up to p192; 5.3
Time complexity, P and NP
32 Nov 21 (X-hr) 7.1 – 7.3
NP-completeness and polynomial time reductions (slides)
33 Nov 27 7.4 up to p276; 7.5 HW7
More NP-completeness proofs
34 Nov 28 (X-hr) 7.5
Computation tableaux; The Cook-Levin theorem; Unrecognizability of ALLCFG;
33 Nov 29 7.4 HW8 (optional) Wrap up
  Dec 5 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