Texts:
Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge
Vijay Vazirani, Approximation Algorithms, Springer
This is an introduction to two important and active areas of research in algorithms. After taking this class you will have a background that will allow you to start working towards research in these areas or to apply existing results and efficient algorithms to your own areas of research.
Randomization
We will first explore the power of randomization: (how)
does the ability to make random choices help in solving problems?
We'll see problems that are easier to solve using randomization,
we'll see those where randomization gives better solutions, and
we'll see things that just cannot be done without randomization.
We will also learn how to remove randomization from algorithms
in some cases where that is possible.
The topics covered in this part will include the minimum cut problem,
Chernoff and Hoeffding bounds, the coupon collector problem,
maximum cut, derandomization, matchings, random walks,
identity verification, randomized data structures, linear programming
and online algorithms.
Approximation
In the second part of the course, we will focus on intractable optimization
problems and study various approaches to finding approximately optimal
solutions. In other words, we will study approximation algorithms,
efficient algorithms that find almost optimal solutions.
The topics here will include set cover problems,
Steiner trees, traveling salesman problems,
linear programming duality and randomized rounding,
Steiner network problems and metric space embeddings.
Other
The choice of topics is partly open to suggestions.
Prerequisites for the course: CSE550 or CSE450
or some background in algorithms or optimization.
Most prerequisites will be integrated in the course.
Grading
Grades will be based on a few homework assignments,
a take-home midterm exam and a final project.