Ashmit Rao

Program costs: time and space. Worst case and average case analysis. Asymptotics and "big O" notation. Polynomial and exponential growth. Asymptotic estimates of costs for simple algorithms. Use of induction and generating functions.

Algorithm design strategies: top down design, divide and conquer. Application to sorting and searching and to matrix algorithms. Solution of relevant recurrence relations.

Data structures and their representations: arrays, lists, stacks, queues, trees, heaps, priority queues, graphs.

Introduction to discrete optimisation algorithms: dynamic programming, greedy algorithms, shortest path problems.

Graph algorithms: examples of depth-first and breadth-first search algorithms. Topological sorting, connected components.