View on GitHub

COMP6741

Course webpage – Algorithms for Intractable Problems

Welcome to the course webpage for UNSW’s COMP6741!

Course description

The course focuses on algorithms for solving intractable computational problems, so-called NP-hard problems. Ideally, one would want to design algorithms that solve each instance optimally and in polynomial time. But since no polynomial time algorithm is known for any NP-hard problem, we will relax these requirements and design algorithms that either do not solve the problem optimally, that only solve a subset of instances, or whose worst-case running time is super-polynomial in the input size or some other parameter of the input. Among algorithms that do not provide optimal solutions, we discuss heuristics and approximation algorithms. Heuristics have no optimality guarantees but tend to work well in practice. Approximation algorithms give additional guarantees of the quality of computed solution as compared to the optimal solution.

Among algorithms that only solve a subset of instances, we discuss graph classes where NP-hard graph problems often become polynomial-time solvable when the input is restricted to such graphs.

Among algorithms that do not run in polynomial time, we discuss exponential-time algorithms and parameterized algorithms. In exponential-time algorithms we see algorithmic techniques to solve NP-hard problems provably faster than brute-force in the worst case. In parameterized algorithms, a parameter k is associated with each instance and the goal is to design algorithms whose worst-case running time is fast whenever k is small. We will also see lower bounds for problems and how to rule out certain running times under various complexity assumptions.

In addition to deterministic algorithms, we discuss speed-ups if we have access to randomised algorithms or quantum algorithms.

News

Resources

for enroled students

additional textbooks

Course schedule

Week Topics
1 Introduction; NP-completeness
2 Kernelization; approximation algorithms; (integer) linear programming
3 Kernelization; basics of Parameterized Complexity
4 Parameterized intractability; branching algorithms
5 Branching algorithms; measure & conquer
6 -
7 Randomized algorithms; treewidth
8 Treewidth; exponential time hypothesis
9 Quantum algorithms; heuristics and local search
10 Group assignment presentations; review

Frequently Asked Questions

  1. Is COMP6741 a WAM-booster?

    Based on past statistics, students with a current weighted average mark (WAM) in the high distinction (HD) range typically achieve a course mark that is higher than their current WAM. Students in the distinction (DN) range typically achieve a course mark in line with their WAM. And other students typically achieve a course mark that is lower than their WAM.

  2. What are the prerequisites?

    You should have done COMP3121/9101 or the extended version of that course, COMP3821/9801. The prerequisite knowledge is further detailed in this pdf.

  3. How is the course taught?

    The course is taught in a flipped-classroom style. Lectures are pre-recorded. During the lecture time slots, we solve tutorial-style exercise sheets, review lecture material that is useful to solve these exercises, explore various approaches to solve (or fail to solve) the exercises, and answer questions about the lecture material.

  4. What are the student expectations?

    Before each meeting (2 times per week), it is expected that you watch the associated pre-recorded lecture (if notations or terms are unclear, consult the glossary, find resources online that you can share with other students in the forum, and/or ask/answer questions in the forum) and that you attempt the associated exercise sheet (you may not be able to solve all exercises, but it is important to attempt them and think about them in depth, so as to pinpoint the difficulties).

    During the meeting, we typically answer questions you may have about the lecture, discuss the exercise sheets and provide either hints or (partial) solutions, and clarify assignment questions. We may also discuss the solution to assignments that you submitted in previous weeks.

    Assignments assume that you are up-to-date with all lectures and attempted all exercise sheets yourself.

  5. How is the course assessed?

    In 2024, there are 3 assignments and 1 final exam. The assignment mark is worth 50% of the overall mark, composed of two individual assignments (15% each) and one group assignment (20%). The final exam is worth 50% and is run on Inspera. Bonus marks are possible in case of exceptional performance.

  6. When can I take COMP6741?

    COMP6741 runs in 2024 term 1. In future years, it is planned that the course will run in term 1, but it might not be offered every year.

Hall of fame

Show

The course has attracted extremely smart and dedicated students over the years.

The best performers have demonstrated exceptional problem-solving abilities, a mastery of advanced algorithmic techniques for challenging computational problems, and a deep understanding of the analysis of algorithms and the complexity of computational problems.

The top 3 students in each offering are listed below.

YearTop students
20231. Anders Mah
2. Redmond Mobbs
2. Zixu He
20221. Angus Ritossa
2. Charran Kethees
3. Jeffrey Yang
3. Sean Zammit
20201. Ian Dunkerley
1. Ethan Brown
3. Daniel Woolnough
20191. Madeleine Kyng
2. Louis Cheung
3. Andrew Ross
20181. Brittany Evat
2. Joshua Lau
3. Adrian Goldwaser
20171. David Coates
2. Suganya Suresh
3. Felix Abrahamsson
20161. Mohammad Huda
2. Andrew Semler
3. Michael Chen
20151. Ray Li
1. Oliver Fisher
3. Magnus Hagmar
20141. Mitchell Ward
2. Alexis Shaw
2. Ben Edser