Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

Exact Exponential Algorithms

MSc Lecture - Summer 2021

Due to the COVID-19 pandemic, this course will be offered online. Thus, it is important that all participants enroll via our Moodle page. The BBB-Link for lectures and exercises will be posted there. Note that aside from Moodle-enrollment you have to also register with the Studienreferat.

Description

Especially in the past year we have learned the meaning of exponential growth. From the perspective of efficient algorithmic design we therefore usually only consider polynomial running times to be acceptable. Problems for which we are unable to come up with polynomial time algorithms, we turn to the concept of NP-hardness - our favorite excuse to use heuristics that sacrifice solution quality or general applicability for efficiency. Our Master's courses usually teach you many sophisticated techniques for this scenario.

This course does the opposite and gives up on polynomial running time to guarantee exact solutions. We will mostly follow the book Exact Exponential Algorithms by Fedor V. Fomin and Dieter Kratsch (Springer 2010), extended by some current research trends. As the preface of this book puts it so bluntly: "This book is about bad algorithms.", so: This course is about bad algorithms.

Many people in the research area of exact exponential algorithms use the bolt statement attributed to Alan Perlis (famous first ever Turing Award winner):
"For every polynomial-time algorithm you have, there is an exponential algorithm that I would rather run." 
While I cannot for sure dismiss the existence of such magically fast exponential algorithms, this is not the intended theme here.

A much better reason to choose exact algorithms as Master's course topic is the skills it trains. In my experience, there is nothing like exponential dependence to demand care and rigor in the design of algorithms. Even tricks that "only" shrink a worst-case running time from \(2^n\) to \(1.99^n\) are usually very elaborate and insightful. In this course we will learn new sides of all-time favorite methods like branching and dynamic programming, but also encounter new tricks like subset convolution. As counterpart, we discuss the conjecture (S)ETH as our new excuse not to improve exponential algorithms.

At last, even a most extreme fan of efficiency has to admit that checking the true quality of heuristics requires comparison to an exact solution, and that there might even be situations where we can (or even have to) afford to choose quality over efficiency.

Requirements

There are no formal requirements for this course, however a basic understanding of algorithm design and analysis is expected.

Examination

The grade for this course is fully determined by an oral exam of approximately 30 minutes with a time-slot that can be picked individually at the end of the semester.

Dates

Lecture & Exercise slots are Tuesday and Thursday 11:00 all via BBB (link provided via Moodle).

First kick-off lecture on April 15.