Overview
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 … For more content click the Read More button below.
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.
Conditions for Enrolment
Prerequisite: COMP3121 or COMP3821.
Course Outline
To access course outline please visit below link (Please note that access to UNSW Canberra course outlines requires VPN):
Fees
Type | Amount |
---|---|
Commonwealth Supported Students (if applicable) | $1191 |
Domestic Students | $5970 |
International Students | $5970 |
Pre-2019 Handbook Editions
Access past handbook editions (2018 and prior)