|
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 |
|
|