# 高级算法 (Fall 2023)

Instructor

Email yinyt@nju.edu.cn
office 计算机系 804

Email shili@nju.edu.cn
office 计算机系 605

Email liu@nju.edu.cn
office 计算机系 516
Class
Class meetings Tuesday, 2pm-5pm,

Office hours Thursday, 2pm-4pm,

Textbooks
Motwani and Raghavan.
Randomized Algorithms.
Cambridge Univ Press, 1995.
Vazirani.
Approximation Algorithms.
Springer-Verlag, 2001.
v · d · e

This is the webpage for the Advanced Algorithms class of fall 2023. Students who take this class should check this page periodically for content updates and new announcements.

# Announcement

• (2023/09/04) 上课时间通知： 第一次上课时间更改为第二周周二（9月12日）14:00-17:00。
• (2023/11/23) 补课时间调查问卷链接：https://wj.qq.com/s2/13624543/2b1b/
• (2024/01/02) Final已经发布，文档密码公布于QQ群中。

• Instructor :

# Syllabus

### 先修课程 Prerequisites

• 必须：离散数学，概率论，线性代数。
• 推荐：算法设计与分析。

### Course materials

• 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
• 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

# Lecture Notes

1. Min Cut, Max Cut, and Spectral Cut (slides)
2. Fingerprinting (slides)
3. Hashing and Sketching (slides)
4. Concentration of measure (slides)
5. Dimension Reduction (slides)
6. Lovász Local Lemma (slides)
7. Spectral graph theory and Cheeger's inequality (slides)
8. Random Walk (slides)
9. Electrical networks (slides)
10. Markov chain Monte Carlo and Coupling (slides)
11. Expanders: Pseudorandomness, Coding and Constructions, guest lecture by Dr. Pei Wu (notes)
12. Greedy Algorithms and Local Search (slides, handout)
• Maximum-Weight Independent Set in Matroids
• 2-Approximation Algorithm for Vertex Cover
• $\displaystyle{ f }$-Approximation for Set-Cover with Frequency $\displaystyle{ f }$ (Lecture Notes from Shuchi Chawla's Course)
• $\displaystyle{ (\ln n + 1) }$-Approximation for Set-Cover (Section 1.6 of WS book)
• $\displaystyle{ (1 − 1/\mathrm{e}) }$-Approximation for Maximum Coverage
• $\displaystyle{ (1 − 1/\mathrm{e}) }$-Approximation for Submodular Maximization under a Cardinality Constraint
• 2-Approximation for Maximum-Cut via Local Search
• Local Search for Uncapacitated Facility Location (Section 9.1 of WS book)
13. Dynamic Programming (slides, handout)
14. Linear Programming Rounding (slides, handout)
15. The Primal-Dual Schema (slides, handout)
16. SDP based algorithms