Course description:
When faced with an NP-hard problem, one has little hope of obtaining a deterministic algorithm that completes the correct answer for any instance with a guaranteed worst-case polynomial-time running time. One approach is to sacrifice determinism (using randomized algorithms), worst-case bounds (using average-case analysis), or exact solutions (using approximation algorithms). Fixed-parameter algorithms are deterministic, exact algorithms with worst-case bounds. The exponential blow-up in running time is confined to one or more parameters of the problem that, in practice, may be sufficiently small as to render the algorithm practical. The field of exact algorithms explores reducing the size of the exponent.
In this course, we will explore paradigms used to design such algorithms, and touch briefly on related complexity measures and extensions to counting, enumeration, and approximation.
Required background:
Students are expected to be familiar with algorithm paradigms (greedy algorithms, divide-and-conquer, dynamic programming, search tree), algorithm analysis and asymptotic notation, models of computation, reductions, graph theory basics, and approximation algorithms. In addition, comfort with common problems (e.g. vertex cover, independent set, clique, dominating set) will be assumed.
Course structure:
The course will be structured around the presentation and discussion of a sequence of papers; the class will meet on Thursdays, 1:00-3:50 in M3-3103.
During the first three weeks, I will present a broad overview of most of the well-establish paradigms in the area. Students will be expected to complete the accompanying exercises.
Each student in the class will be responsible for running an approximately 50-minute seminar.
The last few weeks will consist of short (15-20 minute) presentations of course projects.
The relative weightings of the components are listed below:
Seminar (30%)
Project (50%)
Class participation (20%):
More information can be found at the course D2L site.