Course syllabus

The course for 2019 is in three independent parts. The course coordinator is Mark C. Wilson. Please contact him for all questions relating to the course in general. For specific questions about lectures and assignments by a given lecturer, please contact that lecturer directly.

The first 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.

The second part is taught by Michael J. Dinneen. We will cover basic combinatorial algorithms (how to enumerate objects and rank/hash them). We then study 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 third part is taught by Simone Linz.  We further study fixed-parameter tractable (FPT) techniques and approximation algorithms.

There will be one assignment (a mixture of written work and programming) by each lecturer, each worth 13.33% of the course marks. The final exam is worth 60.01%.

Class Representative: Alexander Swain aswa408@aucklanduni.ac.nz

Lectures: