skip to primary navigation skip to content

Search site

Study at Cambridge

Undergraduate

Graduate

About the University

Research at Cambridge

Department of Computer Science and Technology

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

Introducing Algorithms: three hard problems (21:42)

Insertsort (22:18)

Asymptotic complexity, big-O notation, big-Theta, big-Omega, small-o, small-omega (19:04)

Lecture 2
25 Jan

The cost of sorting (17:30)

Selectsort, binary insertsort, bubblesort (10:48)

Mergesort (23:55)

Lecture 3
27 Jan

Heapsort (17:58)

The heap is amazing! Here is one more reason why: the asymptotic cost to build one (19:19)

Lecture 4
29 Jan

Quicksort, median, order statistics, stability (25:58)

How to sort in linear time: counting sort, bucket sort, radix sort (21:21)

Sorting algorithms compared (4:28)

Example sheet 1
Tick 1 (due 7 Feb)

Lecture 5
1 Feb

Dynamic programming introduction (11:43)

Rod cutting (dynamic programming example) (22:22)

Find optimal order for a chain of matrix multiplications (d.p. example) (22:55)

Lecture 6
3 Feb

Longest common subsequence (d.p. example) (18:45)

Hall allocation (d.p. example) (16:31)

Tick 2 (due 21 Feb)

Lecture 7
5 Feb

Greedy solution to hall allocation problem (cheaper!) (27:41)

Huffman compression (another greedy algorithm) (36:16)

Algorithm design strategies (5:12)

Lecture 8
8 Feb

What can the Sinclair ZX Spectrum teach you about data structures, memory, and pointers? (20:14)

List, tree, stack, queue, dictionary (elementary data structures) (22:50)

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

Priority queues and binomial heaps (32:02

Three secrets for doing well in your university exams (18:21)

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.5, 6.6 Prim's and Kruskal's algorithms (14:29)

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

7.8 Amortized analysis of the Fibonacci heap (29:35)

Lecture 23
15 Mar

7.9 Disjoint sets (18:07)

Example sheet 6

Lecture 24
TBA

Director's cut: further topics

[画像:University of Cambridge]

Study at Cambridge

About the University

Research at Cambridge