 |
6.045/18.400 |
| Course Home Page |
| Objectives and Outcomes |
| Contact Info |
| General Information/Policies |
| Calendar |
|
||||||
|
| February 2005 | ||||||
| Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday |
| 1 | 2
Class begins Lecture 1: Introduction | 3 Recitation 1: Math Review | 4 | 5 | ||
| 6 | 7 Lecture 2: Deterministic Finite Automata | 8 | 9 Lecture 3: Nondeterministic Finite Automata | 10 Recitation 2: DFAs and NFAs | 11 | 12 |
| 13 | 14 Lecture 4: Regular Expressions | 15 | 16 Lecture 5: Non-regular Languages | 17 Recitation 3: Regular Expressions and Non-regular languages | 18 | 19 |
| 20 | 21 No class (Presidents Day) | 22
Lecture 6: Algorithms for Automata | 23 Lecture 7: Quiz 1 | 24 Recitation 4: Quiz Questions and Automata Wrap-up | 25 | 26 |
| 27 | 28
Lecture 8: Turing Machines | |||||
| March 2005 | ||||||
| Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday |
| 1 | 2 Lecture 9: Nondeterministic TMs | 3 Recitation 5: Turing Machines | 4 | 5 | ||
| 6 | 7 Lecture 10: Undecidability | 8 | 9 Lecture 11: PCP | 10 Recitation 6: Undecidibility | 11 | 12 |
| 13 | 14 Lecture 12: Reducibility | 15 | 16 Lecture 13: Recursion Theorem | 17 Recitation 7: Reducibility, Rice's Theorem and Recursion Theorem | 18 | 19 |
| 20 | 21 Spring Vacation | 22 Spring Vacation | 23 Spring Vacation | 24 Spring Vacation | 25 Spring Vacation | 26 |
| 27 | 28 Lecture 14: Counter and Stack Machines | 29 | 30
Lecture 15: Quiz 2 | 31
Recitation 8: Quiz 2 Questions and Computability Wrap-up | ||
| April 2005 | ||||||
| Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday |
| 1 | 2 | |||||
| 3 | 4 Lecture 16: Time Complexity | 5 | 6 Lecture 17: Nondeterministic Time Complexity | 7 Recitation 9: P and NP | 8 | 9 |
| 10 | 11 Lecture 18: NP-Completeness | 12 | 13 Lecture 19: Cook-Levin Theorem | 14 Recitation 10: Poly-Time Reductions | 15 | 16 |
| 17 | 18 No Class (Patriots Day) | 19 | 20 Lecture 20: NP-Completeness II | 21 Recitation 11: NP-Completeness Drop date | 22 | 23 |
| 24 | 25 Lecture 21: Advanced Time-Complexity | 26 | 27 Lecture 22: Quiz III | 28
Recitation 12: Quiz 3 Questions and End of Time-Complexity | 29 | 30 |
| May 2005 | ||||||
| Sunday | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday |
| 1 | 2 Lecture 23: Space Complexity | 3 | 4 Lecture 24: Space Complexity II | 5 Recitation 13: Space Complexity III | 6 | 7 |
| 8 | 9 Lecture 25: Probabilistic Complexity | 10 | 11 Last class Lecture 26: Probabilistic Complexity | 12 Last recitations Recitation 14: Probabilistic Complexity and Interactive Proofs | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 | 31 | ||||