Theory of Computation	CS345
Haverford College	Spring 2002
Syllabus	John Dougherty

Week	KS	HMU	Topics
1	1, 2.1 - 2.2	1.1, 1.4 - 1.5	introduction and review; finite automata (DFA and NFA)
2	2.3 - 2.4	2.2 - 2.3, 3.1 - 3.2	equivalence of DFA and NFA; regular expressions; regular languages and properties
3	2.5 - 2.7	4.1, 4.4	nonregular languages; pumping lemma for regular languages; algorithms; state minimization
4	3.1 - 3.2	5.1 - 5.2, 5.4	context free languages (CFL) and grammars (CFG); parsing; parse trees; ambiguity
5	3.3 - 3.6	6.1 - 6.4	pushdown automata (PDA); CFL and PDA; closure; languages that are not CFL
6	3.7 - 3.8	7.1 - 7.2	Chomsky-normal form (CNF); determinism; ambiguous grammars; pumping lemma for CFL
7			Review -- Midterm Exam (take-home over break)
			Midterm break
8	4.1 - 4.2	8.2	Turing machines (TM); definitions; computations
9	4.3 - 4.5	8.4	extensions of TM; nondeterministic TM (NTM); Turing enumerable languages
10	5.1 - 5.2	9.1 - 9.2	undecidability; Church-Turing thesis; universal TM UTM)
11	5.3 - 5.5	9.3, 9.5	undecidable problems; halting problem
12	6.1 - 6.2	10.1	computational complexity; classes P and NP
13	6.2 - 6.3	10.2, 10.4, 11	NP-complete; NP-hard; other computational classes
14			Review -- Final Examination (during Finals Period)

This schedule is very tentative and may be changed.
Actual assignment and exam schedule will be announced in class.