Schedule

Date	Topics	Lecture Notes	Book Sections	Announcements
Jan. 19	Introduction	Notes #1	Sections 0.1-0.2	syllabus posted
Jan. 21	Proof techniques		Sections 0.3-0.4	Assignment #1 posted
Jan. 24	Finite automata		Section 1.1
Jan. 26	Nondeterministic FA		Section 1.2
Jan. 28	Constructing NFA		Section 1.2
Jan. 31	DFA = NFA		Section 1.2
Feb. 2	Regular operations		Sections 1.1-1.2	Assignment #2 posted
Feb. 4	Regular expressions		Sections 1.3
Feb. 7	Reg. exps give reg. languages		Sections 1.3
Feb. 9	Advanced topics	Multi-head FA		Solution to hw1 posted
Feb. 11	Pumping lemma for regular languages		Sections 1.4
Feb. 14	Context free grammars		Sections 2.1	Assignment #3 posted
Feb. 16	Regular grammars	C grammar, Midterm-I review	Sections 2.1	Solution to hw2 posted
Feb. 18	Midterm I
Feb. 21	Parse tree, Ambiguous grammars		Sections 2.1
Feb. 23	Applications in programming languages.		Sections 2.1
Feb. 25	Chomsky normal form		Sections 2.1
Feb. 28	Pushdown automata (PDA)		Sections 2.2	Homework #3 collected
March 2	PDA accepts CFL		Sections 2.2	Assignment #4 posted
March 4	CFG for PDA		Sections 2.2	Solution to hw3 posted
March 7	Pumping lemma for CFL		Sections 2.3
March 9	Closure properties for CFL
March 11	Deterministic CFL		Sections 2.4	Homework #4 collected
March 14 - 18	Spring break
March 21	Closure properties of DCFL	Snapshorts 1, 2	Sections 2.4
March 23	Chomsky hierarchy	More reading
March 25	Turing machines		Section 3.1	Assignment #5 posted
March 28	Church-Turing Thesis	Read Section 3.3 carefully	Sections 3.2-3.3	Solution to hw4 posted
March 30	Decidable problems		Section 4.1
April 1	Turing-recognizable problems	Midterm-II review	Section 3.1	Deadline for HW#5 extended to April 8
April 4	Midterm-II
April 6	Nondeterminism and decidability		Section 3.2
April 8	The Halting problem is undecidable	further reading	Section 4.2	Homework #5 collected
April 11	Mapping reducibility		Section 5.3
April 13	Midterm II review
April 15	Good Friday
April 18	Rice Theorem, PCP		Section 5.2, Exercise 5.28	Homework #6 posted
April 20	Time complexity, the class P		Sections 7.1-7.2	Solution to hw5 posted
April 22	CFLs are in P		Section 7.2
April 25	The class NP		Section 7.3
April 27	Two equivalent definitions of NP		Section 7.3
May 2	NP-completeness theory		Section 7.4	Homework #6 collected
May 3	Space complextiy and Course Review	Course Review	Chapter 8	Solution to hw6 posted

Assignments
(Assignments are due on the designated due dates at the beginning of the class)

Assignment	Due Date	Solution
Assignment #1	Feb. 2	Solution
Assignment #2	Feb. 14	Solution
Assignment #3	Feb. 28	Solution
Assignment #4	March 11	Solution
Assignment #5	April 8	Solution
Assignment #6	April 29	Solution