Algorithm design and analysis is a fundamental and important part of computer science. This course introduces students to advanced techniques for the design and analysis of algorithms and explores some applications of the resulting algorithms.
The first part of this course studies advanced algorithms for families of graphs of bounded combinatorial width (treewidth, pathwidth, treedepth, branchwidth), often formulated as linear-time dynamic programs, for many popular NP-hard problems. The second part covers parameterised and approximation algorithms for several classical NP-hard optimisation problems. If time allows, we will also look at applications from computational biology. No knowledge of biology is required!
The material taught in this course is particularly relevant for all students wishing to pursue further postgraduate studies in theoretical computer science or discrete mathematics and for those who are planning for a career that involves efficient programming and/or problem-solving.