TCS Wiki - User contributions [en]

高级算法 (Fall 2025)

2025-11-29T03:41:00Z

Shili: /* Lecture Notes */

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 =
|label5 =
|data5 = '''栗师'''
|header6 =
|label6 = Email
|data6 = shili@nju.edu.cn
|header7 =
|label7= office
|data7= 计算机系 605
|header8 =
|label8 =
|data8 = '''刘景铖'''
|header9 =
|label9 = Email
|data9 = liu@nju.edu.cn
|header10 =
|label10= office
|data10= 计算机系 516
|header11 = Class
|label11 =
|data11 =
|header12 =
|label12 = Class meetings
|data12 = Monday, 2pm-4pm Thursday (双), 2pm-4pm 仙Ⅰ-320
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = TBD, 计算机系 804 
|header15 = Textbooks
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

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

= Announcement =
* '''(2025/9/10)''' 本周四（9月11日）课程时间地点不变，为第五、六节在仙I-320。从第四周（9月15日）开始，采用新的上课时间：每周一的第五、六节，以及双周四的第五、六节，地点仍在仙I-320。

= Course info =
* '''Instructor '''（授课时间顺序）:
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
* '''Teaching Assistant''':
** 侯哲：houzhe@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday, 2pm-4pm, 仙Ⅰ-320
** Thursday (双), 2pm-4pm, 仙Ⅰ-320
* '''Office hour''': Wednesday 2pm-3pm, 计算机系 804
* '''QQ群''': 524141453（加群请注明专业学号姓名）

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

=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== Course materials ===
* [[高级算法 (Fall 2025) / Course materials|教材和参考书]]

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

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

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

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

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

= Assignments =
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.

*[[高级算法 (Fall 2025)/Problem Set 1|Problem Set 1]] 请在 2025/10/30 上课之前(14:00 UTC+8) 提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2025)/第一次作业提交名单|第一次作业提交名单]]

*[[高级算法 (Fall 2025)/Problem Set 2|Problem Set 2]] 请在 2025/12/1 上课之前(14:00 UTC+8) 提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A2.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2025)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2025/Cut.pdf slides])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2025)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2025/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2025)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2025)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2025/Hashing.pdf slides])
#* [[高级算法 (Fall 2025)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2025)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2025)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2025/Concentration.pdf slides])
#* [[高级算法 (Fall 2025)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2025)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2025/NNS.pdf slides])
#* [https://www.cs.princeton.edu/~hy2/teaching/fall22-cos521/notes/JL.pdf Professor Huacheng Yu's note on Johnson-Lindenstrauss Theorem]
#* [http://people.csail.mit.edu/gregory/annbook/introduction.pdf An introduction of LSH]
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2025/LLL.pdf slides])
#* [https://theory.stanford.edu/~jvondrak/MATH233A-2018/Math233-lec02.pdf Professor Jan Vondrák's Lecture Notes on LLL]
#* [https://www.cc.gatech.edu/~vigoda/6550/Notes/Lec16.pdf Professor Eric Vigoda's Lecture Notes on Algorithmic LLL]
# Spectral graph theory and Cheeger's inequality ([[Media:Spectral-graph-theory-AA.pdf|slides]])
#* [https://cs.uwaterloo.ca/~lapchi/cs860-2022/notes/04-Cheeger.pdf Chapter 4] and [https://cs.uwaterloo.ca/~lapchi/cs860-2022/notes/05-Cheeger-generalizations.pdf Chapter 5] of Professor Lap Chi Lau's book
#* See also [https://lucatrevisan.github.io/41000/lecture02.pdf 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
# Random walks ([[Media:Random walk-AA.pdf|slides]])
#* [https://cs.uwaterloo.ca/~lapchi/cs860-2022/notes/06-random-walks.pdf 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
#* [https://arxiv.org/pdf/0909.3346.pdf Perfect Matchings in <math>O(n \log n)</math> Time in Regular Bipartite Graphs, by Goel, Kapralov and Khanna]
#* [https://epubs.siam.org/doi/epdf/10.1137/1.9781611978322.166 A recent work discussing its extensions to regular non-bipartite graphs, by Dani and Hayes]
# Markov chains and spectral gap ([[Media:MCMC AA 2024.pdf|slides]])
#* [https://link.springer.com/article/10.1007/s10955-011-0284-x The Mathematics of Mixing Things Up] by Persi Diaconis
#* [https://math.uchicago.edu/~shmuel/Network-course-readings/MCMCRev.pdf The Markov Chain Monte Carlo Revolution]
# Markov chains and path coupling ([[Media:MCMC path coupling.pdf|slides]])
#* [https://pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf Markov chains and Mixing times, 2nd edition] by David A. Levin and Yuval Peres
#* [https://arxiv.org/abs/2307.13826 Spectral independence and optimal mixing of Markov chains] by Zongchen Chen, Daniel Stefankovic and Eric Vigoda
# Greedy Algorithms ([https://tcs.nju.edu.cn/slides/aa2025/Greedy.pdf slides], [https://tcs.nju.edu.cn/slides/aa2025/Greedy-handout.pdf slides-handout])
# Linear Programming ([https://tcs.nju.edu.cn/slides/aa2025/LinearProgram.pdf slides], [https://tcs.nju.edu.cn/slides/aa2025/LinearProgram-handout.pdf slides-handout])
# Linear Programming Rounding ([https://tcs.nju.edu.cn/slides/aa2025/LPRounding.pdf slides], [https://tcs.nju.edu.cn/slides/aa2025/LPRounding-handout.pdf slides-handout])
# Linear Programming Duality ([https://tcs.nju.edu.cn/slides/aa2025/Duality.pdf slides], [https://tcs.nju.edu.cn/slides/aa2025/Duality-handout.pdf slides-handout])
# Primal-Dual Algorithms ([https://tcs.nju.edu.cn/slides/aa2025/PrimalDual.pdf slides], [https://tcs.nju.edu.cn/slides/aa2025/PrimalDual-handout.pdf slides-handout])
# Semi-Definite Programming and Max-Cut ([https://tcs.nju.edu.cn/slides/aa2025/SDP.pdf slides], [https://tcs.nju.edu.cn/slides/aa2025/SDP-handout.pdf slides-handout])
# Multiplicative Weight Update Method ([https://tcs.nju.edu.cn/slides/aa2025/MWU.pdf slides], [https://tcs.nju.edu.cn/slides/aa2025/MWU-handout.pdf slides-handout])
# Extension Complexity ([https://tcs.nju.edu.cn/slides/aa2025/ExtensionComplexity.pdf slides], [https://tcs.nju.edu.cn/slides/aa2025/ExtensionComplexity-handout.pdf slides-handout])

