本校同學希望旁聽課程請直接聯絡助教吳政宏 r11921036@ntu.edu.tw In this course, we 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. In the first half of the semester, we will focus on approximation algorithms. Approximation algorithms are algorithms that find near-optimal solutions with provable performance guarantees in polynomial time. We will cover design techniques such as rounding and primal-dual algorithms. In the second half of the semester, we will focus on different topics in randomized algorithms. We will cover algorithm design techniques such as hashing, sampling, random walks, and derandomization.

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

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

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