Algorithms — Michaelmas Term 2023

Role: Tutor
Course: Algorithms (Year 1, MEng Computer Science)
Term: Autumn Term 2023
Format: Six fortnightly tutorials (pairs)

Topics covered

1. Asymptotic analysis — O, Ω, Θ notation; recurrence relations; Master theorem
2. Sorting — mergesort, quicksort, heapsort; lower bounds for comparison sorting
3. Graph algorithms — BFS, DFS, Dijkstra, Bellman-Ford, Kruskal, Prim
4. Dynamic programming — memoisation, tabulation; classic problems (LCS, knapsack, edit distance)
5. Greedy algorithms — interval scheduling, Huffman coding; exchange argument proofs
6. Complexity — P, NP, NP-completeness; reductions; Cook-Levin theorem

Assessment

Students submitted written problem sheets before each tutorial. I marked these and used them as the basis for discussion. Final examination is set and marked by the course lecturer.