Syllabus for CSC 4170-50
Theory of Computation

Date	Chapter	Topic
Jan 16	1.1	Introduction and review
Jan 18	----	BNF
Jan 23	1.2	Languages and grammars (most important!)
Jan 25	2.1	DFAs and their implementation
Jan 30	2.2	NDFAs and their implementation
Feb 1	2.3	DFAs = NDFAs
Feb 6	3.1	Regular expressions
Feb 8	3.2	Regular expressions denote regular languages
Feb 13	3.3	Regular grammars
Feb 15	4.1, 4.2	Closure, homomorphism
Feb 20	4.3	Pigeonhole principle, pumping lemma (difficult)
Feb 22	----	Review for midterm
Feb 27	----	Midterm exam
Feb 29	5.1	CFGs
Mar 5	5.2	Parsing and ambiguity
Mar 7	7.1	Pushdown automata
Mar 19	7.2, 7.3	NPDAs & CFGs
Mar 21	8.1	A pumping lemma for cfgs (still difficult)
Mar 26	9.1	Turing machines
Mar 28	10.4, 10.5	Universal Turing Machines and LBAs
Apr 2	11.1	Recursively enumerable languages
Apr 9	11.2	Unrestricted grammars
Apr 11	11.3, 11.4	The Chomsky hierarchy
Apr 16	12.1	Undecidable problems
Apr 18	13.1	Church's Thesis
Apr 23	13.2	Complexity Theory, P and NP
Apr 25	all	Review for Final
Apr 30	----	Go over homework, Q & A
May 7	Cumulative	Final exam 5:30-7:30