Computer Science 6789:
Parameterized Complexity Analysis: Foundations and Applications
(Winter 2014)
http://www.cs.mun.ca/~harold/Courses/CS6789
Lecture Outline (Tentative)
- Review: Classical computational complexity analysis (3 lectures)
(algorithms, worst-case time asymptotic time complexity,
polynomial time, polynomial-time many-one
reducibility, NP-completeness)
- Parameterized complexity theory (5 lectures)
(parameterized problems, fixed-parameter tractability,
parameterized reducibility, parameterized classes)
- Illustrations of parameterized complexity analysis (12 lectures)
(In-depth of analyses of 4-5 selected problems (2-4 lectures
apiece))
- Student presentations (3 lectures)
Evaluation Scheme
| Assignments (3) |
30% |
|
| Class Exams (2) |
30% |
Thursday, February 6
Thursday, March 6 |
| Student Presentations (2) |
10% |
|
| Course project |
30% |
TBA |
- Marks for missed assignments (with appropriate documentation) will be averaged over
the remaining assignments.
- Students must pass both in-class exam to pass the course.
Assignment Deadlines (Tentative)
| Assignment | Given | Due |
| Assignment #1 | Dec 19, 2013 | Jan 30 |
| Assignment #2 | Jan 30 | Feb 27 |
| Assignment #3 | Feb 27 | Mar 20 |
Recommended Readings
- Downey, R. (2012) "A Basic Parameterized Complexity Primer." In H.L.
Bodlaender, R.G. Downey, F.V. Fomin, and D. Marx (eds.) The
Multivariate Algorithmic Revolution and Beyond. Lecture Notes in
Computer Science no. 7370. Springer. 91-128.
- Downey, R. and Fellows, M.R. (1999) Parameterized Complexity. Springer.
- Niedermeier, R. (2006) Invitation to Fixed-parameter Algorithms.
Oxford University Press.
- Sloper, C. and Telle, J.A. (2008) "An overview of techniques for designing
parameterized algorithms." Computer Journal, 51(2), 122-136.
Created: December 11, 2013
Last Modified: January 30, 2013