# 高级算法 (Fall 2022)

Instructor

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

Office hours Thursday, 2pm-4pm
804
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 2022. Students who take this class should check this page periodically for content updates and new announcements.

# Announcement

• (2022/10/10) 第一次作业已发布，请在 2022/10/25 上课之前提交到 njuadvalg22@163.com (文件名为'学号_姓名_A1.pdf').
• (2022/11/1) 第二次作业已发布，请在 2022/11/15 上课之前提交到 njuadvalg22@163.com (文件名为'学号_姓名_A2.pdf').
• (2022/11/28) 第三次作业已发布，请在 2022/12/13 上课之前提交到 njuadvalg22@163.com (文件名为'学号_姓名_A3.pdf').
• (2022/12/13) 第四次作业已发布，请在 2023/1/3 下午2点之前提交到 njuadvalg22@163.com (文件名为'学号_姓名_A4.pdf').

# Course info

• email: yinyt@nju.edu.cn
• 线上直播: 腾讯会议 598 944 8767
• 线下: 逸B-104
• Office hour: Thursday, 2pm-4pm
• QQ群: 945849735

# Syllabus

### 先修课程 Prerequisites

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

### Course materials

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

# Lecture Notes

1. Min-Cut and Max-Cut (slides) (video1 video2 video3 video4)
Probability basics
2. Fingerprinting (slides) (video1 video2 video3)
Finite field basics
3. Balls into bins (slides1 slides2) (video1 video2 video3 video4) including a guest lecture by Prof. Chaodong Zheng
Limited independence
4. Hashing and Sketching (slides) (video1 video2 video3)
Basic tail inequalities
5. Concentration of measure (slides) (video1 video2 video3)
Conditional expectations
6. Dimension Reduction (slides) (video1 video2 video3 video4 video5 video6)
Jelani Nelson's note on Johnson-Lindenstrauss Theorem
An introduction of LSH
7. Lovász Local Lemma (slides) (video1 video2 video3 video4 video5 video6)
Professor Jan Vondrák's Lecture Notes on LLL
Professor Eric Vigoda's Lecture Notes on Algorithmic LLL
8. Greedy and Local Search (slides) (video1 video2 video3 video4 video5 video6)
Professor Jan Vondrák's notes and slides on submodular optimization
9. Rounding Dynamic Programs (slides)
Vazirani book Chap. 8
10. Rounding Linear Programs (slides) (video1 video2 video3)
Vazirani book Chap. 14, 16
Notes on LP and SDP by Anupam Gupta and Ryan O’Donnell
11. The Primal-Dual Schema (slides) (video1 video2 video3)
Vazirani book Chap. 12, 15
12. SDP based algorithms (slides) (video1)
Vazirani book Chap. 26