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).
  • 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"