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.
Please note that the University reserves the right to vary student fees in line with relevant legislation. This fee information is provided as a guide and more specific information about fees, including fee policy, can be found on the fee website.
For advice about fees for courses with a fee displayed as "Not Applicable", including some Work Experience and UNSW Canberra at ADFA courses, please contact the relevant Faculty.
Where a Commonwealth Supported Students fee is displayed, it does not guarantee such places are available.