| Date | Material covered (and corresponding parts of the CLRS textbook) |
|---|---|
| Sep 6 | Introduction and mathematical preliminaries (secs 4.1 - 4.3, 7.1 - 7.4, 28.2) |
| Sep 13 |
Graphs (B.4, pp. 1080--1084) and their adjacency matrices (22.1, pp. 527--531);
graph colouring (Problem B-1, pp. 1091--1092).
Recommended supplementary reading:
Bondy and Murty.
Class P (34.1, pp. 971--979). Recommended supplementary reading: Garey and Johnson. Background to review if necessary: Program correctness (especially loop invariants). |
| Sep 20 | Problem SAT. Reducibility (34.3, pp. 984--985). Reducing SAT to CLIQUE (34.5.1, pp. 1003--1006) and reducing 3-CNF-SAT to SUBSET-SUM (34.5.5, pp. 1013--1017). |
| Sep 27 | Reducing CLIQUE to STABLE-SET and reducing STABLE-SET to VERTEX-COVER (34.5.2, pp. 1006--1007). Class NP (34.2, pp. 981--982). NP-completeness (34.3, p. 986). Cook's theorem (= "SAT is NP-complete"). |
| Oct 4 | The Prim-Dijkstra algorithm (23.2, pp. 570--573 and lecture notes). Abstract data types Stack and Priority Queue. |
| Oct 11 | C code for Prim-Dijkstra, Stack implemented as a linked list, and Priority Queue implemented as a linked list. Reducing 3-CNF-SAT to 3-COLOUR (Problem 34-3, pp. 1019--1020). |
| Oct 18 | Midterm |
| Oct 25 | Priority Queue implemented as a binary heap and as a pairing heap. The notion of amortized analysis (p. 405). |
| Nov 1 | Abstract data type Dictionary. Its implementation by binary search trees (12.1 -- 12.3, pp. 253--264) and splay trees. |
| Nov 8 | Amortized analysis: aggregate analysis (p. 406), the accounting method (p. 410), and the potential method (pp. 412--413; "potential" = "minimum balance requirement"). Incrementing a binary counter (pp. 408--409, 411-412, and 414--415). |
| Nov 15 | |
| Nov 22 | |
| Nov 29 | |
| Dec 9 (Fri) | Final 19:00-22:00 in FG Building, room B030. |