Algorithms 2
Course arrangements
- Lecture notes: alg2.pdf
(This course is a continuation of Algorithms 1, which is why the notes for Algorithms 2 start at start at Section 5, and why the lectures start at Lecture 13.) - Recordings The pre-recorded videos, listed below, cover all examinable material. You can watch them in your own time, but you are encouraged to keep to the schedule. The Recordings tab has YouTube playlists.
- Live in-person sessions There is one live in-person session each week, for discussions and digressions and for sharing the ‘spirit’ of the course. This is off syllabus material, and there will be no recordings. The sessions are in New Museum Site, Lecture Theatre A, 10–11am.
Schedule
| 18 Feb, 10am | Live in-person session: introduction
[slides]
Challenge 1: fast maximum |
| Lecture 13 18 Feb |
5, 5.1 Graphs (14:27)
graphs
5.2 Depth-first search (11:37)
5.3 Breadth-first search (6:43)
|
| Lecture 14 21 Feb |
5.4 Dikstra's algorithm (15:25) plus proof (24:01)
|
| Lecture 15 23 Feb |
5.5 Algorithms and proofs (9:29)
5.6 Bellman-Ford (12:13)
|
| Lecture 16 25 Feb |
5.7 Dynamic programming (13:06)
5.8 Johnson's algorithm (13:43)
|
| 25 Feb, 10am | Live in-person session: “not even wrong” [slides] Challenge 2: finding order (for discussion on 11 March) |
| Example sheet 4 including optional tick ex4-bfs | |
| Lecture 17 28 Feb |
6.1 Flow networks (9:31)
subgraphs
6.2 Ford-Fulkerson algorithm (21:55)
|
| Lecture 18 2 Mar |
6.3 Max-flow min-cut theorem (19:38)
6.4 Matchings (11:01)
|
| Lecture 19 4 Mar |
6.7 Topological sort (14:16)
|
| 4 Mar, 10am | Live in-person session: max-flow min-cut and Lagrangian optimization [slides] |
| Example sheet 5, plus optional tick ex5-match
Tick 3 (due 12 March) |
|
| Lecture 20 7 Mar |
7.1 Aggregate analysis (8:56)
7.2 Amortization: introduction (10:41)
7.3 Amortization: definition (10:59)
7.4 Potential functions (14:17)
|
| Lecture 21 9 Mar |
7.5 Three priority queues (18:26)
7.6, 7.7 Fibonacci heap (18:13)
advdata with fibheap.py, or
FibHeap.java
|
| Lecture 22 11 Mar |
|
| 11 Mar, 10am | Live in-person session: GANs and other optimizations [slides]
Tunan Shi's solution to Challenge 2 using simulated annealing |
| Lecture 23 14 Mar |
7.9 Disjoint sets (18:07)
|
| Example sheet 6 | |
| 16 Mar, 10am | Live in-person session: geometry algorithms [notes] |