= Related Online Courses=
* [https://www.cs.cmu.edu/~15850/ Advanced Algorithms] by Anupam Gupta at CMU.
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [http://courses.csail.mit.edu/6.854/current/ Advanced Algorithms] by David Karger and Aleksander Mądry at MIT.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860-2022/ Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.

高级算法 (Fall 2025)

2025-11-29T03:40:22Z

Shili:

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 =
|label5 =
|data5 = '''栗师'''
|header6 =
|label6 = Email
|data6 = shili@nju.edu.cn
|header7 =
|label7= office
|data7= 计算机系 605
|header8 =
|label8 =
|data8 = '''刘景铖'''
|header9 =
|label9 = Email
|data9 = liu@nju.edu.cn
|header10 =
|label10= office
|data10= 计算机系 516
|header11 = Class
|label11 =
|data11 =
|header12 =
|label12 = Class meetings
|data12 = Monday, 2pm-4pm Thursday (双), 2pm-4pm 仙Ⅰ-320
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = TBD, 计算机系 804 
|header15 = Textbooks
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

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

= Announcement =
* '''(2025/9/10)''' 本周四（9月11日）课程时间地点不变，为第五、六节在仙I-320。从第四周（9月15日）开始，采用新的上课时间：每周一的第五、六节，以及双周四的第五、六节，地点仍在仙I-320。

= Course info =
* '''Instructor '''（授课时间顺序）:
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
* '''Teaching Assistant''':
** 侯哲：houzhe@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday, 2pm-4pm, 仙Ⅰ-320
** Thursday (双), 2pm-4pm, 仙Ⅰ-320
* '''Office hour''': Wednesday 2pm-3pm, 计算机系 804
* '''QQ群''': 524141453（加群请注明专业学号姓名）

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

=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== Course materials ===
* [[高级算法 (Fall 2025) / Course materials|教材和参考书]]

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

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

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

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

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

= Assignments =
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.

*[[高级算法 (Fall 2025)/Problem Set 1|Problem Set 1]] 请在 2025/10/30 上课之前(14:00 UTC+8) 提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2025)/第一次作业提交名单|第一次作业提交名单]]

