[Announcements] | [General Information] | [Additional Material] | [Schedule] |

- [25/02]: Homework 5 was slightly modified to make the definition of Weighted 3-SAT clearer.
- [23/02]: (Last homework!). Homework 6 posted. This homework is optional.
- [29/01]: First class. Welcome!

Instructors: Michail Lampis and Eunjung Kim

Email: michail.lampis AT dauphine.fr and eunjungkim78 AT gmail.com

In this course we cover basic algorithmic techniques for dealing with problem that (probably) cannot be solved in polynomial time. We cover the basic toolbox of exponential-time algorithms, parameterized complexity, as well as the related hardness theories.

More information on the topics to be covered appears in the schedule below (which will be updated during the semester).

The course consists of 10 lectures of 1.5 hours

The final grades for the course will be based on homework assignments. There will be no exam.

Lecture No. | Date | Topic | Notes |
---|---|---|---|

1 | 29/1 | Branching Algorithms | homework 1 |

2 | 1/2 | Iterative Compression | homework 2 |

3 | 2/2 | Kernelization | notes |

4 | 3/2 | Kernelization II | notes |

5 | 4/2 | Color Coding | notes,homework 3 |

6 | 8/2 | Exponential Time Hypothesis | notes, homework 4 |

7 | 12/2 | Parameterized Hardness | notes,homework 5 |

8 | 15/2 | More hardness | Lec. 7 continued |

9 | 18/2 | Structural Parameters/Treewidth/DP | notes |

10 | 19/2 | Local Search | homework 6 |