高级算法 (Fall 2023)

高级算法
Advanced Algorithms

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, 仙Ⅰ-206
Office hours	Thursday, 2pm-4pm, 计算机系 804
Textbooks
Motwani and Raghavan. Randomized Algorithms. Cambridge Univ Press, 1995.
Vazirani. Approximation Algorithms. Springer-Verlag, 2001.

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群中。

Course info

• Instructor :

• 尹一通：<yinyt@nju.edu.cn>，计算机系 804
• 栗师：<shili@nju.edu.cn>，计算机系 605
• 刘景铖：<liu@nju.edu.cn>，计算机系 516

• Teaching Assistant:
  • 陈弘毅：<502023330006@smail.nju.edu.cn>，计算机系 426
  • 邹宗瑞：<zou.zongrui@smail.nju.edu.cn>，计算机系 410
• Mailbox for Homework: njuadvalg23@163.com
• Class meeting: Tuesday, 2pm-5pm, 仙Ⅰ-206
• Office hour: Thursday, 2pm-4pm, 计算机系 804
• QQ群: 876680440

Syllabus

随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。

先修课程 Prerequisites

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

Course materials

• 教材和参考书

成绩 Grades

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

学术诚信 Academic Integrity

学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 ACM Policy on Plagiarism的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

Assignments

• Problem Set 1 请在 2023/11/14 上课之前(14:00 UTC+8)提交到 njuadvalg23@163.com (文件名为'学号_姓名_A1.pdf'). 第一次作业提交名单
• Problem Set 2 请在 2023/12/19 上课之前(14:00 UTC+8)提交到 njuadvalg23@163.com (文件名为'学号_姓名_A2.pdf'). 第二次作业提交名单
• Take home final (2023 fall) 请在 2024/01/09 2024/01/14 12:00 UTC+8 提交到 njuadvalg23@163.com (文件名为'学号_姓名_final.pdf').

Lecture Notes

1. Min Cut, Max Cut, and Spectral Cut (slides)
   • Probability basics
2. Fingerprinting (slides)
   • Finite field basics
3. Hashing and Sketching (slides)
   • Limited independence
   • Basic deviation inequalities
4. Concentration of measure (slides)
   • Conditional expectations
5. Dimension Reduction (slides)
   • Professor Huacheng Yu's note on Johnson-Lindenstrauss Theorem
   • An introduction of LSH
6. Lovász Local Lemma (slides)
   • Professor Jan Vondrák's Lecture Notes on LLL
   • Professor Eric Vigoda's Lecture Notes on Algorithmic LLL
7. Spectral graph theory and Cheeger's inequality (slides)
   • Chapter 4 and Chapter 5 of Professor Lap Chi Lau's book
   • See also Professor Luca Trevisan's note for a different treatment of positive and negative entries in the threshold rounding step, which works even if the vector is not an eigenvector
8. Random Walk (slides)
   • Chapter 6 of Professor Lap Chi Lau's book
   • See Chapter 7.1.1 of Probability and Computing for an analysis of the random walk algorithm for 2SAT
   • Perfect Matchings in [math]\displaystyle{ O(n \log n) }[/math] Time in Regular Bipartite Graphs, by Goel, Kapralov and Khanna
9. Electrical networks (slides)
   • Chapter 11 and Chapter 12 of Professor Daniel A. Spielman's Spectral and Algebraic Graph Theory book
   • See also Chapter 4 of Professor Nisheeth K. Vishnoi's [math]\displaystyle{ Lx=b }[/math] monograph and Chapter 2 of Probability on Trees and Networks by Lyons and Peres
   • Related course note: Professor Salil Vadhan's, Professor Shayan Oveis Gharan's
   • For a reference of the Lagrange dual formulation of a constrained convex optimization problem, and the corresponding optimality (KKT) conditions, see Chapter 5.5.3 of Convex Optimization by Boyd and Vandenberghe
   • Graph connectivity is closely related to many complexity theoretic questions, see a survey by Professor Avi Wigderson
10. Markov chain Monte Carlo and Coupling (slides)
11. Expanders: Pseudorandomness, Coding and Constructions, guest lecture by Dr. Pei Wu (notes)
    • A very nice survey on Expanders by Hoory, Linial, Wigderson
    • See also Professor Venkat Guruswami’s lecture note on expander codes
12. Greedy Algorithms and Local Search (slides, handout)
    • Maximum-Weight Independent Set in Matroids
    • 2-Approximation Algorithm for Vertex Cover
    • [math]\displaystyle{ f }[/math]-Approximation for Set-Cover with Frequency [math]\displaystyle{ f }[/math] (Lecture Notes from Shuchi Chawla's Course)
    • [math]\displaystyle{ (\ln n + 1) }[/math]-Approximation for Set-Cover (Section 1.6 of WS book)
    • [math]\displaystyle{ (1 − 1/\mathrm{e}) }[/math]-Approximation for Maximum Coverage
    • [math]\displaystyle{ (1 − 1/\mathrm{e}) }[/math]-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)
    • Vazirani book Chap. 8
14. Linear Programming Rounding (slides, handout)
    • Vazirani book Chap. 14, 16
    • Notes on LP and SDP by Anupam Gupta and Ryan O’Donnell
15. The Primal-Dual Schema (slides, handout)
    • Vazirani book Chap. 12, 15
16. SDP based algorithms
    • Vazirani book Chap. 26

Related Online Courses

• Advanced Algorithms by Anupam Gupta at CMU.
• Advanced Algorithms by Ankur Moitra at MIT.
• Advanced Algorithms by David Karger and Aleksander Mądry at MIT.
• The Modern Algorithmic Toolbox by Tim Roughgarden and Gregory Valiant at Stanford.
• Advanced Algorithm Design by Pravesh Kothari and Christopher Musco at Princeton.
• Linear and Semidefinite Programming (Advanced Algorithms) by Anupam Gupta and Ryan O'Donnell at CMU.
• CS Theory Toolkit by Ryan O'Donnell at CMU.
• Eigenvalues and Polynomials by Lap Chi Lau at University of Waterloo.
• The "Foundations of Data Science" book by Avrim Blum, John Hopcroft, and Ravindran Kannan.