Contemporary Approaches to Algorithm Design
In this course, we will study the main contemporary approaches to the design of algorithms. These approaches include various analysis techniques, design methods and computation models. The students will learn how to apply algorithm engineering (which aims to bridge the gap between theory and practice), use multi-level memory hierarchy and design cache-oblivious algorithms, speed up exact exponential algorithms (e.g., by branching techniques), design parameterized algorithms (algorithms that take advantage of specific inputs bound to a parameter), design approximation algorithms (fast algorithms that return approximate
results of good quality), design randomized algorithms (fast algorithms that return uncertain results of good confidence), design quantum algorithms (algorithms that integrate quantum reality into computation). Finally, we will describe the concept of the realistic (as opposed to the worst-case) complexity of algorithms and computational problems.