Short Course Description
Credits: 3
Prerequisites: Data Structures and Algorithms
This course aims at two targets. One is to get the students acquainted with a selection of advanced techniques in algorithmic theory, and the other is to let the students experience what is the spirit in contemporary algorithmic research. Namely, what problems are considered interesting, and how to evaluate possible solutions
The course will include topics from the following list: (1) Approximation background: Decision and optimization problems, NP Hardness, approximation algorithm, approximation scheme. (2) Basic approximation algorithms: vertex and set cover, traveling salesman, subset sum, knapsack. (3) Randomized algorithms: the probabilistic method with applications to max-cut and max-SAT; randomized rounding; random sampling and its applications (e.g., to property testing). (4) Online problems: ski rentals, self-organizing lists, best-expert and bandit, paging, load balancing, call admission in communication networks. (5) Distributed and parallel computation: models and algorithms. Algorithms include Bellman-Ford, maximal independent set, prefix sums, minimum spanning tree.
Full Syllabus
