The lectures assume that you have already done the pre-class readings from the textbook (Sipser). So they do not walk through basic definitions but, rather, concentrate on aspects of the topic that you probably didn't fully understand after doing the readings. This schedule is just a draft for now; the topics may shift around and the readings will be made more specific soon, but the exam dates will not change.
Week | Monday | Tuesday | Thursday | Friday | ||||
---|---|---|---|---|---|---|---|---|
Week 1 Jan 17-21 |
Pre-class reading: Chapter 0: intro and section 1 (p1-3), and subsection "strings and languages" (p13-14) [topics are from Sipser 1.1-1.3] |
Pre-class reading: None [topic is from Sipser 1.4] |
Warm-up Problems 1 due at midnight | |||||
Week 2 |
Homework 1 due at midnight | Pre-class reading: definition and examples of PDAs (section 2.2, p111-116) academic integrity policy CFGs / PDAs (worksheet) |
Pre-class reading: definition and examples of CFGs (Section 2.1 p102-105) CFGs / PDAs |
Warm-up Problems 2 due at midnight | ||||
Week 3 |
Homework 2 due at midnight |
CFGs / PDAs |
Pre-class reading: Intro to Turing Machines (p165-170) Turing machine defn. and variants |
Warm-up Problems 3 due at midnight | ||||
Week 4 |
Homework 3 due at midnight |
campus emergency info Exam review |
Exam 1 | No warm-up problems due | ||||
Week 5 Feb 14-18 |
No HW due today |
regrade requests |
(un)decidable languages |
Warm-up Problems 5 due at midnight | ||||
Week 6 Feb 21-25 |
Homework 4 due at midnight | Enumerators (worksheet) |
Pre-class reading: p215-217 Reducibility |
Warm-up Problems 6 due at midnight | ||||
Week 7 Feb 28-Mar 4 |
Homework 5 due at midnight | Reductions using computation histories (worksheet) |
Turing Reducibility (Oracle TMs) (worksheet) |
Warm-up Problems 7 due at midnight (extended to Sunday) | ||||
Week 8 Mar 7-11 |
Homework 6 due at midnight | Exam review (worksheet) |
Exam 2 | No warm-up problems due | ||||
Spring Break | ||||||||
Week 9 Mar 21-25 |
No HW due today | Time complexity (worksheet) |
Time complexity (including NP and ptime-reductions) (worksheet) |
Warm-up Problems 9 due at midnight | ||||
Week 10 Mar 28-Apr 1 |
Homework 7 due at midnight | Time complexity (including NP and ptime-reductions) (worksheet) |
Time complexity (including NP and ptime-reductions) (worksheet) |
Warm-up Problems 10 due at midnight | ||||
Week 11 Apr 4-8 |
Homework 8 due at midnight | (Chap. 8) Space complexity (worksheet) |
Space complexity (worksheet) |
|||||
Week 12 Apr 11-15 |
Homework 9 due at midnight | Exam review (worksheet) |
Exam 3 | No warm-up problems due | ||||
Week 13 Apr 18-22 |
No HW due today |
Space complexity: L and NL |
(Chap. 6) Recursion theorem |
|||||
Week 14 Apr 25-29 |
Homework 10 due at midnight |
Hierarchy Theorems and Relativization (Ch 9) |
Descriptive complexity (Ch 6) |
|||||
Week 15 May 2-6 |
Homework 11 due at midnight | Exam review (worksheet) |
No class | |||||
Finals Week |