COMP36111 Advanced Algorithms 1 syllabus 2019-2020
This course unit has two objectives. The first is to introduce the student to a range of fundamental, non-trivial algorthms, and to the techniques required to analyse their correctness and running-time. The second is to present a conceptual framework for analysing the intrinsic complexity of computational problems, which abstracts away from details of particular algorithms.
Topics considered include finding components in graphs, computing optimum flows in networks, matching in bi-partite graphs, solving the stable marriage problem, and string matching in text.
The second part considers the more general problem of analysing the intrinsic complexity of computational problems. Topics considered include the Turing model of computation and its associated complexity hierarchy, hardness and reductions, and both upper and lower complexity-bounds for various well-known problems from logic and graph theory.
Undirected graphs: union find and the inverse Ackerman function
Flow optimization and matching
The stable marriage problem and the Gale-Shapley algorithm
String matching and the KMP algorithm.
Some problems from logic: upper bounds
Hardness and reductions: Cook's theorem
Some problems from graph theory: 3-colouring, Hamiltonian and Eulerian circuits, the TSP
Some problems from logic: lower bounds
Savitch's theorem and the Immerman-Szelepcsényi theorem
How to pass the exam.
36111-cwk1-F-Formulating Arguments; Out of 20; Deadline End Wk II Oct 4th 14:00
36111-cwk2-S-exercisesA; Out of 20; Deadline End Wk IV Oct 18th 14:00
36111-cwk3-S-exercisesB; Out of 20; Deadline End Wk IX Nov 22nd 14:00
36111-cwk1-F-Formulating Arguments; Out of 20; Deadline End Wk II Oct 4th 14:00 36111-cwk2-S-exercisesA; Out of 20; Deadline End Wk IV Oct 18th 14:00 36111-cwk3-S-exercisesB; Out of 20; Deadline End Wk IX Nov 22nd 14:00
22 lecture course but some lectures will be cancelled to provide time for assessed exercises.
Feedback methodsTwo pieces of assessed coursework during the course unit.
- Lectures (22 hours)
- Analytical skills
- Problem solving
|Programme outcome||Unit learning outcomes||Assessment|
|A2 B1 B2 B3 D6||Be able to develop, and reason about the correctness and performance of, algorithms for string searching and for calculating over graphs.|
|A2 B1 B2 B3 C5 D6||Understand the distinction between linear and polynomial-time tasks, and those with exponential-time algorithms; tractable and intractable tasks.|
|A2 B1 B2 B3 C5 D6||Understand the general notion of complexity classes, P and NP, completeness and hardness, and the relationships between classes by reduction.|
|A2 B1 B2 B3 C5 D6||You will also have seen how to show tasks are NP-complete and know a range of NP-complete problems.|
|A2 B1 B2 B3 C5 D6||You will understand the hierarchy of complexity classes and know some of the key theorems concerning these classes.|
|Introduction to the theory of computation (3rd edition)||Sipser, Michael||9781133187813||Cengage Learning||2013||✔|
|Algorithm design and applications||Goodrich, Michael T. and Roberto Tamassia||9781118335918||Wiley||2014||✔|
Course unit materials
Links to course unit teaching materials can be found on the School of Computer Science website for current students.