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.
