skip to primary navigationskip to content

Department of Computer Science and Technology

Algorithms

Course pages 2020–21

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
Mergesort (23:55)
Lecture 3
27 Jan
Heapsort (17:58)
Lecture 4
29 Jan
Example sheet 1
Tick 1 (due 7 Feb)
Lecture 5
1 Feb
Lecture 6
3 Feb
Tick 2 (due 21 Feb)
Lecture 7
5 Feb
Lecture 8
8 Feb
Example sheet 2
Lecture 9
10 Feb
Lecture 10
12 Feb
2-3-4 trees (15:58)
Lecture 11
15 Feb
B-trees (38:05)
Hash tables (33:24)
Lecture 12
17 Feb
Example sheet 3
Lecture 13
19 Feb
Lecture 14
22 Feb
5.4 Dikstra's algorithm (15:25) plus proof (24:01)
Lecture 15
24 Feb
Lecture 16
26 Feb
Example sheet 4
Lecture 17
1 Mar
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
Lecture 19
5 Mar
Example sheet 5
Tick 3 (due 14 March)
Lecture 20
8 Mar
Lecture 21
10 Mar
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
Example sheet 6
Lecture 24
TBA
Director's cut: further topics