Algorithms

Example sheets that I have used to teach algorithms in addition to the guide for supervisors provided by the computer laboratory.

Download Example sheet 1: Sorting. Review of complexity and O-notation. Trivial sorting algorithms of quadratic complexity. Review of merge sort and quicksort, understanding their memory behaviour on statically allocated arrays. Heapsort.
Download Example sheet 2: Stability. Other sorting methods including sorting in linear time. Median and order statistics. Strategies for algorithm design. Dynamic programming. Divide and conquer paradigm.
Download Example sheet 3: Divide and conquer, greedy algorithms and other useful paradigms. Data structures. Primitive data structures. Abstract data types. Pointers, stacks, queues, lists, trees. Binary search trees.
Download Example sheet 4: Binary search trees. Red-black trees. B-trees. Hash tables. Priority queues and heaps.
Download Example sheet 5: Advanced data structures. Fibonacci heaps. Graph representations.
Download Example sheet 6: Disjoint sets. Graph algorithms. Graph representations. Breadth-first and depth first search. Topological sort. Minimum spanning tree. Kruskal and Prim algorithms.
Download Example sheet 7: Single-source shortest paths: Bellman-Ford and Dijkstra algorithms. All-pairs shortest paths: matrix multiplication and Johnson’s algorithms.
Download Example sheet 8: Maximum flow: Ford-Fulkerson method, Max-Flow Min-Cut Theorem. Matchings in bipartite graphs. Geometric algorithms. Intersection of segments. Convex hull: Graham’s scan, Jarvis’s march.