Teaching     Home
Dartmouth Logo
Computer Science
Dartmouth College

Computer Science 39
Theory of Computation

Amit Chakrabarti

Fall 2007

[ 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 | Mon-Wed-Fri 12:30-13:35, X-hr Tue 13:00-13:50

Amit Chakrabarti | Sudikoff 107 | 6-1710 | Office hours: Wed 17:00-18:00, Sun 14:00-16:00, or by appointment
Teaching Assistants

Umang Bhaskar | Sudikoff 205 | 6-8745 | Office hours: Thu 16:30-17:30, Sun 16:30-18:30, or by appointment
Ranganath Kondapally | Sudikoff 112 | 6-0569 | Office hours: Thu 16:30-17:30, Sun 16:30-18:30, 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.

Lecture Number
and Date

Reading Due
Before Class


Topics Covered in
This Lecture

1 Sep 26 Welcome, administrivia, overview; Mathematical notation (slides)
2 Sep 28 0.1, 0.2, 0.3 Types of proof: by construction, by contradiction, by induction (slides)
3 Oct 1 0.4 Strings and languages; Finite automata introduced (slides)
4 Oct 2 (X-hr) 1.1 up to p34
More on (deterministic) finite automata; some examples of DFAs
5 Oct 3 1.1
Formal definition of DFA as (Q,Σ,δ,q0,F); further examples; the third-last-char challenge
6 Oct 5
NFA introduced; Examples; Formalization of NFAs and DFA/NFA computation
7 Oct 8 HW1
More on NFAs; The union, concatenation and Kleene star operations
8 Oct 9 (X-hr)
Regular expressions, examples, conversion to NFA (lecture notes)
9 Oct 10 1.3 up to p66
Equivalence of DFAs, NFAs and regular expressions, I
10 Oct 12 1.2
Equivalence of DFAs, NFAs and regular expressions, II (lecture notes)
11 Oct 15 1.3 HW2
The pumping lemma and its proof
12 Oct 16 (X-hr) 1.4
Applications of the pumping lemma: proving languages to be non-regular
13 Oct 17
Closure properties of regular languages
  Oct 19 No lecture; homecoming
14 Oct 22 Chapter 1 HW3
Pushdown automata (PDAs); Examples
  Oct 23 (X-hr)
Quiz 1: closed-notes, in-class
15 Oct 24
More examples of PDAs
16 Oct 26
More examples of PDAs; Introduction to Context-Free Grammars
17 Oct 29 2.2 HW4
Examples of CFGs; CFG for equally many 0s as 1s (lecture notes)
18 Oct 30 (X-hr)
CFGs formalized; closure of CFLs under union, concatenation and Kleene star
19 Oct 31 2.1
Equivalence of CFGs and PDAs, I: PDA to CFG
20 Nov 2
Equivalence of CFGs and PDAs, II: CFG to PDA (lecture notes)
21 Nov 5 2.2 (again) Midterm
Pumping lemma for context-free languages; Applications
22 Nov 6 (X-hr) 2.3
Chomsky Normal Form; Proof of the pumping lemma for CFLs
23 Nov 7 Chapter 2
Turing machines; Informal description and simple examples
24 Nov 9 3.1
Two TM applets; formal definition of a TM
25 Nov 12 HW5
Deciders/recognizers; Multi-tape TMs and their equivalence with TMs (slides)
26 Nov 13 (X-hr) 3.2 up to p150
Review session with TAs
27 Nov 14
Nondeterministic TMs; the RAM model; Church-Turing Thesis (slides)
28 Nov 16 Chapter 3
Enumerator TMs; Decision problems for the major language classes: ADFA, ACFG and ATM
29 Nov 19 HW6
Decidability of ADFA, ACFG; Recognizability of ATM; Undecidability of ATM; Unrecognizability of ATM
  Nov 20 (X-hr) 4.1
Quiz 2: closed-notes, in-class
30 Nov 26 4.1 (again)
Reductions; Decidability of EDFA, ALLDFA, EQDFA, ECFG; Unrecognizability of ETM
31 Nov 27 (X-hr) Chapter 4
Time complexity, P and NP
32 Nov 28 5.1 up to p192; 5.3 HW7
NP-completeness and polynomial time reductions (slides)
33 Nov 30 7.1 – 7.3
More NP-completeness proofs
34 Dec 3 7.4 up to p276; 7.5
Computation tableaux; The Cook-Levin theorem
35 Dec 4 (X-hr) 7.5 HW8 (optional)
Unrecognizability of ALLCFG; Wrap up
  Dec 10 Take-home 48-hour final exam, due at 6:00pm sharp
Please the click the above link for info on the final exam.
Your clock won't start until you fill out your password on that page.

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