COMPSCI 720: Advanced Design and Analysis of Algorithms

The course for 2018 is in two independent parts.

The first part is taught by Michael J. Dinneen. We will initially cover basic combinatorial algorithms (how to enumerate objects and rank/hash them). We then study fixed-parameter tractable (FPT) techniques for coping with NP-hard problems such as linear-time dynamic programs for graphs of bounded treewidth. Finally we cover some advanced algorithm topics on approximation and local search.

The second part is taught by Mark C. Wilson. We will cover techniques for counting objects without enumerating them. This involves recurrence relations, generating functions, and symbolic sums. These tools have many uses in analysis of algorithms, and in application areas such as statistical physics. We will use the open source software SAGE for computations.

There will be 2 assignments (a mixture of written work and programming) by each lecturer, each worth 10% of the course marks. The final exam is worth 60%.

Class Rep: William Asiata <wasi131@aucklanduni.ac.nz>

Lectures: