To demonstrate how the study of algorithmics has been applied in a number of different domains. To introduce formal concepts of measures of complexity and algorithms analysis. To introduce fundamental methods in data structures and algorithms design. To make students aware of computationally hard problems and possible ways of coping with them.

(LO1) At the conclusion of the module students should have an appreciation of the diversity of computational fields to which algorithmics has made significant contributions.

(LO2) At the conclusion of the module students should  have fluency in using basic data structures (queues, stacks, trees, graphs, etc) in conjunction with classical algorithmic problems (searching, sorting, graph algorithms, security issues) and be aware of basic number theory applications, etc.

(LO3) At the conclusion of the module students should  be familiar with formal theories providing evidence that many important computational problems are inherently intractable, e.g., NP-completeness.

1) 2 weeks: Introduction to algorithms, big-Oh notation, divide-and-conquer algorithms, master method
2) 1 week: linked lists, binary search trees, heaps, heapsort
3) 1 week: sorting algorithms (counting inversions, quick sort, radix sort, counting sort)
4) 2 weeks: greedy algorithms, dynamic programming, memoisation, Fibonacci numbers
5) 1 week: graph algorithms, shortest paths
6) 1 week: maximum flows (Ford Fulkerson algorithm), bipartite matching
7) 1 week: NP-completeness (complexity classes P and NP, search-to-decision reductions, example of vertex-cover to clique reduction)
8) 1 week: number-theoretic algorithms (Euclid’s GCD, extended Euclid’s algorithm, RSA)
9) 1 week: Possible advanced topics: Further complexity theory (BPP, circuits, query and communication complexity), fun with algorithms (hardness of speedrunning video games, complexity of algorithms for Rubik’s cube and related puzzles, etc.), randomised and approximation algorithms.

Teaching Method 1 - Lecture
Description:
Teaching Method 2 - Tutorial
Description:

Standard on-campus delivery
Teaching Method 1 - Lecture
Description: Mix of on-campus/on-line synchronous/asynchronous sessions
Teaching Method 2 - Tutorial
Description: On-campus synchronous sessions