CS 240 Schedule

Slides for each week's lectures are available by clicking on the topic for that week.

The following schedule roughly estimates the day we will cover given material and is subject to change. You are responsible for keeping yourself informed of the possible evolution in content and schedule. The assigned readings should be read before the corresponding class. You are responsible for keeping up with the reading and for all material covered in class (some of which may not be in the book). This includes classnotes, assignments, handouts, additional readings, etc. If you miss a class for any reason you are responsible for making arrangements with classmates to provide you with all information disseminated in class that day.

WeekTopicReadingAssignment
8/31 Review of mathematical concepts and proof techniques (PPT)Ch. 0
9/9 Finite automata (PPT)Ch. 1.1, 1.2 A1 S1
9/16 Regular Expressions (PPT)Ch. 1.3 A2 S2
9/23 Pumping Lemma, Non-regular languages (PPT)Ch. 1.4 A3 S3
9/30 Exam I Review Review sheet Broken PL proofs More PL proofs E1-S
10/7 Context-free grammars (PPT) Ch. 2.1
10/19 Pushdown Automata (PPT)Ch. 2.2 A4 S4
10/26 Non-context-free languages (PPT)Ch. 2.3 A5 S5
11/2 CFL closure properties (PPT)
11/9Exam II Review: Exam topics CFG-PDA in-class worksheet E2-S
11/16 Turing machines (PPT)Ch. 3.1, 3.2, 3.3 A6 S6
11/23 Decidability (PPT)Ch. 4.1, 4.2 A7 S7
11/30 Reductions (PPT) Reduction HelpCh. 5.1, 5.2 A8 Latex
12/7 Exam III Review Exam III topics Decidability in-class worksheet
12/10 Exam III, 1PM-4PM 105 SP