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