*[[高级算法 (Fall 2025)/Problem Set 2|Problem Set 2]] 请在 2025/12/1 上课之前(14:00 UTC+8) 提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A2.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2025)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2025/Cut.pdf slides])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2025)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2025/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2025)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2025)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2025/Hashing.pdf slides])
#* [[高级算法 (Fall 2025)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2025)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2025)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2025/Concentration.pdf slides])
#* [[高级算法 (Fall 2025)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2025)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2025/NNS.pdf slides])
#* [https://www.cs.princeton.edu/~hy2/teaching/fall22-cos521/notes/JL.pdf Professor Huacheng Yu's note on Johnson-Lindenstrauss Theorem]
#* [http://people.csail.mit.edu/gregory/annbook/introduction.pdf An introduction of LSH]
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2025/LLL.pdf slides])
#* [https://theory.stanford.edu/~jvondrak/MATH233A-2018/Math233-lec02.pdf Professor Jan Vondrák's Lecture Notes on LLL]
#* [https://www.cc.gatech.edu/~vigoda/6550/Notes/Lec16.pdf Professor Eric Vigoda's Lecture Notes on Algorithmic LLL]
# Spectral graph theory and Cheeger's inequality ([[Media:Spectral-graph-theory-AA.pdf|slides]])
#* [https://cs.uwaterloo.ca/~lapchi/cs860-2022/notes/04-Cheeger.pdf Chapter 4] and [https://cs.uwaterloo.ca/~lapchi/cs860-2022/notes/05-Cheeger-generalizations.pdf Chapter 5] of Professor Lap Chi Lau's book
#* See also [https://lucatrevisan.github.io/41000/lecture02.pdf 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
# Random walks ([[Media:Random walk-AA.pdf|slides]])
#* [https://cs.uwaterloo.ca/~lapchi/cs860-2022/notes/06-random-walks.pdf 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
#* [https://arxiv.org/pdf/0909.3346.pdf Perfect Matchings in <math>O(n \log n)</math> Time in Regular Bipartite Graphs, by Goel, Kapralov and Khanna]
#* [https://epubs.siam.org/doi/epdf/10.1137/1.9781611978322.166 A recent work discussing its extensions to regular non-bipartite graphs, by Dani and Hayes]
# Markov chains and spectral gap ([[Media:MCMC AA 2024.pdf|slides]])
#* [https://link.springer.com/article/10.1007/s10955-011-0284-x The Mathematics of Mixing Things Up] by Persi Diaconis
#* [https://math.uchicago.edu/~shmuel/Network-course-readings/MCMCRev.pdf The Markov Chain Monte Carlo Revolution]
# Markov chains and path coupling ([[Media:MCMC path coupling.pdf|slides]])
#* [https://pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf Markov chains and Mixing times, 2nd edition] by David A. Levin and Yuval Peres
#* [https://arxiv.org/abs/2307.13826 Spectral independence and optimal mixing of Markov chains] by Zongchen Chen, Daniel Stefankovic and Eric Vigoda
# Greedy Algorithms ([http://tcs.nju.edu.cn/slides/aa2025/Greedy.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/Greedy-handout.pdf slides-handout])
# Linear Programming ([http://tcs.nju.edu.cn/slides/aa2025/LinearProgram.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/LinearProgram-handout.pdf slides-handout])
# Linear Programming Rounding ([http://tcs.nju.edu.cn/slides/aa2025/LPRounding.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/LPRounding-handout.pdf slides-handout])
# Linear Programming Duality ([http://tcs.nju.edu.cn/slides/aa2025/Duality.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/Duality-handout.pdf slides-handout])
# Primal-Dual Algorithms ([https://tcs.nju.edu.cn/slides/aa2025/PrimalDual.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/PrimalDual-handout.pdf slides-handout])
# Semi-Definite Programming and Max-Cut ([https://tcs.nju.edu.cn/slides/aa2025/SDP.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/SDP-handout.pdf slides-handout])
# Multiplicative Weight Update Method ([https://tcs.nju.edu.cn/slides/aa2025/MWU.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/MWU-handout.pdf slides-handout])
# Extension Complexity ([http://tcs.nju.edu.cn/slides/aa2025/ExtensionComplexity.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/ExtensionComplexity-handout.pdf slides-handout])

= Related Online Courses=
* [https://www.cs.cmu.edu/~15850/ Advanced Algorithms] by Anupam Gupta at CMU.
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [http://courses.csail.mit.edu/6.854/current/ Advanced Algorithms] by David Karger and Aleksander Mądry at MIT.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860-2022/ Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.

高级算法 (Fall 2025)

2025-11-17T05:54:32Z

Shili: /* Lecture Notes */

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 =
|label5 =
|data5 = '''栗师'''
|header6 =
|label6 = Email
|data6 = shili@nju.edu.cn
|header7 =
|label7= office
|data7= 计算机系 605
|header8 =
|label8 =
|data8 = '''刘景铖'''
|header9 =
|label9 = Email
|data9 = liu@nju.edu.cn
|header10 =
|label10= office
|data10= 计算机系 516
|header11 = Class
|label11 =
|data11 =
|header12 =
|label12 = Class meetings
|data12 = Monday, 2pm-4pm Thursday (双), 2pm-4pm 仙Ⅰ-320
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = TBD, 计算机系 804 
|header15 = Textbooks
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

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

= Announcement =
* '''(2025/9/10)''' 本周四（9月11日）课程时间地点不变，为第五、六节在仙I-320。从第四周（9月15日）开始，采用新的上课时间：每周一的第五、六节，以及双周四的第五、六节，地点仍在仙I-320。

= Course info =
* '''Instructor '''（授课时间顺序）:
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
* '''Teaching Assistant''':
** 侯哲：houzhe@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday, 2pm-4pm, 仙Ⅰ-320
** Thursday (双), 2pm-4pm, 仙Ⅰ-320
* '''Office hour''': Wednesday 2pm-3pm, 计算机系 804
* '''QQ群''': 524141453（加群请注明专业学号姓名）

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

=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== Course materials ===
* [[高级算法 (Fall 2025) / Course materials|教材和参考书]]

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

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

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

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

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

= Assignments =
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.

*[[高级算法 (Fall 2025)/Problem Set 1|Problem Set 1]] 请在 2025/10/30 上课之前(14:00 UTC+8) 提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2025)/第一次作业提交名单|第一次作业提交名单]]

