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.
|
Monday |
Wednesday |
Friday |
|
September 2nd
×No class. Labor Day.
|
4th C1
Preliminaries. §§ 0.*.
|
6th C2
Introduction; recursion theorem (informal). §§ 0.*, 6.1.
|
|
9th C3
Finite-state automata (FSAs). § 1.1.
|
11th C4
Non-determinism (FSAs). § 1.2.
|
13th C5
Regular expressions (regexes). § 1.3.
|
|
16th
⋆ Quiz 1
|
18th C6
Equivalence of regexes and FSAs. § 1.3.
|
20th C7
Nonregular languages. § 1.4.
|
|
23rd C8
Context-free grammars (CFGs). § 2.{0, 1}.
|
25th C9
Catch-up; review.
|
27th
⋆ Midterm Exam 1
|
|
30th C10
Pushdown automata (PDAs). § 2.2.
|
October 2nd C11
CFGs and PDAs. § 2.{2, 3}.
|
4th C12
Non-context-free languages. § 2.3.
|
|
7th C13
Catch-up; review.
|
9th C14
Special topic; catch-up; review.
|
11th
⋆ Quiz 2
|
|
14th
×No class. Fall break Oct. 14th–15th.
|
16th C15
Turing Machines. § 3.1.
|
18th C16
Turing Machine variants. § 3.2.
|
|
21st C17
Church-Turing Thesis. § 3.3.
|
23rd C18
Catch-up; review.
|
25th
⋆ Midterm Exam 2
|
|
28th C19
Decidability. § 4.{0, 1}.
|
30th C20
Undecidability. § 4.2.
|
November 1st C21
Reducibility. § 5.1.
|
|
4th C22
Post Correspondence Problem (PCP). § 5.2.
|
6th C23
Catch-up; review.
|
8th
⋆ Quiz 3
|
|
11th
×No class. Veterans Day.
|
13th C24
Mapping reducibility. § 5.3.
|
15th C25
Time complexity basics and the class P. §§ 7.{0, 1, 2}.
|
|
18th C26
The class P; CYK algorithm. § 7.2.
|
20th C27
Catch-up and review.
|
22nd
⋆ Midterm Exam 3
|
|
25th C28
The class NP. § 7.3.
|
27th
×No class. Thanksgiving break Nov. 27th–Dec. 1st.
|
29th
×No class. Thanksgiving break Nov. 27th–Dec. 1st.
|
|
December 2nd C29
NP-completeness. § 7.4.
|
4th C30
NP-complete problems. § 7.5.
|
6th C31
Space complexity; Savitch’s Thm.; PSPACE completeness. §§8.1–8.3.
|
|
9th C32
Classes L and NL. §§ 8.4–8.5.
|
11th C33
Synthesis and review.
|
13th C34
Synthesis and review.
|
|
16th
×No class. ⋆ Finals week Dec. 16th–20th.
|
18th
×No class. ⋆ Final exam: Dec. 18th 12:15–2:15 p.m.
|
20th
×No class. ⋆ Check Univ. schedule for final exams.
|
|
|
||
|
|
||
|
|