# 高级算法 (Fall 2017)

Instructor

Email yitong.yin@gmail.com yinyt@nju.edu.cn
office 计算机系 804
Class
Class meetings Thursday, 8am-10am

Office hours Monday, 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 2017. Students who take this class should check this page periodically for content updates and new announcements.

# Announcement

• (2017/9/7) 新学期第一次上课。
• (2017/9/21) 第一次作业发布。10月12日课上交。
• (2018/1/2) 期末考试定于1月11日晚7点整准时开始，地点在仙I-207。

# Course info

• Instructor : 尹一通，
• email: yitong.yin@gmail.com, yinyt@nju.edu.cn
• office: 计算机系 804.
• Class meeting: Thursday 8am-10am, 逸B-105.
• Office hour: Monday 2pm-4pm, 计算机系 804.

# Syllabus

### 先修课程 Prerequisites

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

### Course materials

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

# Lecture Notes

1. Min-Cut and Max-Cut (slides)
Probability basics
2. Fingerprinting (slides)
Finite field basics
3. Hashing and Sketching (slides)
Basic tail inequalities
4. Balls into bins and Chernoff bound (slides) : Guest lecture by Chaodong Zheng
5. Concentration of measure (slides) : Guest lecture by Chaodong Zheng
6. Dimension Reduction and Locality-Sensitive Hashing (slides)
Jelani Nelson's note on Johnson-Lindenstrauss Theorem
An introduction of LSH
7. Greedy and Local Search (slides)
Computational complexity
8. Rounding Dynamic Programs (slides)
Vazirani book Chap. 8, 9
9. Rounding Linear Programs (slides)
Vazirani book Chap. 14, 16
10. The Primal-Dual Schema (slides)
Vazirani book Chap. 12, 15
Vazirani book Chap. 24, 25
11. Semidefinite Programs (slides)
Vazirani book Chap. 26
SoS SDP course Lecture 1.1, 1.2, 2.1
12. Lovász Local Lemma (slides)
13. The Monte Carlo Method: Sampling and Counting (slides)
14. MCMC: Markov Chain Monte Carlo methods (slides)