COMP6741: Parameterized and Exact Computation

Prerequisites:

God I love this course. I found the course content really interesting, and the content was taught well. It follows on heavily from COMP4141, starting off with NP-reductions before moving more into parameterised algorithms. Being familiar with reductions will help (since the course has so many), and having some experience with formal proof methods will help as well. A really nice course if you're interested in theoretical computer science, and more so if you're interested in complexity theory and parameterised algorithms. The lectures are pre-recorded, and the lecture timeslots are instead consultations, where Serge went over the exercises and assignment solutions, which really helped with understanding the course.
Content-wise, the course begins talking about complexity in general, and NP-hardness reductions, before moving onto parameterised complexity classes. The remainder of the course mostly focuses on techniques to find FPT algorithms, and other parameterised classes, as well as establishing several examples to base reductions from, and a lot of theory behind the techniques. It also discusses different parameters, and how they can affect tractability. The course ends discussing heuristics, and using local searches as a method to solve NP-complete problems efficiently.

2x 2hr Lectures

4/5

Yes, lectures recorded, and lecture timeslots converted into recorded consultations.

A/Prof. Serge Gaspers

Lecture slides, exercises with solutions, and some more condensed lecture notes all available online.

5/5

2020 T3

100 HD