*[[高级算法 (Fall 2025)/Problem Set 2|Problem Set 2]] 请在 2025/12/1 上课之前(14:00 UTC+8) 提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A2.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2025)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2025/Cut.pdf slides])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2025)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2025/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2025)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2025)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2025/Hashing.pdf slides])
#* [[高级算法 (Fall 2025)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2025)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2025)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2025/Concentration.pdf slides])
#* [[高级算法 (Fall 2025)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2025)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2025/NNS.pdf slides])
#* [https://www.cs.princeton.edu/~hy2/teaching/fall22-cos521/notes/JL.pdf Professor Huacheng Yu's note on Johnson-Lindenstrauss Theorem]
#* [http://people.csail.mit.edu/gregory/annbook/introduction.pdf An introduction of LSH]
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2025/LLL.pdf slides])
#* [https://theory.stanford.edu/~jvondrak/MATH233A-2018/Math233-lec02.pdf Professor Jan Vondrák's Lecture Notes on LLL]
#* [https://www.cc.gatech.edu/~vigoda/6550/Notes/Lec16.pdf Professor Eric Vigoda's Lecture Notes on Algorithmic LLL]
# Spectral graph theory and Cheeger's inequality ([[Media:Spectral-graph-theory-AA.pdf|slides]])
#* [https://cs.uwaterloo.ca/~lapchi/cs860-2022/notes/04-Cheeger.pdf Chapter 4] and [https://cs.uwaterloo.ca/~lapchi/cs860-2022/notes/05-Cheeger-generalizations.pdf Chapter 5] of Professor Lap Chi Lau's book
#* See also [https://lucatrevisan.github.io/41000/lecture02.pdf 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
# Random walks ([[Media:Random walk-AA.pdf|slides]])
#* [https://cs.uwaterloo.ca/~lapchi/cs860-2022/notes/06-random-walks.pdf 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
#* [https://arxiv.org/pdf/0909.3346.pdf Perfect Matchings in <math>O(n \log n)</math> Time in Regular Bipartite Graphs, by Goel, Kapralov and Khanna]
#* [https://epubs.siam.org/doi/epdf/10.1137/1.9781611978322.166 A recent work discussing its extensions to regular non-bipartite graphs, by Dani and Hayes]
# Markov chains and spectral gap ([[Media:MCMC AA 2024.pdf|slides]])
#* [https://link.springer.com/article/10.1007/s10955-011-0284-x The Mathematics of Mixing Things Up] by Persi Diaconis
#* [https://math.uchicago.edu/~shmuel/Network-course-readings/MCMCRev.pdf The Markov Chain Monte Carlo Revolution]
# Markov chains and path coupling ([[Media:MCMC path coupling.pdf|slides]])
#* [https://pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf Markov chains and Mixing times, 2nd edition] by David A. Levin and Yuval Peres
#* [https://arxiv.org/abs/2307.13826 Spectral independence and optimal mixing of Markov chains] by Zongchen Chen, Daniel Stefankovic and Eric Vigoda
# Greedy Algorithms ([http://tcs.nju.edu.cn/slides/aa2025/Greedy.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/Greedy-handout.pdf slides-handout])
# Linear Programming ([http://tcs.nju.edu.cn/slides/aa2025/LinearProgram.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/LinearProgram-handout.pdf slides-handout])
# Linear Programming Rounding ([http://tcs.nju.edu.cn/slides/aa2025/LPRounding.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/LPRounding-handout.pdf slides-handout])
# Linear Programming Duality ([http://tcs.nju.edu.cn/slides/aa2025/Duality.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/Duality-handout.pdf slides-handout])
# Primal-Dual Algorithms ([http://tcs.nju.edu.cn/slides/aa2025/PrimalDual.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/PrimalDual-handout.pdf slides-handout])
# Semi-Definite Programming and Max-Cut ([http://tcs.nju.edu.cn/slides/aa2025/SDP.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/SDP-handout.pdf slides-handout])
# Multiplicative Weight Update Method ([http://tcs.nju.edu.cn/slides/aa2025/MWU.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/MWU-handout.pdf slides-handout])
# Extension Complexity ([http://tcs.nju.edu.cn/slides/aa2025/ExtensionComplexity.pdf slides], [http://tcs.nju.edu.cn/slides/aa2025/ExtensionComplexity-handout.pdf slides-handout])

