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