# Difference between revisions of "高级算法 (Fall 2021)"

Jump to: navigation, search

Advanced Algorithms
Instructor

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

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

# Announcement

• (2021/08/31) 今天在线课程的slides和录屏视频已经上传，参见lecture notes部分。
• (2021/09/15) 第一次作业已发布，请在 2021/9/28 上课之前提交到 njuadvalg21@163.com (文件名为'学号_姓名_A1.pdf').
• (2021/11/25) 下周（11月30日）开始，课程改为线上，线上腾讯会议号仍为 598 944 8767。

# Course info

• email: yinyt@nju.edu.cn
• 线上直播: 腾讯会议 598 944 8767
• 线下: 逸B-207
• Office hour: 待定
• QQ群: 893909781

# Syllabus

### 先修课程 Prerequisites

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

### 成绩 Grades

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

# Lecture Notes

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