= Related Online Courses=
* [https://www.cs.cmu.edu/~15850/ Advanced Algorithms] by Anupam Gupta at CMU.
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [http://courses.csail.mit.edu/6.854/current/ Advanced Algorithms] by David Karger and Aleksander Mądry at MIT.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860-2022/ Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.

高级算法 (Fall 2025)

2025-11-14T07:20:04Z

Shili: /* Lecture Notes */

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 =
|label5 =
|data5 = '''栗师'''
|header6 =
|label6 = Email
|data6 = shili@nju.edu.cn
|header7 =
|label7= office
|data7= 计算机系 605
|header8 =
|label8 =
|data8 = '''刘景铖'''
|header9 =
|label9 = Email
|data9 = liu@nju.edu.cn
|header10 =
|label10= office
|data10= 计算机系 516
|header11 = Class
|label11 =
|data11 =
|header12 =
|label12 = Class meetings
|data12 = Monday, 2pm-4pm Thursday (双), 2pm-4pm 仙Ⅰ-320
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = TBD, 计算机系 804 
|header15 = Textbooks
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

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

= Announcement =
* '''(2025/9/10)''' 本周四（9月11日）课程时间地点不变，为第五、六节在仙I-320。从第四周（9月15日）开始，采用新的上课时间：每周一的第五、六节，以及双周四的第五、六节，地点仍在仙I-320。

= Course info =
* '''Instructor '''（授课时间顺序）:
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
* '''Teaching Assistant''':
** 侯哲：houzhe@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday, 2pm-4pm, 仙Ⅰ-320
** Thursday (双), 2pm-4pm, 仙Ⅰ-320
* '''Office hour''': Wednesday 2pm-3pm, 计算机系 804
* '''QQ群''': 524141453（加群请注明专业学号姓名）

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

=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== Course materials ===
* [[高级算法 (Fall 2025) / Course materials|教材和参考书]]

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

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

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

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

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

= Assignments =
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.

*[[高级算法 (Fall 2025)/Problem Set 1|Problem Set 1]] 请在 2025/10/30 上课之前(14:00 UTC+8) 提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2025)/第一次作业提交名单|第一次作业提交名单]]

*[[高级算法 (Fall 2025)/Problem Set 2|Problem Set 2]] 请在 2025/12/1 上课之前(14:00 UTC+8) 提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A2.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2025)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2025/Cut.pdf slides])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2025)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2025/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2025)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2025)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2025/Hashing.pdf slides])
#* [[高级算法 (Fall 2025)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2025)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2025)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2025/Concentration.pdf slides])
#* [[高级算法 (Fall 2025)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2025)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2025/NNS.pdf slides])
#* [https://www.cs.princeton.edu/~hy2/teaching/fall22-cos521/notes/JL.pdf Professor Huacheng Yu's note on Johnson-Lindenstrauss Theorem]
#* [http://people.csail.mit.edu/gregory/annbook/introduction.pdf An introduction of LSH]
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2025/LLL.pdf slides])
#* [https://theory.stanford.edu/~jvondrak/MATH233A-2018/Math233-lec02.pdf Professor Jan Vondrák's Lecture Notes on LLL]
#* [https://www.cc.gatech.edu/~vigoda/6550/Notes/Lec16.pdf Professor Eric Vigoda's Lecture Notes on Algorithmic LLL]
# Spectral graph theory and Cheeger's inequality ([[Media:Spectral-graph-theory-AA.pdf|slides]])
#* [https://cs.uwaterloo.ca/~lapchi/cs860-2022/notes/04-Cheeger.pdf Chapter 4] and [https://cs.uwaterloo.ca/~lapchi/cs860-2022/notes/05-Cheeger-generalizations.pdf Chapter 5] of Professor Lap Chi Lau's book
#* See also [https://lucatrevisan.github.io/41000/lecture02.pdf 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
# Random walks ([[Media:Random walk-AA.pdf|slides]])
#* [https://cs.uwaterloo.ca/~lapchi/cs860-2022/notes/06-random-walks.pdf 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
#* [https://arxiv.org/pdf/0909.3346.pdf Perfect Matchings in <math>O(n \log n)</math> Time in Regular Bipartite Graphs, by Goel, Kapralov and Khanna]
#* [https://epubs.siam.org/doi/epdf/10.1137/1.9781611978322.166 A recent work discussing its extensions to regular non-bipartite graphs, by Dani and Hayes]
# Markov chains and spectral gap ([[Media:MCMC AA 2024.pdf|slides]])
# Markov chains and path coupling ([[Media:MCMC path coupling.pdf|slides]])
# Greedy Algorithms ([http://tcs.nju.edu.cn/slides/aa2024/Greedy.pdf slides], [http://tcs.nju.edu.cn/slides/aa2024/Greedy-handout.pdf slides-handout])
# Linear Programming ([http://tcs.nju.edu.cn/slides/aa2024/LinearProgram.pdf slides], [http://tcs.nju.edu.cn/slides/aa2024/LinearProgram-handout.pdf slides-handout])
# Linear Programming Rounding ([http://tcs.nju.edu.cn/slides/aa2024/LPRounding.pdf slides], [http://tcs.nju.edu.cn/slides/aa2024/LPRounding-handout.pdf slides-handout])
# Linear Programming Duality ([http://tcs.nju.edu.cn/slides/aa2024/Duality.pdf slides], [http://tcs.nju.edu.cn/slides/aa2024/Duality-handout.pdf slides-handout])
# Primal-Dual Algorithms ([http://tcs.nju.edu.cn/slides/aa2024/PrimalDual.pdf slides], [http://tcs.nju.edu.cn/slides/aa2024/PrimalDual-handout.pdf slides-handout])
# Semi-Definite Programming and Max-Cut ([http://tcs.nju.edu.cn/slides/aa2024/SDP.pdf slides], [http://tcs.nju.edu.cn/slides/aa2024/SDP-handout.pdf slides-handout])
# Multiplicative Weight Update Method ([http://tcs.nju.edu.cn/slides/aa2024/MWU.pdf slides], [http://tcs.nju.edu.cn/slides/aa2024/MWU-handout.pdf slides-handout])
# Extension Complexity ([http://tcs.nju.edu.cn/slides/aa2024/ExtensionComplexity.pdf slides], [http://tcs.nju.edu.cn/slides/aa2024/ExtensionComplexity-handout.pdf slides-handout])

