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 NPhard computational problems. Since no polynomial time algorithm is known for any of these problems, the running time of the algorithms will have a superpolynomial dependence on the input size or some other parameter of the input.
The first part presents algorithmic techniques to solve NPhard problems provably faster than bruteforce in the worst case, such as branching algorithms, dynamic programming across subsets, inclusionexclusion, 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 fixedparameter 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 fixedparameter tractable and not kernelizable to polynomial kernels subject to complexitytheoretic assumptions.
The course timetable is available here .
NPhard 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 NPhard 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, selfdirected 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 problemsolving capabilities and fortifies the understanding of newly learned concepts.
The assignments further enhance problemsolving at the students' own pace.
The exams confront students with additional problems and test their understanding of concepts and problemsolving capabilities.There are three assignments. Assignments 1 and 2 are group assignments (23 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 openbook.
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 online 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 
no lecture

2  Introduction; Dynamic programming 
3  Branching algorithms 
4  Branching algorithms; InclusionExclusion 
5  InclusionExclusion; Basics of Parameterized Complexity 
6  Kernelization 
7  Parameterized Branching Algorithms 
8  Midterm; Parameterized Intractability: the Whierarchy 
9  Parameter Treewidth 
10  Iterative Compression 
11  Randomized methods and colorcoding; 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 
Recommended readings
Other useful resources
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 blackandwhite 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.