This course will study various techniques for designing and analyzing algorithms. We will mainly focus on problems for which the exact algorithm is not known or not efficient enough and problems with resource constraints. Besides designing efficient algorithms, proving the performance guarantees is also a main topic of this course. Some topics that we will cover are as follows: Approximation Algorithms: Algorithms that find near-optimal solutions with provable performance guarantees in polynomial time. This course will mainly focus on approximation algorithms for NP-hard problems. Randomized Algorithms: Algorithms that use random numbers. We will focus on algorithms with provable success probabilities and good expected solution quality. Streaming Algorithms: Algorithms that solve problems on massive datasets. In this type of problem, usually, the algorithm is only allowed to read the data once and use no more than a constant or poly-logarithmic amount of space. Online Algorithm: The input to the problem is not known in advance and arrives over time. An online algorithm must decide how to process a specific input before seeing future inputs. The goal is to perform as well as an algorithm that knows all inputs beforehand. We will cover algorithm design techniques such as hashing, sampling, and linear programming.

本課程主要針對從事演算法研究的學生，提供演算法設計的技巧與未來學習的方向。

預修課程: 演算法、機率、離散數學、資料結構

相關論文

Design of Approximation Algorithms, Williamson and Shmoys Randomized Algorithms, Motwani and Raghavan Approximation Algorithms, Vazirani