## Algorithms

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

 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. 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. 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. Example sheet 4: Binary search trees. Red-black trees. B-trees. Hash tables. Priority queues and heaps. Example sheet 5: Advanced data structures. Fibonacci heaps. Graph representations. Example sheet 6: Disjoint sets. Graph algorithms. Graph representations. Breadth-first and depth first search. Topological sort. Minimum spanning tree. Kruskal and Prim algorithms. Example sheet 7: Single-source shortest paths: Bellman-Ford and Dijkstra algorithms. All-pairs shortest paths: matrix multiplication and Johnson’s algorithms. 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.