Algorithms
Course arrangements
- Lecture notes
– for lectures 1–12,
plus example sheets
– for lectures 13–23, plus example sheets 4, 5, and 6, and code - Schedule The table below shows what the lecture timetable would have been, were it not for COVID measures. It lists example sheets at the stage at which the material has been covered. You are encouraged to keep to this schedule — you should watch videos, study lecture notes, and work on the example sheets and ticks on the dates below. If you binge-watch the whole set at 1.5× speed in one weekend, you are unlikely to reach the same level of understanding and retention! Please do not run behind the schedule: Cambridge terms are short and intense, and things quickly snowball, and it becomes very hard to catch up.
- Auditing this course The lecturers (who retain the copyright and performance rights over their lectures) have chosen to make their video lectures globally available. If you wish to audit this course, you are welcome to watch the videos and you do not need to request permission. We regret we cannot make the automated coding assessments ('ticks') public.
Videos and example sheets
Here are the videos for each lecture. The Recordings tab has YouTube playlists, including extra videos that go into more depth on some topics.
Lecture 1 22 Jan |
Insertsort (22:18)
|
Lecture 2 25 Jan |
The cost of sorting (17:30)
Mergesort (23:55)
|
Lecture 3 27 Jan |
Heapsort (17:58)
|
Lecture 4 29 Jan |
Sorting algorithms compared (4:28)
|
Example sheet 1
Tick 1 (due 7 Feb) |
|
Lecture 5 1 Feb |
Dynamic programming introduction (11:43)
|
Lecture 6 3 Feb |
Hall allocation (d.p. example) (16:31)
|
Tick 2 (due 21 Feb) | |
Lecture 7 5 Feb |
Algorithm design strategies (5:12)
|
Lecture 8 8 Feb |
|
Example sheet 2 | |
Lecture 9 10 Feb |
Binary search trees (38:50)
|
Lecture 10 12 Feb |
2-3-4 trees (15:58)
Red-black trees (28:35)
|
Lecture 11 15 Feb |
B-trees (38:05)
Hash tables (33:24)
|
Lecture 12 17 Feb |
|
Example sheet 3 | |
Lecture 13 19 Feb |
5, 5.1 Graphs (14:27)
graphs
5.2 Depth-first search (11:37)
5.3 Breadth-first search (6:43)
|
Lecture 14 22 Feb |
5.4 Dikstra's algorithm (15:25) plus proof (24:01)
|
Lecture 15 24 Feb |
5.5 Algorithms and proofs (9:29)
5.6 Bellman-Ford (12:13)
|
Lecture 16 26 Feb |
5.7 Dynamic programming (13:06)
5.8 Johnson's algorithm (13:43)
|
Example sheet 4 | |
Lecture 17 1 Mar |
6.1 Flow networks (9:31)
subgraphs
6.2 Ford-Fulkerson algorithm (21:55)
|
Lecture 18 3 Mar |
6.3 Max-flow min-cut theorem (19:38)
Typos on pages 35 and 36—lecture notes have been updated—thanks to M.Macko 6.4 Matchings (11:01)
|
Lecture 19 5 Mar |
6.7 Topological sort (14:16)
|
Example sheet 5
Tick 3 (due 14 March) |
|
Lecture 20 8 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 10 Mar |
7.5 Three priority queues (18:26)
7.6, 7.7 Fibonacci heap (18:13)
advdata with fibheap.py, or
FibHeap.java
Typo on page 65—lecture notes have been updated—thanks to A.Pesenti |
Lecture 22 12 Mar |
|
Lecture 23 15 Mar |
7.9 Disjoint sets (18:07)
|
Example sheet 6 | |
Lecture 24 TBA |
Director's cut: further topics
|