Algorithms 2
This course is a continuation of Algorithms 1 (which is why these notes start at Section 5, and why the lectures start at Lecture 13).Lecture notes
- Full notes as printed
- Corrections
Announcements, Q&A, tick submission
— MoodleSchedule
5. Graphs and path finding graphs.ipynb | |
Lecture 13 [slides] |
5, 5.1 Graphs (14:27)
5.2 Depth-first search (11:37)
5.3 Breadth-first search (6:43)
|
Optional tick: bfs-all from ex4.q6
|
|
Lecture 14 [slides] |
5.4 Dikstra's algorithm (15:25) plus proof (24:01)
|
Lecture 15 [slides] |
5.5 Algorithms and proofs (9:29)
5.6 Bellman-Ford (12:13)
|
Optional challenge: chatgpt-bfs
Optional tick: bf-cycle from ex4.q19
|
|
Lecture 16 [slides] |
5.7 Dynamic programming (13:06)
5.8 Johnson's algorithm (13:43)
|
Example sheet 4 [pdf] | |
6. Graphs and subgraphs subgraphs.ipynb | |
Lecture 17 [slides] |
6.1 Flow networks (9:31)
6.2 Ford-Fulkerson algorithm (21:55)
|
Compulsory tick: max-flow (due 12noon on 13 March)
|
|
Lecture 18 [slides] |
6.3 Max-flow min-cut theorem (19:38)
|
Lecture 19 [slides] |
6.4 Matchings (11:01)
|
Lecture 20 [slides] |
6.7 Topological sort (14:16)
|
Optional challenge: rank-sim
Example sheet 5 [pdf] |
|
7. Advanced data structures | |
Lecture 20 ctd.
[slides] |
7.1 Aggregate analysis (8:56)
7.2 Amortization: introduction (10:41)
7.3 Amortization: definition (10:59)
|
Lecture 21 [slides] |
7.4 Potential functions (14:17)
|
Lecture 22 [slides] |
7.5 Three priority queues (18:26)
7.6, 7.7 Fibonacci heap (18:13)
|
Optional tick: fib-heap
|
|
Lecture 23 [slides] |
7.8 (continued)
7.9 Disjoint sets (18:07)
|
Optional tick: dis-set from ex6.q12
Example sheet 6 [pdf]
|
|
Further topics | |
Lecture 24 [slides] |
X. Optimization algorithms
|