Latest News

Second homework assignement.

Jan 28, 2021

The second assignment is available now. Due by 4 February.

Change of duedate for 1st homework.

Jan 24, 2021

The first assignment is due by 28 January (midnight).

First homework assignement.

Jan 18, 2021

The first assignment is available now. Due by 25 January.

First class on 11th Jan.

Jan 9, 2021

See you on zoom, the link and password to be shared by email.

Basic information

  • Instructor: Eunjung Kim, Michail Lampis
  • email: michail.lampis AT dauphine.fr and eunjungkim78 AT gmail.com
  • The course will be delivered over 10 lectures of 1.5h each.

Course description

In this course, we cover basic algorithmic techniques for dealing with problem that are computationally intractable, i.e. those unlikely to be solvable in polynomial time under standard computational complexity assumption. We cover the basic toolbox of exponential-time algorithms, parameterized complexity, as well as the related hardness theories.

The course is designed for 2nd year master students. A basic level of understanding in mathematics, algorithms, computational complexity and complexity analysis is assumed.

References

Textbook in exact algorithms.

  • F. V. Fomin and D. Kratsch. Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, 2010: a nice and concise introduction to designing exact algorithms, free download available here.

Textbooks in parameterized complexity.

  • R. Niedermeier. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. Oxford, 2006: Easy to read (and short).
  • R. G. Downey and M. R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013: A-to-Z in parameterized complexity.
  • M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015: an excellent and latest coverage of parameterized algorithms.

Other materials, available online.

  • J. Chen, F. V. Fomin, Y. Liu, S. Lu, and Y. Villanger. Improved algorithms for the feedback vertex set problems. In the prooceedings of 10th international Workshop on Algorithms and Data Structures (WADS 2007), 422-433, 2007.
  • N. Alon, R. Yuster, and U. Zwick. Color-coding. J. ACM, 42(4):844-856, 1995.
  • B. Reed, K. Smith, and A. Vetta. Finding odd cycle transversals. Oper. Res. Lett., 32(4):299-301, 2004.

Policy

  • All the classes will be online. The link is shared by email.
  • Grading will be 100% based on homework assessment. There will no exam.