# Department of Computer Science and Technology

Course pages 2017–18

# Algorithms

The algorithms course is an introductory course in algorithms. It is 24 lectures, given by Robert Harle (lectures 1-10) and Damon Wischik (11-24).

## Notes

• Lectures 1–10
For the first 10 lectures, the printed notes were an edited version of the original notes produced by Professor Frank Stajano (who developed the course but is on sabbatical this year). The original notes remain available below. Studying from either the edited or original (or both!) is fine for this course.
• Lectures 11–18
Notes as printed [pdf]
Sample code [ipynb]
11–14: routing. 15–16: trees and DAGs. 18–20: flows and matchings.
• Lectures 20–24
Notes as printed [pdf]
17: binomial heap. 20: amortized analysis. 21–22: Fibonacci heap. 23: disjoint sets. 24: geometric algorithms.

## Examples Sheet

• Example sheet for lectures 1–10.
Sheet updated 31/01 to include section on algorithm design at end
• Example sheet 5 [pdf]   for lectures 11–14
• Example sheet 6 [pdf]   for lectures 15–20
• Example sheet 7/8 [pdf]   for lectures 17 & 20–23
• Example sheet 8 [pdf]   for lecture 24

## Moodle

Further resources including annotated slides and help forum may be found on the course Moodle page.

## Corrections

WhenWhereWhat
2018-03-02 Section 5.8 page 23 The theorem should state "Suppose we have a forest f and a cut C such that (i) C contains no edges of f, and (ii) there exists a MST containing f. If we add to f the min-weight edge in C, then the result is still part of a MST." (This is a more general result than the version in the printed handout. This version is needed for the proof that Kruskal's algorithm is correct.)
2018-02-11 Section 5.10 page 27 The description of flame chart should read "if function f calls function g then g is drawn above f"
2018-02-17 Example sheet 5 question 5 Should read "modify `dfs`" rather than "modify `dfs_stack`".
2018-02-18 Example sheet 5 question 10 Should read "uses recursion and memoization to compute h(t)",
2018-02-28 Section 6.2 page 35 Caption should read "a cut of capacity 22"
• © 2018 Department of Computer Science and Technology, University of Cambridge
Information provided by Dr Robert Harle