Description: This course will cover some advanced topics on algorithm design and analysis. Some of the tentative topics are given below:
- NP-hardness recap.
- Linear programming: Rounding, Primal-dual
- Hardness of approximation:
- Semidefinite programming
- Johnson Lindenstrauss
- Singular Value Decomposition (SVD)
- Streaming algorithms: Distinct elements, Frequency moments, majority element
- VC dimension