Date |
Topics |
Notes |
Readings |
Exercises |
| 04/01 |
Introduction; Turing machines |
[ps] [pdf] |
0.1-0.4 |
- |
| 06/01 |
Configurations; Computable functions; Decidable and recognizable languages |
[ps] [pdf] |
3.1, 3.3 |
3.1, 3.5, 3.8 |
| 11/01 |
Turing machine variants; Simulation |
[ps] [pdf] |
3.2 |
3.12, 3.13 |
| 13/01 |
Universal Turing machines |
[ps] [pdf] |
- |
- |
| 18/01 |
Proving decidability and recognizability; Random access machines |
[ps] [pdf] |
- |
- |
| 20/01 |
Existence of undecidable and unrecognizable languages |
[ps] [pdf] |
4.2 |
4.7, 4.8 |
| 25/01 |
The Halting problem; Reductions |
[ps] [pdf] |
5.1, 5.3 |
5.6, 5.7 |
| 27/01 |
Examples of reductions |
[ps] [pdf] |
- |
- |
| 01/02 |
Rice's theorem; Some natural undecidable languages |
[ps] [pdf] |
- |
- |
| 03/02 |
Post's correspondence problem |
[ps] [pdf] |
5.2 |
- |
| 08/02 |
Time complexity; The classes P and NP |
[ps] [pdf] |
7.1-7.3 |
7.6, 7.7, 7.8 |
| 10/02 |
Characterization of NP; the class co-NP; Views of the world |
[ps] [pdf] |
- |
- |
| 22/02 |
NP-completeness |
[ps] [pdf] |
7.4 |
7.17 |
| 24/02 |
Cook's theorem |
[ps] [pdf] |
- |
- |
| 01/03 |
3SAT; Decision, search, and optimization problems |
[ps] [pdf] |
- |
- |
| 03/03 |
Vertex Cover |
[ps] [pdf] |
7.5 |
- |
| 08/03 |
Subset-Sum; Weak NP-completeness |
[ps] [pdf] |
- |
- |
| 10/03 |
Partition; Hamiltonian-path |
[ps] [pdf] |
- |
- |
| 15/03 |
Approximation algorithms; Vertex-cover and set-cover revisited |
[ps] [pdf] |
10.1 |
- |
| 17/03 |
The Knapsack problem; Scaling; Approximation schemes |
[ps] [pdf] |
- |
- |
| 22/03 |
Inapproximability; Making extra assumptions; TSP revisited |
[ps] [pdf] |
- |
- |
| 24/03 |
Metric TSP |
[ps] [pdf] |
- |
- |
| 29/03 |
Dealing with NP-completeness |
[ps] [pdf] |
- |
- |
| 31/03 |
Space complexity |
[ps] [pdf] |
8.0 |
8.4, 8.5 |
| 05/04 |
Savitch's theorem |
[ps] [pdf] |
8.1 |
- |
| 07/04 |
Public-key cryptosystems, integer factorization, and P versus NP
| [ps] [pdf] |
- |
- |