COMP6741 Parameterized and Exact Computation  
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.