Course

Parameterized and Exact Computation - COMP6741

Faculty: Faculty of Engineering

School: School of Computer Science and Engineering

Course Outline: http://www.cse.unsw.edu.au/~cs6741

Campus: Sydney

Career: Postgraduate

Units of Credit: 6

EFTSL: 0.12500 (more info)

Indicative Contact Hours per Week: 3

Enrolment Requirements:

Prerequisite: COMP9101 or COMP9801.

CSS Contribution Charge: 2 (more info)

Tuition Fee: See Tuition Fee Schedule

Further Information: See Class Timetable

View course information for previous years.

Description

The course focuses on algorithms for exactly solving NP-hard computational problems. Since no polynomial time algorithm is known for any of these problems, the running time of the algorithms will have a super-polynomial dependence on the input size or some other parameter of the input.


The first part presents algorithmic techniques to solve NP-hard problems provably faster than brute-force in the worst case, such as branching algorithms, dynamic programming across subsets, inclusion-exclusion, local search, and measure & conquer. We will also see lower bounds for algorithms and how to rule out certain running times assuming the (Strong) Exponential Time Hypothesis.


Whereas the first part presents "default" algorithms that one would use without knowing much about the instances one is about to solve, the second part acknowledges that the complexity of an instance does not only depend on its size n. A parameter k is associated with each instance and the parameterized complexity framework aims at designing fixed-parameter algorithms whose running times are f(k)*poly(n) for a computable function f. This gives efficient algorithms for small values of the parameter obtained via techniques such as branching, colour coding, iterative compression, and kernelization (preprocessing). We will also see problems that are not fixed-parameter tractable and not kernelizable to polynomial kernels subject to complexity-theoretic assumptions.
UNSW Computing

Study Levels

UNSW Quick Links