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