| 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 |
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.
The course timetable is available here .
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.
After completing the course, students are able to
| 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 |
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.
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% |
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.
Schedule of lecture topics
| Week | Lectures |
| 1 | Introduction; Dynamic programming |
| 2 | Branching algorithms |
| 3 | Branching algorithms; Inclusion-Exclusion |
| 4 | Inclusion-Exclusion; Basics of Parameterized Complexity |
| 5 | Kernelization |
| 6 | Parameterized Branching Algorithms |
| 7 | Midterm; Parameterized Intractability: the W-hierarchy |
| 8 | Parameter Treewidth |
| 9 | Iterative Compression |
| 10 | Randomized methods and color-coding; Kernel lower bounds |
| 11 | Kernel lower bounds; Exponential time hypothesis |
| 12 | Exponential time hypothesis; Review of covered topics |
| 13 | no lecture |
Assignment schedule
| Assignment | announced on | submit by | feedback on |
| 1 | 05 August 2015 | 25 August 2015 | 02 September 2015 |
| 2 | 26 August 2015 | 06 October 2015 | 13 October 2015 |
| 3 | 07 October 2015 | 20 October 2015 | 04 November 2015 |
The midterm is on 09 September 2015 (Week 7).
Recommended readings
Other useful resources
Links
to full texts of eBooks that are available through the UNSW Library.
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, and a timeline has been set for feedback on assignments.
Resource created Thursday 23 July 2015, 07:43:32 PM, last modified Wednesday 29 July 2015, 09:19:32 AM.