Contents

Course Details

Course Code COMP6741
Course Title Parameterized and Exact Computation
Units of Credit 6
Course Website http://cse.unsw.edu.au/~cs6741
Handbook Entry http://www.handbook.unsw.edu.au/undergraduate/courses/current/COMP6741.html

Course Summary

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.

Course Timetable

The course timetable is available here .

Course Aims

NP-hard problems are often at the core of the most challenging, rewarding, and lucrative computational problems in all areas of science and technology. This course will outline principled ways to approach these problems and will give students a better understanding of when and why NP-hard computational problem can be solved with reasonable resources.

Student Learning Outcomes

After completing the course, students are able to

  • design and analyze non-trivial exponential time algorithms for NP-hard problems using a variety of algorithmic methods
  • prove that certain problems cannot be solved in subexponential time or faster than a specific exponential time bound assuming the (Strong) Exponential Time Hypothesis
  • design parameterized algorithms for NP-hard problems using a variety of algorithmic methods
  • prove that certain parameterizations of problems are not fixed-parameter tractable unless FPT = W[1]
  • rule out polynomial kernels for certain parameterizations of problems
This course contributes to the development of the following graduate capabilities:
Graduate Capability
scholarship: capable of independent and collaborative enquiry
scholarship: rigorous in their analysis, critique, and reflection
scholarship: able to apply their knowledge and skills to solving problems
scholarship: capable of effective communication
scholarship: information literate
scholarship: digitally literate
leadership: enterprising, innovative and creative
leadership: capable of initiating as well as embracing change
leadership: collaborative team workers
professionalism: capable of independent, self-directed practice
professionalism: capable of lifelong learning
global citizens: capable of applying their discipline in local, national and international contexts

Assumed Knowledge

Before commencing this course, students should have basic knowledge in algorithms and complexity, acquired in the course COMP3121 .

Teaching Strategies

  • Lectures ... introduce concepts, show examples, contain a tutorial part that allows students to solve problems in groups and discover concepts on their own
  • Assignments ... allow students to solve significant problems
  • Exams ... open-book midterm and final exam

Teaching Rationale

This course is taught the way it is because interleaving lectures with exercises enhances problem-solving capabilities and fortifies the understanding of newly learned concepts.

The assignments further enhance problem-solving at the students' own pace.

The exams confront students with additional problems and test their understanding of concepts and problem-solving capabilities.

Assessment

There are three assignments. Assignments 1 and 2 are group assignments (2-3 students). Assignment 3 is an individual assignment. Each student receives one mark for Assignment 1, two marks for Assignment 2, and one mark for Assignment 3. The Assignments mark of a student is the average of the top three of these marks.

The midterm and the final exam are open-book.

Assignments 25%
Midterm 25%
Final exam 50%

Academic Honesty and Plagiarism

Plagiarism is defined as using the words or ideas of others and presenting them as your own . UNSW and CSE treat plagiarism as academic misconduct, which means that it carries penalties as severe as being excluded from further study at UNSW. There are several on-line sources to help you understand what plagiarism is and how it is dealt with at UNSW:

Make sure that you read and understand these. Ignorance is not accepted as an excuse for plagiarism.

Course Schedule

Schedule of lecture topics

Week Lectures
1 no lecture
2 Introduction; Dynamic programming
3 Branching algorithms
4 Branching algorithms; Inclusion-Exclusion
5 Inclusion-Exclusion; Basics of Parameterized Complexity
6 Kernelization
7 Parameterized Branching Algorithms
8 Midterm; Parameterized Intractability: the W-hierarchy
9 Parameter Treewidth
10 Iterative Compression
11 Randomized methods and color-coding; Kernel lower bounds
12 Kernel lower bounds; Exponential time hypothesis
13 Exponential time hypothesis; Review of covered topics

Assignment schedule

Assignment announced on submit by feedback on
1 17 August 2016 30 August 2016 09 September 2016
2 31 August 2016 04 October 2016 14 October 2016
3 05 October 2016 19 October 2016 04 November 2016
The midterm is on 14 September 2016 (Week 8).

Resources for Students

Recommended readings

Other useful resources

  • [DF13] Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Springer, 2013.
  • [FG06] Jörg Flum and Martin Grohe. Parameterized Complexity Theory. Springer-Verlag, 2006.
  • [G10] Serge Gaspers. Exponential Time Algorithms: Structures, Measures, and Bounds. VDM Verlag Dr. Mueller, 2010.
  • [N06] Rolf Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.
  • FPT Wiki

Course Evaluation and Development

This course is evaluated each session using the CATEI system.

In the previous offerings of this course, no substantial deficiencies were notes. Students did however make helpful comments on how to improve the course.

Based on their comments, improvements have been made to the course handouts for both black-and-white and color printing, the structure of lectures, and a timeline has been set for feedback on assignments.

Resource created Tuesday 19 July 2016, 10:22:38 AM, last modified Monday 29 August 2016, 06:39:57 PM.


Back to top

COMP6741 16s2 (Parameterized and Exact Computation) is powered by WebCMS3
CRICOS Provider No. 00098G