|
Schedule
(subject to change) |
| 16-Jan |
Introduction, some history. |
|
|
| 18-Jan |
Turing machines, languages |
Ch 3.1 |
|
| 21-Jan |
Holiday. |
|
|
| 23-Jan |
|
|
|
| 25-Jan |
2 tapes |
Ch 3.2 |
|
| 28-Jan |
Cellular automata. |
|
|
| 30-Jan |
Universal Turing machines |
All resources other than Sipser. |
|
| 1-Feb |
|
Ch 3.3 |
|
| 4-Feb |
The definition of an algorithm. Big Oh notation, analyzing algorithms. |
Ch. 3.3, 7.1 |
|
| 6-Feb |
Complexity relationships among models, more big-Oh. |
|
|
| 8-Feb |
Snow closing |
|
|
| 11-Feb |
The class P |
Ch 7.2 |
|
| 13-Feb |
|
|
|
| 15-Feb |
Midterm exam 1 |
|
|
| 18-Feb |
Holiday. |
|
|
| 20-Feb |
|
|
Substitute Monday (labs).
Thursday last day to drop classes without a W. |
| 22-Feb |
The class NP, witnesses, nondeterminism |
Ch 7.3 |
|
25-Feb
|
More examples of problems in NP |
Set of linear equations. |
|
| 27-Feb |
Dynamic programming for subset sum. |
Ch 7.4 |
|
| 1-Mar |
Propositional logic. |
|
|
| 4-Mar |
Reduce matching to SAT. Logic circuits |
|
|
| 6-Mar |
Reduce logic circuits to 3SAT. Start Proof of the Cook-Levin theorem |
Ch 7.5 |
|
8-Mar
|
Reductions to several combinatorial problems. |
Ch 4.2 |
|
| 18-Mar |
Completeness of subset sum |
|
|
| 20-Mar |
A Turing-unrecognizable language |
|
|
| 22-Mar |
|
|
|
| 25-Mar |
Review |
|
|
| 27-Mar |
Midterm exam 2 |
|
|
| 29-Mar |
Midterm review |
|
Last day to drop classes with a W. |
| 1-Apr |
Computably enumerable languages, halting problem, reduction |
Ch 5.2 |
|
| 3-Apr |
More undecidable problems |
Ch 5.3 |
|
| 5-Apr |
|
|
|
| 8-Apr |
More NP reductions: partition |
|
|
| 10-Apr |
Hamiltonian path |
|
|
| 12-Apr |
Approximation algorithms |
Ch 10.1 |
|
| 15-Apr |
Holiday |
|
|
| 17-Apr |
|
|
|
| 18-Apr |
Randomized algorithms |
Ch 10.2 |
Substitute Monday (labs) |
| 19-Apr |
|
|
|
| 22-Apr |
|
|
|
| 24-Apr |
Decidability of logical theories |
Lecture notes and Ch 6.2. |
|
| 26-Apr |
|
|
|
| 29-Apr |
|
|
|
| 1-May |
Review |
|
|
| 7-May |
Final exam 9-11am |
|
|