A rigid schedule is not conducive to effective learning, since it would limit our flexibility 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 definite 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.



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.*.


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


 ×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.


 ×No class. Finals week May 7th–11th.
 Final exam: May 8th 1:30–3:30 p.m.


 ×No class. Finals week May 7th–11th.
 Check Univ. schedule for final exams.

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