= Related Online Courses=
* [https://www.cs.cmu.edu/~15850/ Advanced Algorithms] by Anupam Gupta at CMU.
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [http://courses.csail.mit.edu/6.854/current/ Advanced Algorithms] by David Karger and Aleksander Mądry at MIT.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860-2022/ Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.

高级算法 (Fall 2024)

2024-11-06T12:43:11Z

Shili: /* Lecture Notes */

高级算法 (Fall 2024)

2024-11-06T08:47:49Z

Shili: /* Lecture Notes */

高级算法 (Fall 2024)

2024-11-04T14:04:57Z

Shili:

高级算法 (Fall 2023)

2024-11-04T14:03:35Z

2023-12-01T12:33:20Z

Shili: /* Lecture Notes */

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 =
|label5 =
|data5 = '''栗师'''
|header6 =
|label6 = Email
|data6 = shili@nju.edu.cn
|header7 =
|label7= office
|data7= 计算机系 605
|header8 =
|label8 =
|data8 = '''刘景铖'''
|header9 =
|label9 = Email
|data9 = liu@nju.edu.cn
|header10 =
|label10= office
|data10= 计算机系 516
|header11 = Class
|label11 =
|data11 =
|header12 =
|label12 = Class meetings
|data12 = Tuesday, 2pm-5pm, 仙Ⅰ-206 
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = Thursday, 2pm-4pm, 计算机系 804 
|header15 = Textbooks
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

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/

= Course info =
* '''Instructor ''':
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
* '''Teaching Assistant''':
** 陈弘毅：[mailto:502023330006@smail.nju.edu.cn <502023330006@smail.nju.edu.cn>]，计算机系 426
** 邹宗瑞：[mailto:zou.zongrui@smail.nju.edu.cn <zou.zongrui@smail.nju.edu.cn>]，计算机系 410
* '''Mailbox for Homework''': [mailto:njuadvalg23@163.com njuadvalg23@163.com]
* '''Class meeting''': Tuesday, 2pm-5pm, 仙Ⅰ-206
* '''Office hour''': Thursday, 2pm-4pm, 计算机系 804
* '''QQ群''': 876680440

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

=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== Course materials ===
* [[高级算法 (Fall 2023) / Course materials|教材和参考书]]

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

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

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

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

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

= Assignments =
*[[高级算法 (Fall 2023)/Problem Set 1|Problem Set 1]] 请在 2023/11/14 上课之前(14:00 UTC+8)提交到 [mailto:njuadvalg23@163.com njuadvalg23@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2023)/第一次作业提交名单|第一次作业提交名单]]
*[[高级算法 (Fall 2023)/Problem Set 2|Problem Set 2]] 请在 2023/12/19 上课之前(14:00 UTC+8)提交到 [mailto:njuadvalg23@163.com njuadvalg23@163.com] (文件名为'学号_姓名_A2.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2023)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2023/Cut.pdf slides])
#: [[高级算法 (Fall 2023)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2023)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2023/Fingerprinting.pdf slides])
#: [[高级算法 (Fall 2023)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2023)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2023/Hashing.pdf slides])
#: [[高级算法 (Fall 2023)/Limited independence|Limited independence]]
#: [[高级算法 (Fall 2023)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2023)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2023/Concentration.pdf slides])
#: [[高级算法 (Fall 2023)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2023)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2023/NNS.pdf slides])
#: [https://www.cs.princeton.edu/~hy2/teaching/fall22-cos521/notes/JL.pdf Professor Huacheng Yu's note on Johnson-Lindenstrauss Theorem]
#: [http://people.csail.mit.edu/gregory/annbook/introduction.pdf An introduction of LSH]
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2023/LLL.pdf slides])
#: [https://theory.stanford.edu/~jvondrak/MATH233A-2018/Math233-lec02.pdf Professor Jan Vondrák's Lecture Notes on LLL]
#: [https://www.cc.gatech.edu/~vigoda/6550/Notes/Lec16.pdf Professor Eric Vigoda's Lecture Notes on Algorithmic LLL]
# Spectral graph theory and Cheeger's inequality ([[Media:L8_spectral-graph-theory.pdf |slides]])
#: [https://cs.uwaterloo.ca/~lapchi/cs860/notes/04-Cheeger.pdf Chapter 4] and [https://cs.uwaterloo.ca/~lapchi/cs860/notes/05-Cheeger-generalizations.pdf Chapter 5] of Professor Lap Chi Lau's book
#: See also [https://lucatrevisan.github.io/41000/lecture02.pdf 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
# Random Walk ([[Media:AA2023_L9_random_walk.pdf |slides]])
#: [https://cs.uwaterloo.ca/~lapchi/cs860/notes/06-random-walks.pdf 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
#: [https://arxiv.org/pdf/0909.3346.pdf Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs, by Goel, Kapralov and Khanna]
# Electrical networks ([[Media:L10_electrical_networks.pdf|slides]])
#: Chapter 11 and Chapter 12 of Professor Daniel A. Spielman's [http://cs-www.cs.yale.edu/homes/spielman/sagt/sagt.pdf Spectral and Algebraic Graph Theory] book
#: See also Chapter 4 of Professor Nisheeth K. Vishnoi's [https://www.cs.yale.edu/homes/vishnoi/Lxb-Web.pdf Lx=b] monograph and Chapter 2 of [https://rdlyons.pages.iu.edu/prbtree/book_online.pdf Probability on Trees and Networks] by Lyons and Peres
#: Related course note: [https://sites.google.com/g.harvard.edu/sgt/home/spring-2023/schedule-lecture-notes-and-assignments/lecture-notes/lecture-16-notes Professor Salil Vadhan's], [https://homes.cs.washington.edu/~shayan/courses/approx/adv-approx-4.pdf 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 [https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Convex Optimization] by Boyd and Vandenberghe
#: Graph connectivity is closely related to many complexity theoretic questions, see [https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AVI/PRAGUE/conn.pdf a survey] by Professor Avi Wigderson
# Markov chain Monte Carlo and Coupling ([[Media:L11_MCMC.pdf|slides]])
# Expanders: Pseudorandomness, Coding and Constructions, guest lecture by [https://pwu.netlify.app/ Dr. Pei Wu] ([[Media:Advanced_algorithm_2023_peiwu_expander.pdf|notes]])
#: A very nice survey on Expanders by [https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf Hoory, Linial, Wigderson]
#: See also Professor Venkat Guruswami’s lecture note on [https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes8.pdf expander codes]
# Greedy Algorithms and Local Search
#: Maximum-Weight Independent Set in Matroids
#: 2-Approximation Algorithm for Vertex Cover
#: $f$-Approximation for Set-Cover with Frequency f
#: (ln n + 1)-Approximation for Set-Cover
#: 1 − 1/e Approximation for Maximum Coverage
#: 1 − 1/e Approximation for Submodular Maximization under a Cardinality Constraint
#: 2-Approximation for Maximum-Cut via Local Search
#: Local Search for Uncapacitated Facility Location

