Syllabus

Here is my current plan regarding the material that I would like to cover. It is only approximate and I reserve the right to make modifications based on the interests and background of the class and/or time constraints. The plan was informed by the quiz I gave you the first day. All readings are in Sipser (3rd edition). The number in parentheses next to the date is how many classes we have that week.

Week	Topic	Reading
Jan 11 (2)	Introductions Proof Techniques	0, 1
Jan 18 (1)	Regular Languages	1
Jan 25 (2)	Context-free Languages	2.1-2.4
Feb 1 (2)	Church-Turing Thesis	3
Feb 8 (2)	Decidability	4
Feb 15 (1)	Reducibility	5.1-5.3
Feb 22 (2)	First Order Logic Reasoning about programs	6.1, Notes
Feb 29 (1)	Decidability of logical theories	6.2-6.4
Mar 14 (2)	Time Complexity	7.1-7.3
Mar 21 (2)	Time Complexity	7.4-7.5
Mar 28 (2)	Space Complexity	8.1-8.3
Apr 4 (2)	Space Complexity	8.4-8.6
Apr 11 (2)	Intractability Alternation Interactive Proof Systems	9.1,10.3,10.4

Handouts	Topic
Jan 21	Induction and Recursion
Feb 17	Decidability and Undecidability
Feb 29	Reductions
Mar 29	Oracles