Schedule

A rigid schedule is not conducive to eﬀective learning, since it would limit our ﬂexibility in exploring ideas as they arise in class. The actual schedule (both the timing and the selection of topics) will be determined by in-class interactions. Nevertheless, a partial and approximate schedule, to serve as a baseline, appears in Figure 1; it will be updated as we progress. Please use it only as a rough guide to plan your studies. Do not use it to schedule travel or other events. If you need a deﬁnite answer on when something will or will not occur, you should check with me.

At the beginning and end of each class, I typically announce the topics and textbook sections covered in that class and those due at the next class. It is important that students read the material before the class in which it is discussed and, in general, keep up with readings and studies.


Tuesday	Thursday


January 23rd C1 Introduction; recursion theorem (quick). §§ 0.*, 6.1.	25th C2 Preliminaries; recursion theorem recap. §§ 0.* (thoroughly), 6.1 (the best you can).

30th C3 Finite-state automata (FSAs). § 1.1, 1.2.	February 1st C4 Regular expressions, equivalence to FSAs, nonregular languages. § 1.3, 1.4.

6th C5 ⋆ Quiz 1, regular class time & place.	8th C6 Reg. exps.↔FSAs; Context-free grammars; pushdown automata. § 1.3, 2.{0, 1, 2}.

13th C7 Chomsky normal form, pushdown automata. § 2.2, 2.3.	15th C8 Turing Machines, Church-Turing Thesis. § 3.1, 3.2, 3.3.

20th C9 Catch-up; review.	22nd C10 ⋆ Midterm Exam 1, regular class time & place.

27th C11 Decidability. § 4.*.	March 1st C12 Reducibility. § 5.*.

6th C13 Portfolio presentations v1.	8th C14 (snow day) Reducibility and undecidable languages, contd.. § 5.*.

13th ×No class. Spring break Mar. 12th–18th.	15th ×No class. Spring break Mar. 12th–18th.

20th C15 Reducibility. § 5.*.	22nd C16 Reducibility and undecidable languages, contd.. § 5.*.

27th C17 ⋆ Quiz 2, regular class time & place.	29th C18 Time complexity basics and the class P. §§ 7.1–2.

April 3rd C19 The class P; CYK algorithm. § 7.2.	5th C20 The class NP, and NP-completeness. §§ 7.3–4.

10th C21 NP-complete problems. § 7.5.	12th C22 Space complexity; Savitch’s theorem; PSPACE completeness. §§8.1–8.3.

17th C23 Catch-up and review.	19th C24 ⋆ Midterm Exam 2, regular class time & place.

24th C25 Portfolio presentations v2.	26th C26 Classes L and NL. §§ 8.4–8.5.

May 1st C27 Synthesis and review.	3rd C28 Synthesis and review.

8th ×No class. Finals week May 7th–11th. ⋆ Final exam: May 8th 1:30–3:30 p.m.	10th ×No class. Finals week May 7th–11th. ⋆ Check Univ. schedule for ﬁnal exams.

Figure 1: Approximate schedule, likely to change. Textbook items are in §§ chapter.section format.