Algorithms play an important role in computer science and many other science and engineering disciplines. Part of this knowledge has found its way into many science and engineering undergraduate curricula. This advanced algorithms course covers a number of modern topics outside of this basic curriculum.
First, randomization plays an important role in all aspects of algorithms and data structures. This includes basic solutions, such as hash tables and quick sort, that are part of standard data structure libraries used by every programmer. A large part of the internet, from routing tables to massive-scale companies such as Google, are completely reliant on randomization. But even though these ideas are often both simple, very efficient, and highly practical, they are typically not included in a basic course because of lacking prerequisites from discrete probability theory.
Second, a large number of problems are known to be computationally intractable, in the strict sense of being hard for complexity classes like NP or #P. However, this problems still need to be solved. The course presents design and analysis techniques outside of the basic algorithmic undergraduate curriculum for attacking these problems, such as approximation algorithms, exponential time algorithms, parameterized complexity, heuristics and randomized solutions.
Third, many algorithmic solutions must be viewed in the face of massive data encountered today in many application areas, such as google-size databases and information-age science. As instance size grow to mega- and gigabytes, basic data structures and even storage models need to be reconsidered, and new questions arise. Often, randomization plays a central role in the solutions.
Many of these topics are active research questions and the course is at the cutting edge of algorithmic research with rich opportunities for thesis or beginning research work.
