Teaching     Home
Dartmouth Logo
Computer Science
Dartmouth College

Computer Science 39
Theory of Computation

Amit Chakrabarti

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

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: MF 10:00-11:30 or by appointment
Teaching Assistant

Khanh Do Ba | Sudikoff 114 | 6-5573 | Office hours: Tu 17:00-19:00, Th 19:00-21: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.



Reading Due

Homework Due

Class Topic

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