This is an old revision of the document!


PHP's gd library is missing or unable to create PNG images

Approximate schedule, subject to change. You are responsible for keeping yourself informed of the schedule and any changes that may occur over time. The assigned readings should, ideally, be read before the corresponding class. You are responsible for keeping up with the reading and for all material covered in class. I will emphasize different points and some of them will not be in our text book. It is your responsibility to make arrangements with classmates, for them to provide you with all of the information disseminated in class, if you happen to miss a class.

WeekTopicReadingAssignment
1/27 Review of mathematical concepts and proof techniques (PPT)Ch. 0
2/8 Finite automata (PPT)Ch. 1.1, 1.2 A1 S1
2/15 Regular Expressions (PPT)Ch. 1.3 A2 S2
2/22 Pumping Lemma, Non-regular languages (PPT)Ch. 1.4 A3 S3
2/29 Exam I Review Review sheet Broken PL proofs More PL proofs E1-S
3/7 Context-free grammars (PPT) Ch. 2.1
3/14 Spring Break
3/21 Pushdown Automata (PPT)Ch. 2.2 A4 S4
3/28 Non-context-free languages (PPT)Ch. 2.3 A5 S5
4/4 CFL closure properties (PPT)
4/11Exam II Review: Exam topics CFG-PDA in-class worksheet E2-S
4/18 Turing machines (PPT)Ch. 3.1, 3.2, 3.3 A6 S6
4/25 Decidability (PPT)Ch. 4.1, 4.2 A7 S7
5/2 Reductions (PPT) Reduction HelpCh. 5.1, 5.2 A8 Latex
5/9 Exam III Review
5/18 Final Exam