= Related Online Courses=
* [https://www.cs.cmu.edu/~15850/ Advanced Algorithms] by Anupam Gupta at CMU.
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [http://courses.csail.mit.edu/6.854/current/ Advanced Algorithms] by David Karger and Aleksander Mądry at MIT.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860/index.html Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.

高级算法 (Fall 2023)

2023-12-01T12:32:52Z

Shili:

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = '''尹一通'''
|header3 =
|label3 = Email
|data3 = yinyt@nju.edu.cn
|header4 =
|label4= office
|data4= 计算机系 804
|header5 =
|label5 =
|data5 = '''栗师'''
|header6 =
|label6 = Email
|data6 = shili@nju.edu.cn
|header7 =
|label7= office
|data7= 计算机系 605
|header8 =
|label8 =
|data8 = '''刘景铖'''
|header9 =
|label9 = Email
|data9 = liu@nju.edu.cn
|header10 =
|label10= office
|data10= 计算机系 516
|header11 = Class
|label11 =
|data11 =
|header12 =
|label12 = Class meetings
|data12 = Tuesday, 2pm-5pm, 仙Ⅰ-206 
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = Thursday, 2pm-4pm, 计算机系 804 
|header15 = Textbooks
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

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/

= Course info =
* '''Instructor ''':
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
* '''Teaching Assistant''':
** 陈弘毅：[mailto:502023330006@smail.nju.edu.cn <502023330006@smail.nju.edu.cn>]，计算机系 426
** 邹宗瑞：[mailto:zou.zongrui@smail.nju.edu.cn <zou.zongrui@smail.nju.edu.cn>]，计算机系 410
* '''Mailbox for Homework''': [mailto:njuadvalg23@163.com njuadvalg23@163.com]
* '''Class meeting''': Tuesday, 2pm-5pm, 仙Ⅰ-206
* '''Office hour''': Thursday, 2pm-4pm, 计算机系 804
* '''QQ群''': 876680440

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

=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== Course materials ===
* [[高级算法 (Fall 2023) / Course materials|教材和参考书]]

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

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

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

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

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

= Assignments =
*[[高级算法 (Fall 2023)/Problem Set 1|Problem Set 1]] 请在 2023/11/14 上课之前(14:00 UTC+8)提交到 [mailto:njuadvalg23@163.com njuadvalg23@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2023)/第一次作业提交名单|第一次作业提交名单]]
*[[高级算法 (Fall 2023)/Problem Set 2|Problem Set 2]] 请在 2023/12/19 上课之前(14:00 UTC+8)提交到 [mailto:njuadvalg23@163.com njuadvalg23@163.com] (文件名为'学号_姓名_A2.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2023)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2023/Cut.pdf slides])
#: [[高级算法 (Fall 2023)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2023)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2023/Fingerprinting.pdf slides])
#: [[高级算法 (Fall 2023)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2023)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2023/Hashing.pdf slides])
#: [[高级算法 (Fall 2023)/Limited independence|Limited independence]]
#: [[高级算法 (Fall 2023)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2023)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2023/Concentration.pdf slides])
#: [[高级算法 (Fall 2023)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2023)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2023/NNS.pdf slides])
#: [https://www.cs.princeton.edu/~hy2/teaching/fall22-cos521/notes/JL.pdf Professor Huacheng Yu's note on Johnson-Lindenstrauss Theorem]
#: [http://people.csail.mit.edu/gregory/annbook/introduction.pdf An introduction of LSH]
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2023/LLL.pdf slides])
#: [https://theory.stanford.edu/~jvondrak/MATH233A-2018/Math233-lec02.pdf Professor Jan Vondrák's Lecture Notes on LLL]
#: [https://www.cc.gatech.edu/~vigoda/6550/Notes/Lec16.pdf Professor Eric Vigoda's Lecture Notes on Algorithmic LLL]
# Spectral graph theory and Cheeger's inequality ([[Media:L8_spectral-graph-theory.pdf |slides]])
#: [https://cs.uwaterloo.ca/~lapchi/cs860/notes/04-Cheeger.pdf Chapter 4] and [https://cs.uwaterloo.ca/~lapchi/cs860/notes/05-Cheeger-generalizations.pdf Chapter 5] of Professor Lap Chi Lau's book
#: See also [https://lucatrevisan.github.io/41000/lecture02.pdf 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
# Random Walk ([[Media:AA2023_L9_random_walk.pdf |slides]])
#: [https://cs.uwaterloo.ca/~lapchi/cs860/notes/06-random-walks.pdf 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
#: [https://arxiv.org/pdf/0909.3346.pdf Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs, by Goel, Kapralov and Khanna]
# Electrical networks ([[Media:L10_electrical_networks.pdf|slides]])
#: Chapter 11 and Chapter 12 of Professor Daniel A. Spielman's [http://cs-www.cs.yale.edu/homes/spielman/sagt/sagt.pdf Spectral and Algebraic Graph Theory] book
#: See also Chapter 4 of Professor Nisheeth K. Vishnoi's [https://www.cs.yale.edu/homes/vishnoi/Lxb-Web.pdf Lx=b] monograph and Chapter 2 of [https://rdlyons.pages.iu.edu/prbtree/book_online.pdf Probability on Trees and Networks] by Lyons and Peres
#: Related course note: [https://sites.google.com/g.harvard.edu/sgt/home/spring-2023/schedule-lecture-notes-and-assignments/lecture-notes/lecture-16-notes Professor Salil Vadhan's], [https://homes.cs.washington.edu/~shayan/courses/approx/adv-approx-4.pdf 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 [https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf Convex Optimization] by Boyd and Vandenberghe
#: Graph connectivity is closely related to many complexity theoretic questions, see [https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/AVI/PRAGUE/conn.pdf a survey] by Professor Avi Wigderson
# Markov chain Monte Carlo and Coupling ([[Media:L11_MCMC.pdf|slides]])
# Expanders: Pseudorandomness, Coding and Constructions, guest lecture by [https://pwu.netlify.app/ Dr. Pei Wu] ([[Media:Advanced_algorithm_2023_peiwu_expander.pdf|notes]])
#: A very nice survey on Expanders by [https://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf Hoory, Linial, Wigderson]
#: See also Professor Venkat Guruswami’s lecture note on [https://www.cs.cmu.edu/~venkatg/teaching/codingtheory/notes/notes8.pdf expander codes]
# Greedy Algorithms and Local Search
#: Maximum-Weight Independent Set in Matroids
#: 2-Approximation Algorithm for Vertex Cover
#: f-Approximation for Set-Cover with Frequency f
#: (ln n + 1)-Approximation for Set-Cover
#: �1 − 1/e Approximation for Maximum Coverage
#: 1 − 1/e Approximation for Submodular Maximization under a Cardinality Constraint
#: 2-Approximation for Maximum-Cut via Local Search
#: Local Search for Uncapacitated Facility Location

= Related Online Courses=
* [https://www.cs.cmu.edu/~15850/ Advanced Algorithms] by Anupam Gupta at CMU.
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [http://courses.csail.mit.edu/6.854/current/ Advanced Algorithms] by David Karger and Aleksander Mądry at MIT.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860/index.html Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.