Teaching     Home
Dartmouth Logo
Computer Science
Dartmouth College

Computer Science 39
Theory of Computation

Amit Chakrabarti

Fall 2004

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

Chien-Chung Huang | Sudikoff 221 | 6-8753 | Office hours: TTh 16:15-18:15

   "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

Sep 22 Welcome, administrivia, overview; Mathematical notation (slides)
Sep 24 0.1, 0.2, 0.3 Types of proof: by construction, by contradiction, by induction (slides)
Sep 27 0.4 Strings and languages; Finite automata introduced (slides)
Sep 28 (X-hr) 1.1 up to p34 More on (deterministic) finite automata; Understanding the behavior of specific DFAs
Sep 29 1.1 Designing DFAs; Formal definition of a DFA
Oct 1 Formal definition of DFA recap; DFA computation formalized; NFA introduced
Oct 4 Designing NFAs; Union of two regular languages is regular
Oct 5 (X-hr) The concatenation of two regular languages is regular; Kleene star defined
Oct 6 HW1 Regular expressions; Equivalence of DFAs, NFAs and regular expressions, I
Oct 8 1.2 Equivalence of DFAs, NFAs and regular expressions, II
Oct 11 1.3 Equivalence of DFAs, NFAs and regular expressions, III (lecture notes)
Oct 12 (X-hr) Example of DFA to RegExp conversion; The pumping lemma
Oct 13 HW2 Applications of the pumping lemma; Closure properties of regular languages
Oct 15 1.4 Problem solving session, led by Chien-Chung Huang
Oct 18 Chapter 1 Quiz 1: closed-notes, in-class
Oct 19 (X-hr) No lecture today
Oct 20 HW3 Pushdown automata (guest lecture by Srdjan Petrovic)
Oct 22 2.2 More examples of PDAs; Closure (or not) properties
Oct 25 2.2 (reread) Closure and non-closure properties continued; PDA for not-ww
Oct 26 (X-hr) Context-free grammars; Examples
Oct 27 HW4 Equivalence of CFGs and PDAs, I (CFG to PDA, informal)
Oct 29 Equivalence of CFGs and PDAs, II (CFG to PDA, formal; PDA to CFG, idea)
Nov 1 2.1 Equivalence of CFGs and PDAs, III (PDA to CFG, almost formal)
Nov 2 (X-hr) No lecture today
Nov 3 Midterm Chomsky normal form; Pumping lemma for context-free languages
Nov 5 2.3 Proof and applications of the pumping lemma for CFLs
Nov 8 Chapter 2 Turing machines; Informal description and simple examples
Nov 9 (X-hr) 3.1 up to p133 Formal definition of TMs; A TM solution for {0n1n2n: n ≥ 0}
Nov 10 HW5 Configurations, deciders/recognizers, multi-tape TMs (slides)
Nov 12 Closure properties of decidable languages; Nondeterministic TMs (slides)
Nov 15 Church-Turing Thesis; Enumerator TMs
Nov 16 (X-hr) Quiz 2: closed-notes, in-class
Nov 17 Chapter 3 HW6 Decision problems for the major language classes: ADFA, ACFG and ATM
Nov 19 4.1 (and 4.2 ?) Undecidability of ATM and the halting problem; EDFA, ECFG and ETM; ATM
Nov 22 4.2 Reduction from ATM to ETM; Undecidability of ALLCFG
Nov 23 (X-hr) HW7 More undecidable CFG problems; time complexity, P and NP
Nov 29 NP-completeness and polynomial time reductions (slides)
Nov 30 (X-hr) 7.5 The Cook-Levin theorem
Dec 1 7.4 HW8 (optional) Wrap up
Dec 7 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