TCS Wiki - User contributions [en]

高级算法 (Fall 2025)/第三次作业提交名单

2026-01-19T05:22:17Z

Zhangyiyao:

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 221502007 || 崔毓泽
|-
| 221502008 || 梁今为
|-
| 221502013 || 贺龄瑞
|-
| 221502018 || 陈正道
|-
| 221850037 || 王朝晖
|-
| 221900156 || 韩加瑞
|-
| 231098067 || 徐浩然
|-
| 231220002 || 潘谟天
|-
| 231220005 || 樊书岩
|-
| 231220007 || 汪文韬
|-
| 231220012 || 张启越
|-
| 231220019 || 何云天
|-
| 231220056 || 黄思远
|-
| 231220179 || 徐钰炜
|-
| 231240019 || 邵与乔
|-
| 231502022 || 胡骏秋
|-
| 231870127 || 李熠城
|-
| 231870210 || 沈奕齐
|-
| 502024330018 || 胡贵川
|-
| 502024370012 || 胡泽坤
|-
| 502025330006 || 陈俊杰
|-
| 502025330007 || 陈星宇
|-
| 502025330018 || 何平
|-
| 502025330055 || 夏天钰
|-
| 502025330076 || 赵可泰
|-
| 502025330084 || 周一凡
|-
| 502025370010 || 甘东伟
|-
| 502025370014 || 何临哲
|-
| 502025370022 || 李嘉伟
|-
| 502025370028 || 刘亮慧
|-
| 502025370034 || 裴鸣宇
|-
| 502025370060 || 吴璋泰
|-
| 502025370062 || 肖雨辰
|-
| 502025370063 || 许忱
|-
| 522025330028 || 何卓霖
|-
| 522025330048 || 李小涵
|-
| 522025330082 || 沈子杰
|-
| 522025330095 || 王昊田
|-
| 522025330096 || 王敬尧
|-
| 602025330038 || 张峰瑞
|-
| 652024330020 || 沈思
|-
| 652025330001 || 陈瀚
|-
| 652025330005 || 陈煜航
|-
| 652025330009 || 胡伟江
|-
| 652025330013 || 鞠哲
|-
| 652025330029 || 王昕烨
|-
| 652025330030 || 王远博
|-
| 652025330031 || 王在烜
|-
| 652025330033 || 吴文翔
|-
| 652025330034 || 许宝铎
|-
| 652025330043 || 周宇恒
|-
| 652025330045 || 祝永祺
|}
</center>

高级算法 (Fall 2025)/第二次作业提交名单

2026-01-16T09:45:39Z

Zhangyiyao:

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 221502007 || 崔毓泽
|-
| 221502008 || 梁今为
|-
| 221502013 || 贺龄瑞
|-
| 221502018 || 陈正道
|-
| 221850037 || 王朝晖
|-
| 221900156 || 韩加瑞
|-
| 231098067 || 徐浩然
|-
| 231220002 || 潘谟天
|-
| 231220005 || 樊书岩
|-
| 231220007 || 汪文韬
|-
| 231220012 || 张启越
|-
| 231220019 || 何云天
|-
| 231220056 || 黄思远
|-
| 231220179 || 徐钰炜
|-
| 231502022 || 胡骏秋
|-
| 231870127 || 李熠城
|-
| 231870210 || 沈奕齐
|-
| 502024330018 || 胡贵川
|-
| 502024370012 || 胡泽坤
|-
| 502025330006 || 陈俊杰
|-
| 502025330007 || 陈星宇
|-
| 502025330018 || 何平
|-
| 502025330055 || 夏天钰
|-
| 502025330076 || 赵可泰
|-
| 502025330084 || 周一凡
|-
| 502025370010 || 甘东伟
|-
| 502025370014 || 何临哲
|-
| 502025370022 || 李嘉伟
|-
| 502025370028 || 刘亮慧
|-
| 502025370034 || 裴鸣宇
|-
| 502025370060 || 吴璋泰
|-
| 502025370062 || 肖雨辰
|-
| 502025370063 || 许忱
|-
| 522025330028 || 何卓霖
|-
| 522025330048 || 李小涵
|-
| 522025330082 || 沈子杰
|-
| 522025330095 || 王昊田
|-
| 522025330096 || 王敬尧
|-
| 602025330038 || 张峰瑞
|-
| 652024330020 || 沈思
|-
| 652025330005 || 陈煜航
|-
| 652025330001 || 陈瀚
|-
| 652025330009 || 胡伟江
|-
| 652025330013 || 鞠哲
|-
| 652025330029 || 王昕烨
|-
| 652025330030 || 王远博
|-
| 652025330031 || 王在烜
|-
| 652025330033 || 吴文翔
|-
| 652025330034 || 许宝铎
|-
| 652025330043 || 周宇恒
|-
| 652025330045 || 祝永祺
|}
</center>

高级算法 (Fall 2025)

2026-01-16T09:44:37Z

Zhangyiyao: /* Assignments */

{{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。

* '''(2025/12/26)''' Problem Set 3已经发布，文档密码公布于QQ群中。不在QQ群的同学请加入QQ群或邮件联系助教获取密码。

= 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'). [[高级算法 (Fall 2025)/第二次作业提交名单|第二次作业提交名单]]

*[[Media:Advanced_algorithm_2025_HW3.pdf|Problem Set 3]] 请在 2025/01/16 14:00 UTC+8 前提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A3.pdf'). [[高级算法 (Fall 2025)/第三次作业提交名单|第三次作业提交名单]]

= 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)/第三次作业提交名单

2026-01-16T09:43:39Z

Zhangyiyao: Created page with "如有错漏请邮件联系助教. <center> {| class="wikitable" |- ! 学号 !! 姓名 |- | 221502007 || 崔毓泽 |- | 221502008 || 梁今为 |- | 221502013 || 贺龄瑞 |- | 221850037 || 王朝晖 |- | 221900156 || 韩加瑞 |- | 231098067 || 徐浩然 |- | 231220002 || 潘谟天 |- | 231220005 || 樊书岩 |- | 231220007 || 汪文韬 |- | 231220012 || 张启越 |- | 231220019 || 何云天 |- | 231220056 || 黄思远 |- | 231220179 || 徐钰炜 |- | 231240..."

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 221502007 || 崔毓泽
|-
| 221502008 || 梁今为
|-
| 221502013 || 贺龄瑞
|-
| 221850037 || 王朝晖
|-
| 221900156 || 韩加瑞
|-
| 231098067 || 徐浩然
|-
| 231220002 || 潘谟天
|-
| 231220005 || 樊书岩
|-
| 231220007 || 汪文韬
|-
| 231220012 || 张启越
|-
| 231220019 || 何云天
|-
| 231220056 || 黄思远
|-
| 231220179 || 徐钰炜
|-
| 231240019 || 邵与乔
|-
| 231502022 || 胡骏秋
|-
| 231870127 || 李熠城
|-
| 231870210 || 沈奕齐
|-
| 502024330018 || 胡贵川
|-
| 502024370012 || 胡泽坤
|-
| 502025330006 || 陈俊杰
|-
| 502025330007 || 陈星宇
|-
| 502025330018 || 何平
|-
| 502025330055 || 夏天钰
|-
| 502025330076 || 赵可泰
|-
| 502025330084 || 周一凡
|-
| 502025370010 || 甘东伟
|-
| 502025370014 || 何临哲
|-
| 502025370022 || 李嘉伟
|-
| 502025370028 || 刘亮慧
|-
| 502025370034 || 裴鸣宇
|-
| 502025370060 || 吴璋泰
|-
| 502025370062 || 肖雨辰
|-
| 502025370063 || 许忱
|-
| 522025330028 || 何卓霖
|-
| 522025330048 || 李小涵
|-
| 522025330082 || 沈子杰
|-
| 522025330095 || 王昊田
|-
| 522025330096 || 王敬尧
|-
| 602025330038 || 张峰瑞
|-
| 652024330020 || 沈思
|-
| 652025330005 || 陈煜航
|-
| 652025330009 || 胡伟江
|-
| 652025330013 || 鞠哲
|-
| 652025330029 || 王昕烨
|-
| 652025330030 || 王远博
|-
| 652025330031 || 王在烜
|-
| 652025330033 || 吴文翔
|-
| 652025330034 || 许宝铎
|-
| 652025330043 || 周宇恒
|-
| 652025330045 || 祝永祺
|}
</center>

File:Advanced algorithm 2025 HW3.pdf

2026-01-03T09:32:22Z

Zhangyiyao: Zhangyiyao uploaded a new version of File:Advanced algorithm 2025 HW3.pdf

File:Advanced algorithm 2025 HW3.pdf

2025-12-28T05:00:44Z

Zhangyiyao: Zhangyiyao uploaded a new version of File:Advanced algorithm 2025 HW3.pdf

File:Advanced algorithm 2025 HW3.pdf

2025-12-26T14:25:29Z

Zhangyiyao: Zhangyiyao uploaded a new version of File:Advanced algorithm 2025 HW3.pdf

高级算法 (Fall 2025)

2025-12-26T05:09:11Z

Zhangyiyao: /* Assignments */

{{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。

* '''(2025/12/26)''' Problem Set 3已经发布，文档密码公布于QQ群中。不在QQ群的同学请加入QQ群或邮件联系助教获取密码。

= 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'). [[高级算法 (Fall 2025)/第二次作业提交名单|第二次作业提交名单]]

*[[Media:Advanced_algorithm_2025_HW3.pdf|Problem Set 3]] 请在 2025/01/16 14:00 UTC+8 前提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A3.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-12-26T05:06:28Z

Zhangyiyao: /* Announcement */

{{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。

* '''(2025/12/26)''' Problem Set 3已经发布，文档密码公布于QQ群中。不在QQ群的同学请加入QQ群或邮件联系助教获取密码。

= 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'). [[高级算法 (Fall 2025)/第二次作业提交名单|第二次作业提交名单]]

*[[Media:Advanced_algorithm_2025_HW3.pdf|Problem Set 3]] 请在 2025/01/12 14:00 UTC+8 前提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A3.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-12-26T05:06:07Z

Zhangyiyao: /* Announcement */

{{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。

* '''(2025/12/26)''' PS3已经发布，文档密码公布于QQ群中。不在QQ群的同学请加入QQ群或邮件联系助教获取密码。

= 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'). [[高级算法 (Fall 2025)/第二次作业提交名单|第二次作业提交名单]]

*[[Media:Advanced_algorithm_2025_HW3.pdf|Problem Set 3]] 请在 2025/01/12 14:00 UTC+8 前提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A3.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-12-26T05:05:28Z

Zhangyiyao: /* Assignments */

{{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'). [[高级算法 (Fall 2025)/第二次作业提交名单|第二次作业提交名单]]

*[[Media:Advanced_algorithm_2025_HW3.pdf|Problem Set 3]] 请在 2025/01/12 14:00 UTC+8 前提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A3.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.

File:Advanced algorithm 2025 HW3.pdf

2025-12-26T05:01:51Z

Zhangyiyao:

高级算法 (Fall 2025)/Problem Set 3

2025-12-25T14:49:09Z

Zhangyiyao: Blanked the page

高级算法 (Fall 2025)/Problem Set 3

2025-12-25T14:25:11Z

Zhangyiyao: Created page with "*每道题目的解答都要有完整的解题过程，中英文不限。 *我们推荐大家使用LaTeX, markdown等对作业进行排版。 == Problem 1 == Let <math>\mathcal{M} = (E, \mathcal{I})</math> be a matroid with rank function <math>r_{\mathcal{M}} : 2^E \to \mathbb{Z}_{\ge 0}</math>. Prove that <math>r_{\mathcal{M}}</math> is submodular. == Problem 2 == In class, you learned two greedy algorithms with the same framework: * For maximizing a non-negative add..."

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

== Problem 1 ==
Let <math>\mathcal{M} = (E, \mathcal{I})</math> be a matroid with rank function
<math>r_{\mathcal{M}} : 2^E \to \mathbb{Z}_{\ge 0}</math>.
Prove that <math>r_{\mathcal{M}}</math> is submodular.

== Problem 2 ==
In class, you learned two greedy algorithms with the same framework:
* For maximizing a non-negative additive function over a matroid constraint, the greedy algorithm is exact.
* For maximizing a non-negative monotone submodular function under a cardinality constraint, the algorithm gives a <math>(1-1/e)</math>-approximation.

Now we consider a common generalization of both problems: given a matroid
<math>\mathcal{M} = (E, \mathcal{I})</math>
and a non-negative monotone submodular function
<math>f : 2^E \to \mathbb{Z}_{\ge 0}</math>,
find a set <math>A \in \mathcal{I}</math> so as to maximize <math>f(A)</math>.
Consider the same greedy algorithm:

* <math>A \gets \emptyset</math>
* While <math>A</math> is not a base of <math>\mathcal{M}</math>:
*# <math>i^* \gets \arg\max_{i \in E \setminus A : A \cup \{i\} \in \mathcal{I}} f(A \cup \{i\})</math>
*# <math>A \gets A \cup \{i^*\}</math>
* Return <math>A</math>

* (2a) Prove that the algorithm is a <math>1/2</math>-approximation.
* (2b) Show that the approximation ratio of <math>1/2</math> is tight for the algorithm.

Remark: For this problem, a <math>(1-1/e)</math>-approximation is also known, so the greedy algorithm is not optimal.

== Problem 3 ==
Consider the following course selection problem.
We are given a directed acyclic graph <math>G = (V,E)</math>,
where each vertex <math>v \in V</math> represents a course.
Each edge <math>(u,v)</math> indicates that the course <math>u</math> is a prerequisite for course <math>v</math>.
Each vertex <math>v \in V</math> has a weight <math>w_v \in \mathbb{Z}</math>,
which may be positive or negative.
The goal is to choose a maximum-total-weight set <math>S \subseteq V</math>
of courses respecting the precedence constraints:
if <math>v \in S</math>, all prerequisites of <math>v</math> are also in <math>S</math>.

Formulate the problem as a linear program, and show that the optimal solution of the LP is integral.

== Problem 4 ==
Recall that in the maximum coverage problem, we are given a ground set <math>U</math> of <math>n</math> elements,
<math>S_1, S_2, \ldots, S_m \subseteq U</math>,
and an integer <math>k \in [m]</math>.
The goal is to choose a set <math>C \subseteq [m]</math> with <math>|C| = k</math>
that maximizes <math>\left|\bigcup_{i \in C} S_i\right|</math>.

Consider the following linear program relaxation for this problem:

<math>\max \sum_{j \in U} x_j</math>

subject to
<math>
x_j - \sum_{i \in [m] : j \in S_i} y_i \le 0 \quad \forall j \in U \\
y_i \in [0,1] \quad \forall i \in [m]
</math>

* (4a) Show that the value of the LP is at least the value of the original maximum coverage instance.
* (4b) Design a randomized rounding algorithm that, given a solution <math>(x^*, y^*)</math> to the LP,
produces a solution <math>C \subseteq [m]</math> with <math>|C| = k</math> such that
<math>\mathbb{E}\!\left[\left|\bigcup_{i \in C} S_i\right|\right]
\ge \left(1-\frac{1}{e}\right)\sum_{j \in U} x_j^*</math>.
* (4c) Derandomize the algorithm and obtain the same guarantee deterministically.

== Problem 5 ==
Consider the following linear program:

<math>\min \; c^{\mathsf T} x</math>

subject to
<math>
Ax \ge b \\
x_2, x_3, \ldots, x_n \ge 0
</math>

Notice that the variable <math>x_1</math> is free.

* (5a) Convert this LP into standard form.
* (5b) Write the dual of the standard-form LP.
* (5c) Simplify the dual LP.

== Problem 6 ==
Let <math>G = (L,R,E)</math> be a bipartite graph.
Write down the linear program for maximum matching in <math>G</math>,
and the linear program for minimum vertex cover in <math>G</math>.
Prove that the size of the maximum matching equals the size of the minimum vertex cover.

== Problem 7 ==
In the maximum 2-SAT problem, we are given <math>n</math> boolean variables
<math>x_1,\ldots,x_n</math> and <math>m</math> clauses,
each clause being the disjunction of two literals.
Design a <math>0.878</math>-approximation algorithm using SDP.

== Problem 8 ==
In binary classification, we are given a dataset <math>\mathcal{D}</math> of <math>n</math> points
and an unknown labeling <math>h : \mathcal{D} \to \{-1,1\}</math>.
There is a family of classifiers <math>\{f_1,\ldots,f_M\}</math>
and a weak learner that outputs a classifier correct on at least <math>51\%</math> of the weighted data.

* (8a) Show that there exists <math>\alpha \in \mathbb{R}_{\ge 0}^M</math> such that
<math>h(j) = \mathrm{sgn}\!\left(\sum_{i=1}^M \alpha_i f_i(j)\right)</math>.
* (8b) Give a polynomial-time algorithm to compute such an <math>\alpha</math>.

== Problem 9 ==
Let <math>\mathcal{P}_1, \mathcal{P}_2 \subseteq \mathbb{R}^n</math> be polytopes.
Define
<math>
\mathrm{conv}(\mathcal{P}_1,\mathcal{P}_2)
= \{\alpha_1 x^{(1)} + \alpha_2 x^{(2)} :
x^{(1)} \in \mathcal{P}_1,\;
x^{(2)} \in \mathcal{P}_2,\;
\alpha_1,\alpha_2 \ge 0,\;
\alpha_1+\alpha_2=1\}.
</math>
Prove that
<math>\mathrm{xc}(\mathrm{conv}(\mathcal{P}_1,\mathcal{P}_2))
\le \mathrm{xc}(\mathcal{P}_1)+\mathrm{xc}(\mathcal{P}_2)</math>.

== Problem 10 ==
We analyze the following algorithm for finding a cut in triangle-free graphs of maximum degree <math>d</math>.

* (1) Sample a cut <math>(S,\bar S)</math> uniformly at random.
* (2) Label a vertex happy if more than half of its neighboring edges are cut.
* (3) If exactly half are cut, label it happy with probability <math>1/2</math>.
* (4) Otherwise label it unhappy.
* (5) Keep happy vertices fixed; each unhappy vertex switches sides with probability <math>1/2</math>.
* (6) Output the resulting cut.

Fix an edge <math>(u,v)</math>.

* (a) Define <math>p</math> and <math>q</math> as in the description and show
<math>\Pr[(u,v)\text{ is cut}] = \frac12 + \frac{p-q}{2}</math>.
* (b) Define <math>q_u,q_v</math> and show <math>q=\frac12 q_u q_v</math>.
* (c) Define <math>p_u,p_v</math> and show <math>p=\frac12 p_u p_v</math>.
* (d) Show <math>p_u+q_u=1</math>, <math>p_v+q_v=1</math> and derive the final expression.
* (e) Compute <math>p_u</math> and estimate the improvement.

HINT:
<math>{d \choose \lfloor d/2 \rfloor}
= \Omega\!\left(\frac{2^d}{\sqrt d}\right)</math>.

高级算法 (Fall 2025)/第二次作业提交名单

2025-12-08T02:55:27Z

Zhangyiyao:

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 221502007 || 崔毓泽
|-
| 221502008 || 梁今为
|-
| 221502013 || 贺龄瑞
|-
| 221502018 || 陈正道
|-
| 221850037 || 王朝晖
|-
| 221900156 || 韩加瑞
|-
| 231098067 || 徐浩然
|-
| 231220002 || 潘谟天
|-
| 231220005 || 樊书岩
|-
| 231220007 || 汪文韬
|-
| 231220012 || 张启越
|-
| 231220019 || 何云天
|-
| 231220056 || 黄思远
|-
| 231220179 || 徐钰炜
|-
| 231502022 || 胡骏秋
|-
| 231870127 || 李熠城
|-
| 231870210 || 沈奕齐
|-
| 502024330018 || 胡贵川
|-
| 502024370012 || 胡泽坤
|-
| 502025330006 || 陈俊杰
|-
| 502025330007 || 陈星宇
|-
| 502025330018 || 何平
|-
| 502025330055 || 夏天钰
|-
| 502025330076 || 赵可泰
|-
| 502025330084 || 周一凡
|-
| 502025370010 || 甘东伟
|-
| 502025370014 || 何临哲
|-
| 502025370022 || 李嘉伟
|-
| 502025370028 || 刘亮慧
|-
| 502025370034 || 裴鸣宇
|-
| 502025370060 || 吴璋泰
|-
| 502025370062 || 肖雨辰
|-
| 502025370063 || 许忱
|-
| 522025330028 || 何卓霖
|-
| 522025330048 || 李小涵
|-
| 522025330082 || 沈子杰
|-
| 522025330095 || 王昊田
|-
| 522025330096 || 王敬尧
|-
| 602025330038 || 张峰瑞
|-
| 652024330020 || 沈思
|-
| 652025330001 || 陈瀚
|-
| 652025330009 || 胡伟江
|-
| 652025330013 || 鞠哲
|-
| 652025330029 || 王昕烨
|-
| 652025330030 || 王远博
|-
| 652025330031 || 王在烜
|-
| 652025330033 || 吴文翔
|-
| 652025330034 || 许宝铎
|-
| 652025330043 || 周宇恒
|-
| 652025330045 || 祝永祺
|}
</center>

高级算法 (Fall 2025)

2025-12-01T15:07:40Z

Zhangyiyao: /* Assignments */

{{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'). [[高级算法 (Fall 2025)/第二次作业提交名单|第二次作业提交名单]]

= 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-12-01T15:04:46Z

Zhangyiyao: Created page with "如有错漏请邮件联系助教. <center> {| class="wikitable" |- ! 学号 !! 姓名 |- | 221502007 || 崔毓泽 |- | 221502008 || 梁今为 |- | 221502013 || 贺龄瑞 |- | 221502018 || 陈正道 |- | 221850037 || 王朝晖 |- | 221900156 || 韩加瑞 |- | 231098067 || 徐浩然 |- | 231220002 || 潘谟天 |- | 231220005 || 樊书岩 |- | 231220007 || 汪文韬 |- | 231220012 || 张启越 |- | 231220019 || 何云天 |- | 231220056 || 黄思远 |- | 231220..."

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 221502007 || 崔毓泽
|-
| 221502008 || 梁今为
|-
| 221502013 || 贺龄瑞
|-
| 221502018 || 陈正道
|-
| 221850037 || 王朝晖
|-
| 221900156 || 韩加瑞
|-
| 231098067 || 徐浩然
|-
| 231220002 || 潘谟天
|-
| 231220005 || 樊书岩
|-
| 231220007 || 汪文韬
|-
| 231220012 || 张启越
|-
| 231220019 || 何云天
|-
| 231220056 || 黄思远
|-
| 231220179 || 徐钰炜
|-
| 231502022 || 胡骏秋
|-
| 231870127 || 李熠城
|-
| 502024330018 || 胡贵川
|-
| 502024370012 || 胡泽坤
|-
| 502025330006 || 陈俊杰
|-
| 502025330007 || 陈星宇
|-
| 502025330018 || 何平
|-
| 502025330055 || 夏天钰
|-
| 502025330076 || 赵可泰
|-
| 502025330084 || 周一凡
|-
| 502025370010 || 甘东伟
|-
| 502025370014 || 何临哲
|-
| 502025370022 || 李嘉伟
|-
| 502025370028 || 刘亮慧
|-
| 502025370034 || 裴鸣宇
|-
| 502025370060 || 吴璋泰
|-
| 502025370062 || 肖雨辰
|-
| 502025370063 || 许忱
|-
| 522025330028 || 何卓霖
|-
| 522025330048 || 李小涵
|-
| 522025330082 || 沈子杰
|-
| 522025330095 || 王昊田
|-
| 522025330096 || 王敬尧
|-
| 602025330038 || 张峰瑞
|-
| 652024330020 || 沈思
|-
| 652025330001 || 陈瀚
|-
| 652025330009 || 胡伟江
|-
| 652025330013 || 鞠哲
|-
| 652025330030 || 王远博
|-
| 652025330031 || 王在烜
|-
| 652025330033 || 吴文翔
|-
| 652025330034 || 许宝铎
|-
| 652025330043 || 周宇恒
|-
| 652025330045 || 祝永祺
|}
</center>

高级算法 (Fall 2025)/第一次作业提交名单

2025-11-10T08:20:28Z

Zhangyiyao:

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 221502007 || 崔毓泽
|-
| 221502008 || 梁今为
|-
| 221502013 || 贺龄瑞
|-
| 221502018 || 陈正道
|-
| 221850037 || 王朝晖
|-
| 221900156 || 韩加瑞
|-
| 231098067 || 徐浩然
|-
| 231220002 || 潘谟天
|-
| 231220005 || 樊书岩
|-
| 231220007 || 汪文韬
|-
| 231220012 || 张启越
|-
| 231220019 || 何云天
|-
| 231220056 || 黄思远
|-
| 231220179 || 徐钰炜
|-
| 231502022 || 胡骏秋
|-
| 231870127 || 李熠城
|-
| 231870210 || 沈奕齐
|-
| 502024330018 || 胡贵川
|-
| 502024370012 || 胡泽坤
|-
| 502025330006 || 陈俊杰
|-
| 502025330007 || 陈星宇
|-
| 502025330018 || 何平
|-
| 502025330055 || 夏天钰
|-
| 502025330076 || 赵可泰
|-
| 502025330084 || 周一凡
|-
| 502025370010 || 甘东伟
|-
| 502025370014 || 何临哲
|-
| 502025370022 || 李嘉伟
|-
| 502025370028 || 刘亮慧
|-
| 502025370034 || 裴鸣宇
|-
| 502025370060 || 吴璋泰
|-
| 502025370062 || 肖雨辰
|-
| 502025370063 || 许忱
|-
| 522025330028 || 何卓霖
|-
| 522025330048 || 李小涵
|-
| 522025330082 || 沈子杰
|-
| 522025330095 || 王昊田
|-
| 522025330096 || 王敬尧
|-
| 602025330038 || 张峰瑞
|-
| 652024330020 || 沈思
|-
| 652025330001 || 陈瀚
|-
| 652025330005 || 陈煜航
|-
| 652025330009 || 胡伟江
|-
| 652025330013 || 鞠哲
|-
| 652025330029 || 王昕烨
|-
| 652025330030 || 王远博
|-
| 652025330031 || 王在烜
|-
| 652025330033 || 吴文翔
|-
| 652025330034 || 许宝铎
|-
| 652025330043 || 周宇恒
|-
| 652025330045 || 祝永祺
|}
</center>

高级算法 (Fall 2025)

2025-11-10T08:10:43Z

Zhangyiyao: /* Assignments */

{{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]])

= 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)/Problem Set 2

2025-11-10T06:05:32Z

Zhangyiyao: /* Problem 3 (Random walk on graph) */

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

== Problem 1 (Adjacency matrix) ==

Let <math>A</math> be the adjacency matrix of an undirected connected graph <math>G</math>, and <math>\alpha_1</math> be its largest eigenvalue.
* ['''Lowerbounding <math>\alpha_1</math>'''] We proved <math>\alpha_1 \le d_{\mathrm{max}}</math> in class. Show that <math>\alpha_1 \ge d_{\mathrm{avg}}</math> where <math>d_{\mathrm{avg}}:=\frac{2|E|}{|V|}</math> is the average degree of the graph.

* ['''Monotonicity of the spectrum'''] Let <math>A'</math> be the adjacency matrix of any subgraph of <math>A</math> produced by deleting vertices, and let <math>\alpha_1'</math> be the largest eigenvalue of <math>A'</math>. Show that <math>\alpha'_1\leq \alpha_1</math>.

* ['''Chromatic number'''] The chromatic number <math>\chi(G)</math> of a graph is the smallest number of colors needed to color the vertices of <math>G</math> so that no two adjacent vertices share same color. Prove that <math>\chi(G) \le \lfloor \alpha_1 \rfloor +1</math>.

== Problem 2 (Graph Laplacian) ==
* ['''Spectrum of special graphs'''] Find eigenvalues of the Laplacian matrices of the following graphs:
*# The complete graph with <math>n</math> vertices.
*# The [[wikipedia:Star_(graph_theory)|star graph]] with <math>n</math> vertices.

*['''Number of connected components'''] Let <math>G</math> be an undirected graph, and <math>\lambda_1\le \lambda_2 \le \ldots \le \lambda_n</math> be the eigenvalues of its Laplacian matrix <math>{L}</math>. Prove that <math>\lambda_k = 0</math> if and only if <math>G</math> has at least <math>k</math> connected components.

*['''Lowerbounding <math>\lambda_2</math>'''] Let <math>G</math> be an undirected graph whose Laplacian is <math>L</math>, with second-smallest eigenvalue <math>\lambda_2</math>. We know that if <math>G</math> is connected then <math>\lambda_2>0</math>. Prove that <math>\lambda_2 \geq \Omega\left(\frac{1}{rn}\right) \geq \Omega(1/n^2)</math> by analyzing the Rayleigh quotient on all test vectors <math>x\perp \mathbf{1}</math>. Here, <math>r</math> is the ''diameter'' of the graph (i.e. the maximum shortest-path distance between pairs of vertices in the graph). Further, show that when <math>G</math> is simple and <math>d</math>-regular, we have <math>\lambda_2 \geq \Omega(d/n^2)</math>.

== Problem 3 (Random walk on graph) ==
In class, we showed that large conductance implies rapid mixing of random walks. In this problem, we show that this is also necessary to some extent.

Consider an undirected, unweighted graph <math>G = (V,E)</math> with <math>|V|=n</math>. Let <math>\pi</math> be the stationary distribution of the simple random walk on <math>V</math>.

(1) Prove that the conductance <math>\phi(S)</math> can be interpreted as <math>\mathbf{Pr}{ [X_1 \not\in S | X_0 \sim \pi_S ] }</math>, the probability that a random walk started at <math>X_0</math> drawn according to <math>\pi</math> restricted to <math>S</math>, escapes from <math>S</math> in one step.

(2) Further, if <math>G</math> is a regular graph and the adjacency matrix <math>A</math> of <math>G</math> is positive semi-definite (PSD), show that <math>\mathbf{Pr}{[X_t \in S | X_0 \sim \pi_S]} \ge (1- \phi(S))^t</math> for all <math>t\geq 1</math> and <math>t\in \mathbb{N}</math>. (Hint:first show that <math>\langle x,A^t x \rangle\geq \langle x,Ax \rangle^t</math> for any unit vector <math>x</math> and any PSD matrix <math>A</math>.)

(3) The <math>\ell_2</math> mixing time of the random walk over <math>n</math> items with distribution <math>\{p^{(t)}\}_{t\geq 0}</math> is defined as the smallest <math>t</math> such that
:<math>\left\|\frac{p^{(t)}}{\pi} - 1\right\|_{2,\pi}^2 :=\sum_{i=1}^n \pi_i \left(\frac{p_i^{(t)}}{\pi_i} - 1\right)^2 \leq \frac{1}{4}, \quad \forall p^{(0)}.</math>
In the context of (2), suppose there exists a <math>S\subseteq V</math> such that <math>\pi(S) :=\sum_{v\in S}\pi(v) = \frac{1}{\sqrt{n}}</math>, then show that <math>\ell_2</math> mixing time of <math>\{X_i\}_{i\geq 0}</math> is at least <math>\Omega\left(\frac{\log(n)}{\phi(S)}\right)</math> if <math>{\phi(S)}\ll 1</math>.

== Problem 4 (MCMC and coupling) ==

In this problem, you will analyze the MCMC sampler over independent sets of a fixed size <math>k</math>. Given a graph <math>G=(V,E)</math> with maximum degree <math>\Delta</math>, let <math>I_k</math> be the set of all independent sets in <math>G</math> of size <math>k</math>. Consider a random walk <math>\{X_i\}_{i\geq 0}</math> on <math>I_k</math> defined by the following process:

* choose a vertex <math>v\in X_t</math> uniformly at random and a vertex <math>w\in V</math> uniformly at random;

* if <math>w\notin X_t</math> and <math>X_t - \{v\} + \{w\}</math> is independent, <math>X_{t+1} = X_t - \{v\} + \{w\}</math>;

* otherwise, <math>X_{t+1} = X_t</math>.

Use coupling argument to show that if <math>k\leq \frac{n}{3\Delta + 3}</math>, then the <math>\epsilon</math>-mixing time of <math>\{X_i\}_{(i\geq 0)}</math> is a polynomial in <math>n</math> and <math>\log(1/\epsilon)</math>.

== Problem 5 (Cheeger’s Inequality) ==

Let <math>G=(V,E)</math> be a <math>d</math>-regular graph. Let <math>S, T, U</math> be a partition of the vertex set <math>V</math> with <math>|S| \le |T|</math> and <math>|U| \le \epsilon \min\{|S|,|T|\}</math>. We define the projected expansion by <math>\phi_G(S,T\|U) := E(S,T)/(d|S|)</math>. Let <math>\lambda_2</math> be the second smallest eigenvalue of the normalized Laplacian <math>\mathcal{L} := (D-A)/d</math>. Show that for every <math>\epsilon > 0</math>, there exists an efficient algorithm that finds sets <math>S</math>, <math>T</math>, <math>U</math> such that <math>|S| \le |T|</math>, <math>|U| \le \epsilon \min\{|S|,|T|\}</math>, and <math>\phi_G(S,T\|U) \le O(\lambda_2 / \epsilon)</math>.

高级算法 (Fall 2025)

2025-11-10T06:01:16Z

Zhangyiyao: /* Assignments */

{{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]] 请在 TBD 提交到 [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]])

= 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)/Problem Set 2

2025-11-10T05:27:49Z

Zhangyiyao: Created page with "*每道题目的解答都要有完整的解题过程，中英文不限。 *我们推荐大家使用LaTeX, markdown等对作业进行排版。 == Problem 1 (Adjacency matrix) == Let <math>A</math> be the adjacency matrix of an undirected connected graph <math>G</math>, and <math>\alpha_1</math> be its largest eigenvalue. * ['''Lowerbounding <math>\alpha_1</math>'''] We proved <math>\alpha_1 \le d_{\mathrm{max}}</math> in class. Show that <math>\alpha_1 \ge d_{\mathrm{..."

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

== Problem 1 (Adjacency matrix) ==

Let <math>A</math> be the adjacency matrix of an undirected connected graph <math>G</math>, and <math>\alpha_1</math> be its largest eigenvalue.
* ['''Lowerbounding <math>\alpha_1</math>'''] We proved <math>\alpha_1 \le d_{\mathrm{max}}</math> in class. Show that <math>\alpha_1 \ge d_{\mathrm{avg}}</math> where <math>d_{\mathrm{avg}}:=\frac{2|E|}{|V|}</math> is the average degree of the graph.

* ['''Monotonicity of the spectrum'''] Let <math>A'</math> be the adjacency matrix of any subgraph of <math>A</math> produced by deleting vertices, and let <math>\alpha_1'</math> be the largest eigenvalue of <math>A'</math>. Show that <math>\alpha'_1\leq \alpha_1</math>.

* ['''Chromatic number'''] The chromatic number <math>\chi(G)</math> of a graph is the smallest number of colors needed to color the vertices of <math>G</math> so that no two adjacent vertices share same color. Prove that <math>\chi(G) \le \lfloor \alpha_1 \rfloor +1</math>.

== Problem 2 (Graph Laplacian) ==
* ['''Spectrum of special graphs'''] Find eigenvalues of the Laplacian matrices of the following graphs:
*# The complete graph with <math>n</math> vertices.
*# The [[wikipedia:Star_(graph_theory)|star graph]] with <math>n</math> vertices.

*['''Number of connected components'''] Let <math>G</math> be an undirected graph, and <math>\lambda_1\le \lambda_2 \le \ldots \le \lambda_n</math> be the eigenvalues of its Laplacian matrix <math>{L}</math>. Prove that <math>\lambda_k = 0</math> if and only if <math>G</math> has at least <math>k</math> connected components.

*['''Lowerbounding <math>\lambda_2</math>'''] Let <math>G</math> be an undirected graph whose Laplacian is <math>L</math>, with second-smallest eigenvalue <math>\lambda_2</math>. We know that if <math>G</math> is connected then <math>\lambda_2>0</math>. Prove that <math>\lambda_2 \geq \Omega\left(\frac{1}{rn}\right) \geq \Omega(1/n^2)</math> by analyzing the Rayleigh quotient on all test vectors <math>x\perp \mathbf{1}</math>. Here, <math>r</math> is the ''diameter'' of the graph (i.e. the maximum shortest-path distance between pairs of vertices in the graph). Further, show that when <math>G</math> is simple and <math>d</math>-regular, we have <math>\lambda_2 \geq \Omega(d/n^2)</math>.

== Problem 3 (Random walk on graph) ==
In class, we showed that large conductance implies rapid mixing of random walks. In this problem, we show that this is also necessary to some extent.

Consider an undirected, unweighted graph <math>G = (V,E)</math> with <math>|V|=n</math>. Let <math>\pi</math> be the stationary distribution of the simple random walk on <math>V</math>.

(1) Prove that the conductance <math>\phi(S)</math> can be interpreted as <math>\mathbf{Pr}{ [X_1 \not\in S | X_0 \sim \pi_S ] }</math>, the probability that a random walk started at <math>X_0</math> drawn according to <math>\pi</math> restricted to <math>S</math>, escapes from <math>S</math> in one step.

(2) Further, if <math>G</math> is a regular graph and the adjacency matrix <math>A</math> of <math>G</math> is positive semi-definite (PSD), show that <math>\mathbf{Pr}{[X_t \in S | X_0 \sim \pi_S]} \ge (1- \phi(S))^t</math> for all <math>t\geq 1</math> and <math>t\in \mathbb{N}</math>. (Hint:first show that <math>\langle x,A^t x \rangle\geq \langle x,Ax \rangle^t</math> if <math>A</math> is PSD.)

(3) The <math>\ell_2</math> mixing time of the random walk over <math>n</math> items with distribution <math>\{p^{(t)}\}_{t\geq 0}</math> is defined as the smallest <math>t</math> such that
:<math>\left\|\frac{p^{(t)}}{\pi} - 1\right\|_{2,\pi}^2 :=\sum_{i=1}^n \pi_i \left(\frac{p_i^{(t)}}{\pi_i} - 1\right)^2 \leq \frac{1}{4}, \quad \forall p^{(0)}.</math>
In the context of (2), suppose there exists a <math>S\subseteq V</math> such that <math>\pi(S) :=\sum_{v\in S}\pi(v) = \frac{1}{\sqrt{n}}</math>, then show that <math>\ell_2</math> mixing time of <math>\{X_i\}_{i\geq 0}</math> is at least <math>\Omega\left(\frac{\log(n)}{\phi(S)}\right)</math> if <math>{\phi(S)}\ll 1</math>.

== Problem 4 (MCMC and coupling) ==

In this problem, you will analyze the MCMC sampler over independent sets of a fixed size <math>k</math>. Given a graph <math>G=(V,E)</math> with maximum degree <math>\Delta</math>, let <math>I_k</math> be the set of all independent sets in <math>G</math> of size <math>k</math>. Consider a random walk <math>\{X_i\}_{i\geq 0}</math> on <math>I_k</math> defined by the following process:

* choose a vertex <math>v\in X_t</math> uniformly at random and a vertex <math>w\in V</math> uniformly at random;

* if <math>w\notin X_t</math> and <math>X_t - \{v\} + \{w\}</math> is independent, <math>X_{t+1} = X_t - \{v\} + \{w\}</math>;

* otherwise, <math>X_{t+1} = X_t</math>.

Use coupling argument to show that if <math>k\leq \frac{n}{3\Delta + 3}</math>, then the <math>\epsilon</math>-mixing time of <math>\{X_i\}_{(i\geq 0)}</math> is a polynomial in <math>n</math> and <math>\log(1/\epsilon)</math>.

== Problem 5 (Cheeger’s Inequality) ==

Let <math>G=(V,E)</math> be a <math>d</math>-regular graph. Let <math>S, T, U</math> be a partition of the vertex set <math>V</math> with <math>|S| \le |T|</math> and <math>|U| \le \epsilon \min\{|S|,|T|\}</math>. We define the projected expansion by <math>\phi_G(S,T\|U) := E(S,T)/(d|S|)</math>. Let <math>\lambda_2</math> be the second smallest eigenvalue of the normalized Laplacian <math>\mathcal{L} := (D-A)/d</math>. Show that for every <math>\epsilon > 0</math>, there exists an efficient algorithm that finds sets <math>S</math>, <math>T</math>, <math>U</math> such that <math>|S| \le |T|</math>, <math>|U| \le \epsilon \min\{|S|,|T|\}</math>, and <math>\phi_G(S,T\|U) \le O(\lambda_2 / \epsilon)</math>.

高级算法 (Fall 2025)/第一次作业提交名单

2025-10-31T01:52:49Z

Zhangyiyao:

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 221502007 || 崔毓泽
|-
| 221502008 || 梁今为
|-
| 221502013 || 贺龄瑞
|-
| 221502018 || 陈正道
|-
| 221850037 || 王朝晖
|-
| 221900156 || 韩加瑞
|-
| 231098067 || 徐浩然
|-
| 231220002 || 潘谟天
|-
| 231220005 || 樊书岩
|-
| 231220007 || 汪文韬
|-
| 231220012 || 张启越
|-
| 231220019 || 何云天
|-
| 231220056 || 黄思远
|-
| 231220179 || 徐钰炜
|-
| 231502022 || 胡骏秋
|-
| 231870127 || 李熠城
|-
| 502024330018 || 胡贵川
|-
| 502024370012 || 胡泽坤
|-
| 502025330006 || 陈俊杰
|-
| 502025330007 || 陈星宇
|-
| 502025330018 || 何平
|-
| 502025330055 || 夏天钰
|-
| 502025330076 || 赵可泰
|-
| 502025330084 || 周一凡
|-
| 502025370010 || 甘东伟
|-
| 502025370014 || 何临哲
|-
| 502025370022 || 李嘉伟
|-
| 502025370028 || 刘亮慧
|-
| 502025370034 || 裴鸣宇
|-
| 502025370060 || 吴璋泰
|-
| 502025370062 || 肖雨辰
|-
| 502025370063 || 许忱
|-
| 522025330028 || 何卓霖
|-
| 522025330048 || 李小涵
|-
| 522025330082 || 沈子杰
|-
| 522025330095 || 王昊田
|-
| 522025330096 || 王敬尧
|-
| 602025330038 || 张峰瑞
|-
| 652024330020 || 沈思
|-
| 652025330001 || 陈瀚
|-
| 652025330005 || 陈煜航
|-
| 652025330009 || 胡伟江
|-
| 652025330013 || 鞠哲
|-
| 652025330029 || 王昕烨
|-
| 652025330030 || 王远博
|-
| 652025330031 || 王在烜
|-
| 652025330033 || 吴文翔
|-
| 652025330034 || 许宝铎
|-
| 652025330043 || 周宇恒
|-
| 652025330045 || 祝永祺
|}
</center>

高级算法 (Fall 2025)

2025-10-30T06:29:58Z

Zhangyiyao: /* Assignments */

{{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)/第一次作业提交名单|第一次作业提交名单]]

= 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]

= 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-10-30T06:28:31Z

Zhangyiyao:

<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 221502007 || 崔毓泽
|-
| 221502008 || 梁今为
|-
| 221502013 || 贺龄瑞
|-
| 221502018 || 陈正道
|-
| 221850037 || 王朝晖
|-
| 221900156 || 韩加瑞
|-
| 231098067 || 徐浩然
|-
| 231220002 || 潘谟天
|-
| 231220005 || 樊书岩
|-
| 231220007 || 汪文韬
|-
| 231220012 || 张启越
|-
| 231220019 || 何云天
|-
| 231220056 || 黄思远
|-
| 231220179 || 徐钰炜
|-
| 231502022 || 胡骏秋
|-
| 231870127 || 李熠城
|-
| 502024330018 || 胡贵川
|-
| 502024370012 || 胡泽坤
|-
| 502025330006 || 陈俊杰
|-
| 502025330007 || 陈星宇
|-
| 502025330018 || 何平
|-
| 502025330055 || 夏天钰
|-
| 502025330076 || 赵可泰
|-
| 502025330084 || 周一凡
|-
| 502025370010 || 甘东伟
|-
| 502025370014 || 何临哲
|-
| 502025370022 || 李嘉伟
|-
| 502025370028 || 刘亮慧
|-
| 502025370034 || 裴鸣宇
|-
| 502025370060 || 吴璋泰
|-
| 502025370062 || 肖雨辰
|-
| 502025370063 || 许忱
|-
| 522025330028 || 何卓霖
|-
| 522025330048 || 李小涵
|-
| 522025330082 || 沈子杰
|-
| 522025330095 || 王昊田
|-
| 522025330096 || 王敬尧
|-
| 652024330020 || 沈思
|-
| 652025330001 || 陈瀚
|-
| 652025330005 || 陈煜航
|-
| 652025330009 || 胡伟江
|-
| 652025330013 || 鞠哲
|-
| 652025330029 || 王昕烨
|-
| 652025330030 || 王远博
|-
| 652025330031 || 王在烜
|-
| 652025330033 || 吴文翔
|-
| 652025330034 || 许宝铎
|-
| 652025330043 || 周宇恒
|-
| 652025330045 || 祝永祺
|}
</center>

高级算法 (Fall 2025)/第一次作业提交名单

2025-10-30T06:22:01Z

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 221502007 || 崔毓泽
|-
| 221502008 || 梁今为
|-
| 221502013 || 贺龄瑞
|-
| 221502018 || 陈正道
|-
| 221850037 || 王朝晖
|-
| 221900156 || 韩加瑞
|-
| 231098067 || 徐浩然
|-
| 231220002 || 潘谟天
|-
| 231220005 || 樊书岩
|-
| 231220007 || 汪文韬
|-
| 231220012 || 张启越
|-
| 231220019 || 何云天
|-
| 231220056 || 黄思远
|-
| 231220179 || 徐钰炜
|-
| 231502022 || 胡骏秋
|-
| 231870127 || 李熠城
|-
| 502024330018 || 胡贵川
|-
| 502024370012 || 胡泽坤
|-
| 502025330006 || 陈俊杰
|-
| 502025330007 || 陈星宇
|-
| 502025330018 || 何平
|-
| 502025330055 || 夏天钰
|-
| 502025330076 || 赵可泰
|-
| 502025330084 || 周一凡
|-
| 502025370010 || 甘东伟
|-
| 502025370014 || 何临哲
|-
| 502025370022 || 李嘉伟
|-
| 502025370028 || 刘亮慧
|-
| 502025370034 || 裴鸣宇
|-
| 502025370060 || 吴璋泰
|-
| 502025370062 || 肖雨辰
|-
| 502025370063 || 许忱
|-
| 522025330048 || 李小涵
|-
| 522025330082 || 沈子杰
|-
| 522025330095 || 王昊田
|-
| 522025330096 || 王敬尧
|-
| 652024330020 || 沈思
|-
| 652025330001 || 陈瀚
|-
| 652025330005 || 陈煜航
|-
| 652025330009 || 胡伟江
|-
| 652025330013 || 鞠哲
|-
| 652025330029 || 王昕烨
|-
| 652025330030 || 王远博
|-
| 652025330031 || 王在烜
|-
| 652025330033 || 吴文翔
|-
| 652025330034 || 许宝铎
|-
| 652025330043 || 周宇恒
|-
| 652025330045 || 祝永祺
|}
</center>

高级算法 (Fall 2025)/Problem Set 1

2025-10-07T06:53:39Z

Zhangyiyao:

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

== Problem 1 (s–t Min-Cut) ==
Consider adapting Karger's min-cut algorithm to the problem of finding an <math>s</math>–<math>t</math> min-cut in an undirected graph. In this problem, we are given an undirected graph <math>G</math> together with two distinguished vertices <math>s</math> and <math>t</math>. An <math>s</math>–<math>t</math> min-cut is a set of edges whose removal disconnects <math>s</math> from <math>t</math>; we seek an edge set of minimum cardinality.

As the algorithm proceeds, the vertex <math>s</math> may get amalgamated into a new vertex as the result of an edge being contracted; we call this vertex the <math>s</math>-vertex (initially <math>s</math> itself). Similarly, we have a <math>t</math>-vertex. As we run the contraction algorithm, we enforce that we never contract an edge between the <math>s</math>-vertex and the <math>t</math>-vertex.

(a) Show that there are graphs (not multi-graphs) in which the probability that this algorithm finds an <math>s</math>–<math>t</math> min-cut is exponentially small.

(b) How large (asymptotically) can the number of <math>s</math>–<math>t</math> min-cuts in a graph be?

== Problem 2 (Count Sketch) ==
In class we learned about the Count-Min sketch. We saw that it could be used to estimate the frequency of any item in our stream up to an additive error <math>\epsilon \lVert \mathbf{x} \rVert_1</math>, where <math>\lVert \mathbf{x} \rVert_1 = n</math> is the total number of elements streamed in.

In this problem, we'll analyze an alternative algorithm that requires a bit more space, but can estimate the value of <math>x_i</math> to within error <math>\epsilon \lVert \mathbf{x} \rVert_2</math>, which is often much better in practice.

We'll analyze the following procedure:

* For a small value <math>q</math> to be set later, choose a random hash function <math>h(\cdot)</math> that maps every <math>i \in \{1, \dots, N\}</math> to <math>\{1, \dots, q\}</math>. Choose another random hash function <math>g(\cdot)</math> that maps every <math>i \in \{1, \dots, N\}</math> to <math>\{-1, 1\}</math>. Allocate space for <math>q</math> counters <math>C_1, \dots, C_q</math> (all initialized to 0).

* When <math>\mathsf{Increment}(x_i)</math> is called, set <math>C_{h(i)} \leftarrow C_{h(i)} + g(i)</math>.

* When <math>\mathsf{Estimate}(x_i)</math> is called, return <math>y_i = g(i) C_{h(i)}</math>.

Now answer the following:

(a) Show that <math>\mathbb{E}[y_i] = x_i</math>. In other words, show that our estimate for <math>x_i</math> is correct in expectation.

(b) Show that <math>\mathrm{Var}[y_i] \leq \frac{\lVert \mathbf{x} \rVert_2^2}{q}</math>.

(c) What value of <math>q</math> would we need to ensure that we obtain <math>\epsilon</math> error with probability 9/10? How many counters do we need to store in comparison to Count-Min?

== Problem 3 (Concentration of Measure I) ==
Let <math>P, Q</math> be two probability distributions on a finite set <math>\mathcal{X}</math>, with probability mass functions <math>p(x)</math> and <math>q(x)</math>. Let <math>U_1, \dots, U_n</math> be i.i.d. samples from <math>P</math>, and <math>V_1, \dots, V_n</math> be i.i.d. samples from <math>Q</math>. Define the log-likelihood ratio transforms

<math>
X_i = \log \frac{p(U_i)}{q(U_i)},
\qquad
Y_i = \log \frac{p(V_i)}{q(V_i)}.
</math>

Also define

<math>
D_{1/2}(P\|Q) = -2 \log \sum_{x\in \mathcal{X}} \sqrt{p(x)q(x)}.
</math>

Show that

<math>
\Pr\!\left(\sum_{i=1}^n X_i \le \sum_{i=1}^n Y_i\right)
\;\le\; \exp\!\left(-n D_{1/2}(P\|Q)\right).
</math>

== Problem 4 (Concentration of Measure II) ==
Consider the Erdős–Rényi random graph <math>G(n, p)</math>, where every two vertices in the graph are connected randomly and independently with probability <math>p</math>. We denote <math>G \sim G(n, p)</math> if <math>G</math> is generated in this way. We define <math>d := (n - 1) p</math> as the expected degree of the random graph.

(a) For <math>0 < p_1 < p_2 < 1</math>, let <math>G_1 \sim G(n, p_1)</math> and let <math>G_2 \sim G(n, p_2)</math>. Let <math>\Delta(G)</math> be the maximum degree of the graph <math>G</math>. Compare <math>\mathbf{E}[\Delta(G_1)]</math> and <math>\mathbf{E}[\Delta(G_2)]</math> and prove it.

(b) Consider a random graph <math>G \sim G(n, p)</math> with expected degrees <math>d = O(1)</math>. Show that for sufficiently large <math>n</math>, with probability at least 0.9, all vertices of <math>G</math> have degrees <math>O\!\big(\tfrac{\log n}{\log \log n}\big)</math>.

(c) Consider a random graph <math>G \sim G(n, p)</math> with expected degrees <math>d = o(\log n)</math>. Show that for sufficiently large <math>n</math>, with probability at least 0.9, there exists a vertex in <math>G</math> with degree at least <math>10 d</math>.

== Problem 5 (Dimension Reduction) ==

['''Inner product''']
Fix parameters <math>d > 0</math> and <math>\delta, \epsilon \in (0,1)</math>. Let <math>A \in \mathbb{R}^{k \times d}</math> be a random matrix with <math>k = O(\log(1/\delta) / \epsilon^2)</math> rows, and the entries of <math>A</math> are chosen i.i.d. from a Gaussian distribution with mean 0 and variance <math>1/k</math>. Prove that for any <math> x, y \in \mathbb{R}^d </math>, <math> \big|x^\top y - (Ax)^\top(Ay)\big| \leq \epsilon(\lVert x \rVert_2^2 + \lVert y \rVert_2^2)</math> holds with probability at least <math> 1 - \delta </math>.

['''Linear Separability''']
In machine learning, the goal of many classification methods is to separate data into classes using a hyperplane. A hyperplane in <math>\mathbb{R}^d</math> is characterized by a unit vector <math>a \in \mathbb{R}^d</math> (<math>\lVert a \rVert_2 = 1</math>) and <math>c \in \mathbb{R}</math>. It contains all <math>z \in \mathbb{R}^d</math> such that <math>a^\top z = c</math>.

Suppose our dataset consists of <math>n</math> unit vectors in <math>\mathbb{R}^d</math>. These points can be separated into two linearly separable sets <math>X, Y</math>, where <math>|X| + |Y| = n</math>. That is, for all <math>x \in X</math>, <math>a^\top x > c</math> and for all <math>y \in Y</math>, <math>a^\top y < c</math> (or vice versa). Furthermore, suppose that the <math>\ell_2</math> distance of each point in <math>X</math> and <math>Y</math> to this separating hyperplane is at least <math>\epsilon</math>. When this is the case, the hyperplane is said to have margin <math>\epsilon</math>.

* Show that <math>X, Y</math> can be separated by the hyperplane characterized by <math>a \in \mathbb{R}^d</math> (<math>\lVert a \rVert_2 = 1</math>) and <math>c \in \mathbb{R}</math> with margin <math>\epsilon</math> is equivalent to the following condition: for all <math>x \in X</math>, <math>a^\top x \geq c + \epsilon</math> and for all <math>y \in Y</math>, <math>a^\top y \leq c - \epsilon</math> (or vice versa).

* Show that if we use a Johnson–Lindenstrauss map <math>A \in \mathbb{R}^{k \times d}</math> (the scaled Gaussian matrix given in the lecture) to reduce our data points to <math>O(\log n / \epsilon^2)</math> dimensions, then with probability at least <math>9/10</math>, the dimension-reduced data can still be separated by a hyperplane with margin <math>\epsilon / 4</math>.

== Problem 6 (Lovász Local Lemma) ==
Given a simple undirected graph <math>G = (V, E)</math> with <math>|V| = n</math>, <math>|E| = m</math> and maximum degree <math>\Delta</math>. For any <math>v \in V</math>, we denote <math>\Gamma_v</math> as the set of neighbors of <math>v</math> in <math>G</math>. Let <math>\zeta > 0</math> and <math>k \ge 1</math> be an integer. We say the graph <math>G</math> has a <math>(\zeta, k)</math>-partition if there exists a partition
<math>V = U_1 \uplus U_2 \uplus \ldots \uplus U_k</math> such that for any <math>i \in [k]</math> and <math>v \in V</math>, it holds that

<math>
|\Gamma_v \cap U_i| \le \tfrac{(1 + \zeta)\Delta}{k}.
</math>

(a) Prove that any graph <math>G = (V, E)</math> with maximum degree <math>\Delta \ge \Delta_0(\zeta, k) = \Omega\!\big(\tfrac{k^2}{\zeta^2} \log k\big)</math> has a <math>(\zeta, k)</math>-partition.

(b) Show that there exists a randomized algorithm that given any graph <math>G = (V, E)</math> satisfying the conditions above, returns a <math>(\zeta, k)</math>-partition in time <math>O((n + m)\log \tfrac{1}{\epsilon})</math> with success probability at least <math>1 - \epsilon</math>.

高级算法 (Fall 2025)/Problem Set 1

2025-09-27T14:58:33Z

Zhangyiyao: /* Problem 2 (Count Sketch) */

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

== Problem 1 (s–t Min-Cut) ==
Consider adapting Karger's min-cut algorithm to the problem of finding an <math>s</math>–<math>t</math> min-cut in an undirected graph. In this problem, we are given an undirected graph <math>G</math> together with two distinguished vertices <math>s</math> and <math>t</math>. An <math>s</math>–<math>t</math> min-cut is a set of edges whose removal disconnects <math>s</math> from <math>t</math>; we seek an edge set of minimum cardinality.

As the algorithm proceeds, the vertex <math>s</math> may get amalgamated into a new vertex as the result of an edge being contracted; we call this vertex the <math>s</math>-vertex (initially <math>s</math> itself). Similarly, we have a <math>t</math>-vertex. As we run the contraction algorithm, we enforce that we never contract an edge between the <math>s</math>-vertex and the <math>t</math>-vertex.

(a) Show that there are graphs (not multi-graphs) in which the probability that this algorithm finds an <math>s</math>–<math>t</math> min-cut is exponentially small.

(b) How large (asymptotically) can the number of <math>s</math>–<math>t</math> min-cuts in a graph be?

== Problem 2 (Count Sketch) ==
In class we learned about the Count-Min sketch. We saw that it could be used to estimate the frequency of any item in our stream up to an additive error <math>\epsilon \lVert \mathbf{x} \rVert_1</math>, where <math>\lVert \mathbf{x} \rVert_1 = n</math> is the total number of elements streamed in.

In this problem, we'll analyze an alternative algorithm that requires a bit more space, but can estimate the value of <math>x_i</math> to within error <math>\epsilon \lVert \mathbf{x} \rVert_2</math>, which is often much better in practice.

We'll analyze the following procedure:

* For a small value <math>q</math> to be set later, choose a random hash function <math>h(\cdot)</math> that maps every <math>i \in \{1, \dots, N\}</math> to <math>\{1, \dots, q\}</math>. Choose another random hash function <math>g(\cdot)</math> that maps every <math>i \in \{1, \dots, N\}</math> to <math>\{-1, 1\}</math>. Allocate space for <math>q</math> counters <math>C_1, \dots, C_q</math> (all initialized to 0).

* When <math>\mathsf{Increment}(x_i)</math> is called, set <math>C_{h(i)} \leftarrow C_{h(i)} + g(i)</math>.

* When <math>\mathsf{Estimate}(x_i)</math> is called, return <math>y_i = g(i) C_{h(i)}</math>.

Now answer the following:

(a) Show that <math>\mathbb{E}[y_i] = x_i</math>. In other words, show that our estimate for <math>x_i</math> is correct in expectation.

(b) Show that <math>\mathrm{Var}[y_i] \leq \frac{\lVert \mathbf{x} \rVert_2^2}{q}</math>.

(c) What value of <math>q</math> would we need to ensure that we obtain <math>\epsilon</math> error with probability 9/10? How many counters do we need to store in comparison to Count-Min?

== Problem 3 (Concentration of Measure I) ==
Let <math>P, Q</math> be two probability distributions on a finite set <math>\mathcal{X}</math>, with probability mass functions <math>p(x)</math> and <math>q(x)</math>. Let <math>U_1, \dots, U_n</math> be i.i.d. samples from <math>P</math>, and <math>V_1, \dots, V_n</math> be i.i.d. samples from <math>Q</math>. Define the log-likelihood ratio transforms

<math>
X_i = \log \frac{p(U_i)}{q(U_i)},
\qquad
Y_i = \log \frac{p(V_i)}{q(V_i)}.
</math>

Also define

<math>
D_{1/2}(P\|Q) = -2 \log \sum_{x\in \mathcal{X}} \sqrt{p(x)q(x)}.
</math>

Show that

<math>
\Pr\!\left(\sum_{i=1}^n X_i \le \sum_{i=1}^n Y_i\right)
\;\le\; \exp\!\left(-n D_{1/2}(P\|Q)\right).
</math>

== Problem 4 (Concentration of Measure II) ==
Consider the Erdős–Rényi random graph <math>G(n, p)</math>, where every two vertices in the graph are connected randomly and independently with probability <math>p</math>. We denote <math>G \sim G(n, p)</math> if <math>G</math> is generated in this way. We define <math>d := (n - 1) p</math> as the expected degree of the random graph.

(a) For <math>0 < p_1 < p_2 < 1</math>, let <math>G_1 \sim G(n, p_1)</math> and let <math>G_2 \sim G(n, p_2)</math>. Let <math>\Delta(G)</math> be the maximum degree of the graph <math>G</math>. Compare <math>\mathbf{E}[\Delta(G_1)]</math> and <math>\mathbf{E}[\Delta(G_2)]</math> and prove it.

(b) Consider a random graph <math>G \sim G(n, p)</math> with expected degrees <math>d = O(1)</math>. Show that for sufficiently large <math>n</math>, with probability at least 0.9, all vertices of <math>G</math> have degrees <math>O\!\big(\tfrac{\log n}{\log \log n}\big)</math>.

(c) Consider a random graph <math>G \sim G(n, p)</math> with expected degrees <math>d = o(\log n)</math>. Show that for sufficiently large <math>n</math>, with probability at least 0.9, there exists a vertex in <math>G</math> with degree at least <math>10 d</math>.

== Problem 5 (Dimension Reduction) ==

['''Inner product''']
Fix parameters <math>d > 0</math> and <math>\delta, \epsilon \in (0,1)</math>. Let <math>A \in \mathbb{R}^{k \times d}</math> be a random matrix with <math>k = O(\log(1/\delta) / \epsilon^2)</math> rows, and the entries of <math>A</math> are chosen i.i.d. from a Gaussian distribution with mean 0 and variance <math>1/k</math>. Prove that with probability <math>\geq 1 - \delta</math>, the following holds:

<math>
\forall x, y \in \mathbb{R}^d, \quad
\big|x^\top y - (Ax)^\top(Ay)\big| \leq \epsilon(\lVert x \rVert_2^2 + \lVert y \rVert_2^2).
</math>

['''Linear Separability''']
In machine learning, the goal of many classification methods is to separate data into classes using a hyperplane. A hyperplane in <math>\mathbb{R}^d</math> is characterized by a unit vector <math>a \in \mathbb{R}^d</math> (<math>\lVert a \rVert_2 = 1</math>) and <math>c \in \mathbb{R}</math>. It contains all <math>z \in \mathbb{R}^d</math> such that <math>a^\top z = c</math>.

Suppose our dataset consists of <math>n</math> unit vectors in <math>\mathbb{R}^d</math>. These points can be separated into two linearly separable sets <math>X, Y</math>, where <math>|X| + |Y| = n</math>. That is, for all <math>x \in X</math>, <math>a^\top x > c</math> and for all <math>y \in Y</math>, <math>a^\top y < c</math> (or vice versa). Furthermore, suppose that the <math>\ell_2</math> distance of each point in <math>X</math> and <math>Y</math> to this separating hyperplane is at least <math>\epsilon</math>. When this is the case, the hyperplane is said to have margin <math>\epsilon</math>.

* Show that <math>X, Y</math> can be separated by the hyperplane characterized by <math>a \in \mathbb{R}^d</math> (<math>\lVert a \rVert_2 = 1</math>) and <math>c \in \mathbb{R}</math> with margin <math>\epsilon</math> is equivalent to the following condition: for all <math>x \in X</math>, <math>a^\top x \geq c + \epsilon</math> and for all <math>y \in Y</math>, <math>a^\top y \leq c - \epsilon</math> (or vice versa).

* Show that if we use a Johnson–Lindenstrauss map <math>A \in \mathbb{R}^{k \times d}</math> (the scaled Gaussian matrix given in the lecture) to reduce our data points to <math>O(\log n / \epsilon^2)</math> dimensions, then with probability at least <math>9/10</math>, the dimension-reduced data can still be separated by a hyperplane with margin <math>\epsilon / 4</math>.

== Problem 6 (Lovász Local Lemma) ==
Given a simple undirected graph <math>G = (V, E)</math> with <math>|V| = n</math>, <math>|E| = m</math> and maximum degree <math>\Delta</math>. For any <math>v \in V</math>, we denote <math>\Gamma_v</math> as the set of neighbors of <math>v</math> in <math>G</math>. Let <math>\zeta > 0</math> and <math>k \ge 1</math> be an integer. We say the graph <math>G</math> has a <math>(\zeta, k)</math>-partition if there exists a partition
<math>V = U_1 \uplus U_2 \uplus \ldots \uplus U_k</math> such that for any <math>i \in [k]</math> and <math>v \in V</math>, it holds that

<math>
|\Gamma_v \cap U_i| \le \tfrac{(1 + \zeta)\Delta}{k}.
</math>

(a) Prove that any graph <math>G = (V, E)</math> with maximum degree <math>\Delta \ge \Delta_0(\zeta, k) = \Omega\!\big(\tfrac{k^2}{\zeta^2} \log k\big)</math> has a <math>(\zeta, k)</math>-partition.

(b) Show that there exists a randomized algorithm that given any graph <math>G = (V, E)</math> satisfying the conditions above, returns a <math>(\zeta, k)</math>-partition in time <math>O((n + m)\log \tfrac{1}{\epsilon})</math> with success probability at least <math>1 - \epsilon</math>.

高级算法 (Fall 2025)

2025-09-27T14:53:35Z

Zhangyiyao: /* Assignments */

高级算法 (Fall 2025)

2025-09-27T14:53:23Z

Zhangyiyao: /* Assignments */

高级算法 (Fall 2025)/Problem Set 1

2025-09-27T14:48:01Z

Zhangyiyao: Created page with "*每道题目的解答都要有完整的解题过程，中英文不限。 *我们推荐大家使用LaTeX, markdown等对作业进行排版。 == Problem 1 (s–t Min-Cut) == Consider adapting Karger's min-cut algorithm to the problem of finding an <math>s</math>–<math>t</math> min-cut in an undirected graph. In this problem, we are given an undirected graph <math>G</math> together with two distinguished vertices <math>s</math> and <math>t</math>. An <math>s</math>–..."

*每道题目的解答都要有完整的解题过程，中英文不限。

*我们推荐大家使用LaTeX, markdown等对作业进行排版。

== Problem 1 (s–t Min-Cut) ==
Consider adapting Karger's min-cut algorithm to the problem of finding an <math>s</math>–<math>t</math> min-cut in an undirected graph. In this problem, we are given an undirected graph <math>G</math> together with two distinguished vertices <math>s</math> and <math>t</math>. An <math>s</math>–<math>t</math> min-cut is a set of edges whose removal disconnects <math>s</math> from <math>t</math>; we seek an edge set of minimum cardinality.

As the algorithm proceeds, the vertex <math>s</math> may get amalgamated into a new vertex as the result of an edge being contracted; we call this vertex the <math>s</math>-vertex (initially <math>s</math> itself). Similarly, we have a <math>t</math>-vertex. As we run the contraction algorithm, we enforce that we never contract an edge between the <math>s</math>-vertex and the <math>t</math>-vertex.

(a) Show that there are graphs (not multi-graphs) in which the probability that this algorithm finds an <math>s</math>–<math>t</math> min-cut is exponentially small.

(b) How large (asymptotically) can the number of <math>s</math>–<math>t</math> min-cuts in a graph be?

== Problem 2 (Count Sketch) ==
In class we learned about the Count-Min sketch. We saw that it could be used to estimate the frequency of any item in our stream up to an additive error <math>\epsilon \lVert \mathbf{x} \rVert_1</math>, where <math>\lVert \mathbf{x} \rVert_1 = n</math> is the total number of elements streamed in.

In this problem, we'll analyze an alternative algorithm that requires a bit more space, but can estimate the value of <math>x_i</math> to within error <math>\epsilon \lVert \mathbf{x} \rVert_2</math>, which is often much better in practice.

We'll analyze the following procedure:

* For a small value <math>q</math> to be set later, choose a random hash function <math>h(\cdot)</math> that maps every <math>i \in \{1, \dots, N\}</math> to <math>\{1, \dots, q\}</math>. Choose another random hash function <math>g(\cdot)</math> that maps every <math>i \in \{1, \dots, N\}</math> to <math>\{-1, 1\}</math>. Allocate space for <math>q</math> counters <math>C_1, \dots, C_q</math> (all initialized to 0).

* When ''Increment''(<math>x_i</math>) is called, set <math>C_{h(i)} \leftarrow C_{h(i)} + g(i)</math>.

* When ''Estimate''(<math>x_i</math>) is called, return <math>y_i = g(i) C_{h(i)}</math>.

Now answer the following:

(a) Show that <math>\mathbb{E}[y_i] = x_i</math>. In other words, show that our estimate for <math>x_i</math> is correct in expectation.

(b) Show that <math>\mathrm{Var}[y_i] \leq \frac{\lVert \mathbf{x} \rVert_2^2}{q}</math>.

(c) What value of <math>q</math> would we need to ensure that we obtain <math>\epsilon</math> error with probability 9/10? How many counters do we need to store in comparison to Count-Min?

== Problem 3 (Concentration of Measure I) ==
Let <math>P, Q</math> be two probability distributions on a finite set <math>\mathcal{X}</math>, with probability mass functions <math>p(x)</math> and <math>q(x)</math>. Let <math>U_1, \dots, U_n</math> be i.i.d. samples from <math>P</math>, and <math>V_1, \dots, V_n</math> be i.i.d. samples from <math>Q</math>. Define the log-likelihood ratio transforms

<math>
X_i = \log \frac{p(U_i)}{q(U_i)},
\qquad
Y_i = \log \frac{p(V_i)}{q(V_i)}.
</math>

Also define

<math>
D_{1/2}(P\|Q) = -2 \log \sum_{x\in \mathcal{X}} \sqrt{p(x)q(x)}.
</math>

Show that

<math>
\Pr\!\left(\sum_{i=1}^n X_i \le \sum_{i=1}^n Y_i\right)
\;\le\; \exp\!\left(-n D_{1/2}(P\|Q)\right).
</math>

== Problem 4 (Concentration of Measure II) ==
Consider the Erdős–Rényi random graph <math>G(n, p)</math>, where every two vertices in the graph are connected randomly and independently with probability <math>p</math>. We denote <math>G \sim G(n, p)</math> if <math>G</math> is generated in this way. We define <math>d := (n - 1) p</math> as the expected degree of the random graph.

(a) For <math>0 < p_1 < p_2 < 1</math>, let <math>G_1 \sim G(n, p_1)</math> and let <math>G_2 \sim G(n, p_2)</math>. Let <math>\Delta(G)</math> be the maximum degree of the graph <math>G</math>. Compare <math>\mathbf{E}[\Delta(G_1)]</math> and <math>\mathbf{E}[\Delta(G_2)]</math> and prove it.

(b) Consider a random graph <math>G \sim G(n, p)</math> with expected degrees <math>d = O(1)</math>. Show that for sufficiently large <math>n</math>, with probability at least 0.9, all vertices of <math>G</math> have degrees <math>O\!\big(\tfrac{\log n}{\log \log n}\big)</math>.

(c) Consider a random graph <math>G \sim G(n, p)</math> with expected degrees <math>d = o(\log n)</math>. Show that for sufficiently large <math>n</math>, with probability at least 0.9, there exists a vertex in <math>G</math> with degree at least <math>10 d</math>.

== Problem 5 (Dimension Reduction) ==

['''Inner product''']
Fix parameters <math>d > 0</math> and <math>\delta, \epsilon \in (0,1)</math>. Let <math>A \in \mathbb{R}^{k \times d}</math> be a random matrix with <math>k = O(\log(1/\delta) / \epsilon^2)</math> rows, and the entries of <math>A</math> are chosen i.i.d. from a Gaussian distribution with mean 0 and variance <math>1/k</math>. Prove that with probability <math>\geq 1 - \delta</math>, the following holds:

<math>
\forall x, y \in \mathbb{R}^d, \quad
\big|x^\top y - (Ax)^\top(Ay)\big| \leq \epsilon(\lVert x \rVert_2^2 + \lVert y \rVert_2^2).
</math>

['''Linear Separability''']
In machine learning, the goal of many classification methods is to separate data into classes using a hyperplane. A hyperplane in <math>\mathbb{R}^d</math> is characterized by a unit vector <math>a \in \mathbb{R}^d</math> (<math>\lVert a \rVert_2 = 1</math>) and <math>c \in \mathbb{R}</math>. It contains all <math>z \in \mathbb{R}^d</math> such that <math>a^\top z = c</math>.

Suppose our dataset consists of <math>n</math> unit vectors in <math>\mathbb{R}^d</math>. These points can be separated into two linearly separable sets <math>X, Y</math>, where <math>|X| + |Y| = n</math>. That is, for all <math>x \in X</math>, <math>a^\top x > c</math> and for all <math>y \in Y</math>, <math>a^\top y < c</math> (or vice versa). Furthermore, suppose that the <math>\ell_2</math> distance of each point in <math>X</math> and <math>Y</math> to this separating hyperplane is at least <math>\epsilon</math>. When this is the case, the hyperplane is said to have margin <math>\epsilon</math>.

* Show that <math>X, Y</math> can be separated by the hyperplane characterized by <math>a \in \mathbb{R}^d</math> (<math>\lVert a \rVert_2 = 1</math>) and <math>c \in \mathbb{R}</math> with margin <math>\epsilon</math> is equivalent to the following condition: for all <math>x \in X</math>, <math>a^\top x \geq c + \epsilon</math> and for all <math>y \in Y</math>, <math>a^\top y \leq c - \epsilon</math> (or vice versa).

* Show that if we use a Johnson–Lindenstrauss map <math>A \in \mathbb{R}^{k \times d}</math> (the scaled Gaussian matrix given in the lecture) to reduce our data points to <math>O(\log n / \epsilon^2)</math> dimensions, then with probability at least <math>9/10</math>, the dimension-reduced data can still be separated by a hyperplane with margin <math>\epsilon / 4</math>.

== Problem 6 (Lovász Local Lemma) ==
Given a simple undirected graph <math>G = (V, E)</math> with <math>|V| = n</math>, <math>|E| = m</math> and maximum degree <math>\Delta</math>. For any <math>v \in V</math>, we denote <math>\Gamma_v</math> as the set of neighbors of <math>v</math> in <math>G</math>. Let <math>\zeta > 0</math> and <math>k \ge 1</math> be an integer. We say the graph <math>G</math> has a <math>(\zeta, k)</math>-partition if there exists a partition
<math>V = U_1 \uplus U_2 \uplus \ldots \uplus U_k</math> such that for any <math>i \in [k]</math> and <math>v \in V</math>, it holds that

<math>
|\Gamma_v \cap U_i| \le \tfrac{(1 + \zeta)\Delta}{k}.
</math>

(a) Prove that any graph <math>G = (V, E)</math> with maximum degree <math>\Delta \ge \Delta_0(\zeta, k) = \Omega\!\big(\tfrac{k^2}{\zeta^2} \log k\big)</math> has a <math>(\zeta, k)</math>-partition.

(b) Show that there exists a randomized algorithm that given any graph <math>G = (V, E)</math> satisfying the conditions above, returns a <math>(\zeta, k)</math>-partition in time <math>O((n + m)\log \tfrac{1}{\epsilon})</math> with success probability at least <math>1 - \epsilon</math>.

高级算法 (Fall 2025)

2025-08-23T06:35:30Z

Zhangyiyao: /* Course info */

高级算法 (Fall 2025) / Course materials

2025-08-23T06:33:05Z

Zhangyiyao: Created page with "= Course textbooks = {|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;" |100px |width="100%"| :Rajeev Motwani and Prabhakar Raghavan. :'''''Randomized Algorithms'''''. :Cambridge University Press, 1995. |- |100px|| : Vijay Vazirani. :'''''Approximation Algorithms'''''. :S..."

= Course textbooks =
{|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|[[File:MR-randomized-algorithms.png‎|border|100px]]
|width="100%"|
:Rajeev Motwani and Prabhakar Raghavan.
:'''''Randomized Algorithms'''''.
:Cambridge University Press, 1995.
|-
|[[File:Approximation_Algorithms.jpg|border|100px]]||
: Vijay Vazirani.
:'''''Approximation Algorithms'''''.
:Springer-Verlag, 2001.
|}

= References and further readings =
{|border="2" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|[[File:Probability and Computing. 2nd Edition cover.jpg|border|143x143px]]||
: Michael Mitzenmacher and Eli Upfal.
:'''''Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis,''''' 2nd Edition
:Cambridge University Press, 2017.
|-
|[[File:The_Probabilistic_Method.jpg|border|100px]]||
:Noga Alon and Joel Spencer.
:'''''The Probabilistic Method''''', 4th edition.
:Wiley, 2016.
|-
|[[File:Design_of_Approximation_Algorithms.png‎|border|100px]]||
: David P. Williamson and David Shmoys.
:'''''The Design of Approximation Algorithms'''''.
:Cambridge University Press, 2011.
|-
|[[File:Combinatorial_Optimization.webp|border|100px]]||
:Bernhard Korte and Jens Vygen.
:'''''Combinatorial Optimization: theory and algorithms''''', 6th edition.
:Springer, 2018.
|-
|[[File:Lx=b.jpg|border|100px]]||
:Nisheeth K. Vishnoi.
:'''''Lx = b: laplacian solvers and their algorithmic applications'''''.
:Foundations and Trends® in Theoretical Computer Science, 2012.
|-
|[[File:Eigenvalues_and_Polynomials.png|border|100px]]||
:Lap Chi Lau.
:'''''Eigenvalues and Polynomials'''''.
:https://cs.uwaterloo.ca/~lapchi/cs860/notes/eigenpoly.pdf
|-
|[[File:Algo.jpg‎|border|100px]]
|width="100%"|
:Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani.
:'''''Algorithms'''''.
:McGraw-Hill, 2006.
|-
|}

高级算法 (Fall 2025)

2025-08-23T06:32:01Z

Zhangyiyao: Created page with "{{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..."

高级算法 (Fall 2024)

2025-08-23T06:31:26Z

Zhangyiyao: Undo revision 13237 by Zhangyiyao (talk)

{{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 (单), 4pm-6pm Thursday, 2pm-4pm 仙Ⅰ-206
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = Monday, 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 2024. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

* '''(2024/12/26)''' Final已经发布，文档密码公布于QQ群中。不在QQ群的同学请加入QQ群或邮件联系助教获取密码。

= 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''':
** 于逸潇：yixiaoyu@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday (单), 4pm-6pm, 仙Ⅰ-206
** Thursday, 2pm-4pm, 仙Ⅰ-206
* '''Office hour''': Monday, 2pm-4pm, 计算机系 804
* '''QQ群''': 757436140

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

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

=== Course materials ===
* [[高级算法 (Fall 2024) / 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 2024)/Problem Set 1|Problem Set 1]] 请在 2024/10/14 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2024)/第一次作业提交名单|第一次作业提交名单]]

*[[高级算法 (Fall 2024)/Problem Set 2|Problem Set 2]] 请在 2024/11/25 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A2.pdf'). [[高级算法 (Fall 2024)/第二次作业提交名单|第二次作业提交名单]]

*[[Media:Advanced algorithm 2024 Fall take home final.pdf|Take home final (2024 fall)]] 请在 2025/01/12 12:00 UTC+8 提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_final.pdf'). [[高级算法 (Fall 2024)/Final提交名单|Final提交名单]]

= Lecture Notes =
# [[高级算法 (Fall 2024)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2024/Cut.pdf slides])
#* [[高级算法 (Fall 2024)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2024)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2024/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2024)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2024)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2024/Hashing.pdf slides])
#* [[高级算法 (Fall 2024)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2024)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2024)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2024/Concentration.pdf slides])
#* [[高级算法 (Fall 2024)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2024)/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]
# 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])
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2024/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-2024.pdf|slides]])
# Random walks ([[Media:Random walk-AA2024.pdf|slides]])
# Markov chains and coupling ([[Media:MCMC AA 2024.pdf|slides]])
# Markov chain Monte Carlo (MCMC) and expander graphs ([[Media:MCMC2 AA 2024.pdf|slides]])
# Expander random walks and Sparsification ([[Media:Expander random walk+sparsification AA 2024.pdf|slides]])
# Spectral sparsification ([[Media:Spectral sparsification AA 2024.pdf|slides]])

= 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 2024)

2025-08-23T06:29:04Z

Zhangyiyao:

高级算法 (Fall 2024)/Final提交名单

2025-01-12T13:28:43Z

Zhangyiyao:

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220076 || 杨景越
|-
| 211220152 || 吴振宇
|-
| 211250001 || 鞠哲
|-
| 211250044 || 朱家辰
|-
| 211250182 || 胡皓明
|-
| 211502020 || 周相羽
|-
| 211820282 || 彭钰朝
|-
| 211830008 || 缪天顺
|-
| 221220002 || 沈均文
|-
| 221502010 || 梁志浩
|-
| 221840186 || 陈端锐
|-
| 221840188 || 谭泽晖
|-
| 502023330043 || 吕铸恒
|-
| 502024330003 || 陈思睿
|-
| 502024330013 || 杭业晟
|-
| 502024330020 || 蒋承欢
|-
| 502024330022 || 蒋裕成
|-
| 502024330030 || 梁梓豪
|-
| 502024330047 || 王恺予
|-
| 502024330048 || 王力
|-
| 502024330065 || 张天泽
|-
| 502024330075 || 周灿
|-
| 502024370027 || 史浩宇
|-
| 502024370054 || 尹力
|-
| 522024330036 || 李尚达
|-
| 522024330070 || 孙昊天
|-
| 522024330112 || 叶佳
|-
| 522024330118 || 张弛
|-
| 522024330137 || 朱英杰
|-
| 652023330009 || 彭泽
|-
| 652024330007 || 冯烨聪
|-
| 652024330008 || 冯昱达
|-
| 652024330011 || 侯哲
|-
| 652024330012 || 姜振宇
|-
| 652024330022 || 谭森琪
|-
| 652024330033 || 肖依博
|-
| 652024330035 || 杨宇轩
|-
| 652024330040 || 郑翰
|-
| 旁听 || 祝永祺
|}
</center>

高级算法 (Fall 2024)/Final提交名单

2025-01-12T05:39:24Z

Zhangyiyao:

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220076 || 杨景越
|-
| 211220152 || 吴振宇
|-
| 211250001 || 鞠哲
|-
| 211250044 || 朱家辰
|-
| 211250182 || 胡皓明
|-
| 211502020 || 周相羽
|-
| 211820282 || 彭钰朝
|-
| 211830008 || 缪天顺
|-
| 221220002 || 沈均文
|-
| 221502010 || 梁志浩
|-
| 221840186 || 陈端锐
|-
| 221840188 || 谭泽晖
|-
| 502023330043 || 吕铸恒
|-
| 502024330003 || 陈思睿
|-
| 502024330013 || 杭业晟
|-
| 502024330020 || 蒋承欢
|-
| 502024330022 || 蒋裕成
|-
| 502024330047 || 王恺予
|-
| 502024330048 || 王力
|-
| 502024330065 || 张天泽
|-
| 502024330075 || 周灿
|-
| 502024370027 || 史浩宇
|-
| 502024370054 || 尹力
|-
| 522024330036 || 李尚达
|-
| 522024330070 || 孙昊天
|-
| 522024330112 || 叶佳
|-
| 522024330118 || 张弛
|-
| 522024330137 || 朱英杰
|-
| 652023330009 || 彭泽
|-
| 652024330007 || 冯烨聪
|-
| 652024330008 || 冯昱达
|-
| 652024330011 || 侯哲
|-
| 652024330012 || 姜振宇
|-
| 652024330022 || 谭森琪
|-
| 652024330033 || 肖依博
|-
| 652024330035 || 杨宇轩
|-
| 652024330040 || 郑翰
|-
| 旁听 || 祝永祺
|}
</center>

高级算法 (Fall 2024)

2025-01-12T04:52:49Z

Zhangyiyao: /* Assignments */

{{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 (单), 4pm-6pm Thursday, 2pm-4pm 仙Ⅰ-206
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = Monday, 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 2024. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

* '''(2024/12/26)''' Final已经发布，文档密码公布于QQ群中。不在QQ群的同学请加入QQ群或邮件联系助教获取密码。

= 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''':
** 于逸潇：yixiaoyu@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday (单), 4pm-6pm, 仙Ⅰ-206
** Thursday, 2pm-4pm, 仙Ⅰ-206
* '''Office hour''': Monday, 2pm-4pm, 计算机系 804
* '''QQ群''': 757436140

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

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

=== Course materials ===
* [[高级算法 (Fall 2024) / 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 2024)/Problem Set 1|Problem Set 1]] 请在 2024/10/14 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2024)/第一次作业提交名单|第一次作业提交名单]]

*[[高级算法 (Fall 2024)/Problem Set 2|Problem Set 2]] 请在 2024/11/25 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A2.pdf'). [[高级算法 (Fall 2024)/第二次作业提交名单|第二次作业提交名单]]

*[[Media:Advanced algorithm 2024 Fall take home final.pdf|Take home final (2024 fall)]] 请在 2025/01/12 12:00 UTC+8 提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_final.pdf'). [[高级算法 (Fall 2024)/Final提交名单|Final提交名单]]

= Lecture Notes =
# [[高级算法 (Fall 2024)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2024/Cut.pdf slides])
#* [[高级算法 (Fall 2024)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2024)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2024/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2024)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2024)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2024/Hashing.pdf slides])
#* [[高级算法 (Fall 2024)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2024)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2024)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2024/Concentration.pdf slides])
#* [[高级算法 (Fall 2024)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2024)/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]
# 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])
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2024/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-2024.pdf|slides]])
# Random walks ([[Media:Random walk-AA2024.pdf|slides]])
# Markov chains and coupling ([[Media:MCMC AA 2024.pdf|slides]])
# Markov chain Monte Carlo (MCMC) and expander graphs ([[Media:MCMC2 AA 2024.pdf|slides]])
# Expander random walks and Sparsification ([[Media:Expander random walk+sparsification AA 2024.pdf|slides]])
# Spectral sparsification ([[Media:Spectral sparsification AA 2024.pdf|slides]])

= 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 2024)/Final提交名单

2025-01-12T04:48:34Z

Zhangyiyao: Created page with "如有错漏请邮件联系助教. <center> {| class="wikitable" |- ! 学号 !! 姓名 |- | 211220076 || 杨景越 |- | 211220152 || 吴振宇 |- | 211250001 || 鞠哲 |- | 211250044 || 朱家辰 |- | 211250182 || 胡皓明 |- | 211502020 || 周相羽 |- | 211820282 || 彭钰朝 |- | 211830008 || 缪天顺 |- | 221220002 || 沈均文 |- | 221502010 || 梁志浩 |- | 221840188 || 谭泽晖 |- | 502023330043 || 吕铸恒 |- | 502024330003 || 陈思睿 |- | 5020..."

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220076 || 杨景越
|-
| 211220152 || 吴振宇
|-
| 211250001 || 鞠哲
|-
| 211250044 || 朱家辰
|-
| 211250182 || 胡皓明
|-
| 211502020 || 周相羽
|-
| 211820282 || 彭钰朝
|-
| 211830008 || 缪天顺
|-
| 221220002 || 沈均文
|-
| 221502010 || 梁志浩
|-
| 221840188 || 谭泽晖
|-
| 502023330043 || 吕铸恒
|-
| 502024330003 || 陈思睿
|-
| 502024330013 || 杭业晟
|-
| 502024330020 || 蒋承欢
|-
| 502024330022 || 蒋裕成
|-
| 502024330047 || 王恺予
|-
| 502024330048 || 王力
|-
| 502024330065 || 张天泽
|-
| 502024330075 || 周灿
|-
| 502024370027 || 史浩宇
|-
| 502024370054 || 尹力
|-
| 522024330036 || 李尚达
|-
| 522024330070 || 孙昊天
|-
| 522024330112 || 叶佳
|-
| 522024330118 || 张弛
|-
| 522024330137 || 朱英杰
|-
| 652023330009 || 彭泽
|-
| 652024330007 || 冯烨聪
|-
| 652024330008 || 冯昱达
|-
| 652024330011 || 侯哲
|-
| 652024330012 || 姜振宇
|-
| 652024330022 || 谭森琪
|-
| 652024330033 || 肖依博
|-
| 652024330035 || 杨宇轩
|-
| 652024330040 || 郑翰
|-
| 旁听 || 祝永祺
|}
</center>

高级算法 (Fall 2024)

2024-12-26T07:20:22Z

Zhangyiyao: /* Announcement */

{{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 (单), 4pm-6pm Thursday, 2pm-4pm 仙Ⅰ-206
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = Monday, 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 2024. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

* '''(2024/12/26)''' Final已经发布，文档密码公布于QQ群中。不在QQ群的同学请加入QQ群或邮件联系助教获取密码。

= 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''':
** 于逸潇：yixiaoyu@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday (单), 4pm-6pm, 仙Ⅰ-206
** Thursday, 2pm-4pm, 仙Ⅰ-206
* '''Office hour''': Monday, 2pm-4pm, 计算机系 804
* '''QQ群''': 757436140

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

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

=== Course materials ===
* [[高级算法 (Fall 2024) / 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 2024)/Problem Set 1|Problem Set 1]] 请在 2024/10/14 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2024)/第一次作业提交名单|第一次作业提交名单]]

*[[高级算法 (Fall 2024)/Problem Set 2|Problem Set 2]] 请在 2024/11/25 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A2.pdf'). [[高级算法 (Fall 2024)/第二次作业提交名单|第二次作业提交名单]]

*[[Media:Advanced algorithm 2024 Fall take home final.pdf|Take home final (2024 fall)]] 请在 2025/01/12 12:00 UTC+8 提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_final.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2024)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2024/Cut.pdf slides])
#* [[高级算法 (Fall 2024)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2024)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2024/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2024)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2024)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2024/Hashing.pdf slides])
#* [[高级算法 (Fall 2024)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2024)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2024)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2024/Concentration.pdf slides])
#* [[高级算法 (Fall 2024)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2024)/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]
# 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])
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2024/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-2024.pdf|slides]])
# Random walks ([[Media:Random walk-AA2024.pdf|slides]])
# Markov chains and coupling ([[Media:MCMC AA 2024.pdf|slides]])
# Markov chain Monte Carlo (MCMC) and expander graphs ([[Media:MCMC2 AA 2024.pdf|slides]])
# Expander random walks and Sparsification ([[Media:Expander random walk+sparsification AA 2024.pdf|slides]])
# Spectral sparsification Spectral ([[Media:Spectral sparsification AA 2024.pdf|slides]])

= 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.

File:Advanced algorithm 2024 Fall take home final.pdf

2024-12-26T07:16:12Z

Zhangyiyao: Zhangyiyao uploaded a new version of File:Advanced algorithm 2024 Fall take home final.pdf

高级算法 (Fall 2024)

2024-12-26T07:15:43Z

Zhangyiyao: /* Assignments */

{{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 (单), 4pm-6pm Thursday, 2pm-4pm 仙Ⅰ-206
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = Monday, 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 2024. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

* '''(2024/12/26)''' Final已经发布，文档密码公布于QQ群中。

= 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''':
** 于逸潇：yixiaoyu@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday (单), 4pm-6pm, 仙Ⅰ-206
** Thursday, 2pm-4pm, 仙Ⅰ-206
* '''Office hour''': Monday, 2pm-4pm, 计算机系 804
* '''QQ群''': 757436140

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

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

=== Course materials ===
* [[高级算法 (Fall 2024) / 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 2024)/Problem Set 1|Problem Set 1]] 请在 2024/10/14 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2024)/第一次作业提交名单|第一次作业提交名单]]

*[[高级算法 (Fall 2024)/Problem Set 2|Problem Set 2]] 请在 2024/11/25 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A2.pdf'). [[高级算法 (Fall 2024)/第二次作业提交名单|第二次作业提交名单]]

*[[Media:Advanced algorithm 2024 Fall take home final.pdf|Take home final (2024 fall)]] 请在 2025/01/12 12:00 UTC+8 提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_final.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2024)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2024/Cut.pdf slides])
#* [[高级算法 (Fall 2024)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2024)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2024/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2024)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2024)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2024/Hashing.pdf slides])
#* [[高级算法 (Fall 2024)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2024)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2024)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2024/Concentration.pdf slides])
#* [[高级算法 (Fall 2024)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2024)/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]
# 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])
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2024/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-2024.pdf|slides]])
# Random walks ([[Media:Random walk-AA2024.pdf|slides]])
# Markov chains and coupling ([[Media:MCMC AA 2024.pdf|slides]])
# Markov chain Monte Carlo (MCMC) and expander graphs ([[Media:MCMC2 AA 2024.pdf|slides]])
# Expander random walks and Sparsification ([[Media:Expander random walk+sparsification AA 2024.pdf|slides]])
# Spectral sparsification Spectral ([[Media:Spectral sparsification AA 2024.pdf|slides]])

= 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 2024)

2024-12-26T07:03:49Z

Zhangyiyao: /* Announcement */

{{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 (单), 4pm-6pm Thursday, 2pm-4pm 仙Ⅰ-206
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = Monday, 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 2024. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

* '''(2024/12/26)''' Final已经发布，文档密码公布于QQ群中。

= 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''':
** 于逸潇：yixiaoyu@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday (单), 4pm-6pm, 仙Ⅰ-206
** Thursday, 2pm-4pm, 仙Ⅰ-206
* '''Office hour''': Monday, 2pm-4pm, 计算机系 804
* '''QQ群''': 757436140

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

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

=== Course materials ===
* [[高级算法 (Fall 2024) / 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 2024)/Problem Set 1|Problem Set 1]] 请在 2024/10/14 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2024)/第一次作业提交名单|第一次作业提交名单]]

*[[高级算法 (Fall 2024)/Problem Set 2|Problem Set 2]] 请在 2024/11/25 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A2.pdf'). [[高级算法 (Fall 2024)/第二次作业提交名单|第二次作业提交名单]]

*[[Media:Advanced algorithm 2024 Fall take home final.pdf|Take home final (2024 fall)]] 请在 2024/01/12 12:00 UTC+8 提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_final.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2024)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2024/Cut.pdf slides])
#* [[高级算法 (Fall 2024)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2024)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2024/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2024)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2024)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2024/Hashing.pdf slides])
#* [[高级算法 (Fall 2024)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2024)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2024)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2024/Concentration.pdf slides])
#* [[高级算法 (Fall 2024)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2024)/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]
# 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])
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2024/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-2024.pdf|slides]])
# Random walks ([[Media:Random walk-AA2024.pdf|slides]])
# Markov chains and coupling ([[Media:MCMC AA 2024.pdf|slides]])
# Markov chain Monte Carlo (MCMC) and expander graphs ([[Media:MCMC2 AA 2024.pdf|slides]])
# Expander random walks and Sparsification ([[Media:Expander random walk+sparsification AA 2024.pdf|slides]])
# Spectral sparsification Spectral ([[Media:Spectral sparsification AA 2024.pdf|slides]])

= 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 2024)

2024-12-26T07:00:15Z

Zhangyiyao: /* Assignments */

{{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 (单), 4pm-6pm Thursday, 2pm-4pm 仙Ⅰ-206
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = Monday, 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 2024. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

* TBA

= 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''':
** 于逸潇：yixiaoyu@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday (单), 4pm-6pm, 仙Ⅰ-206
** Thursday, 2pm-4pm, 仙Ⅰ-206
* '''Office hour''': Monday, 2pm-4pm, 计算机系 804
* '''QQ群''': 757436140

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

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

=== Course materials ===
* [[高级算法 (Fall 2024) / 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 2024)/Problem Set 1|Problem Set 1]] 请在 2024/10/14 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2024)/第一次作业提交名单|第一次作业提交名单]]

*[[高级算法 (Fall 2024)/Problem Set 2|Problem Set 2]] 请在 2024/11/25 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A2.pdf'). [[高级算法 (Fall 2024)/第二次作业提交名单|第二次作业提交名单]]

*[[Media:Advanced algorithm 2024 Fall take home final.pdf|Take home final (2024 fall)]] 请在 2024/01/12 12:00 UTC+8 提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_final.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2024)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2024/Cut.pdf slides])
#* [[高级算法 (Fall 2024)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2024)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2024/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2024)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2024)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2024/Hashing.pdf slides])
#* [[高级算法 (Fall 2024)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2024)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2024)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2024/Concentration.pdf slides])
#* [[高级算法 (Fall 2024)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2024)/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]
# 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])
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2024/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-2024.pdf|slides]])
# Random walks ([[Media:Random walk-AA2024.pdf|slides]])
# Markov chains and coupling ([[Media:MCMC AA 2024.pdf|slides]])
# Markov chain Monte Carlo (MCMC) and expander graphs ([[Media:MCMC2 AA 2024.pdf|slides]])
# Expander random walks and Sparsification ([[Media:Expander random walk+sparsification AA 2024.pdf|slides]])
# Spectral sparsification Spectral ([[Media:Spectral sparsification AA 2024.pdf|slides]])

= 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.

File:Advanced algorithm 2024 Fall take home final.pdf

2024-12-26T06:58:15Z

Zhangyiyao:

高级算法 (Fall 2024)/第二次作业提交名单

2024-12-09T07:19:44Z

Zhangyiyao:

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220076 || 杨景越
|-
| 211220152 || 吴振宇
|-
| 211250001 || 鞠哲
|-
| 211250044 || 朱家辰
|-
| 211250182 || 胡皓明
|-
| 211502020 || 周相羽
|-
| 211820202 || 彭钰朝
|-
| 211830008 || 缪天顺
|-
| 221220002 || 沈均文
|-
| 221502010 || 梁志浩
|-
| 221840186 || 陈端锐
|-
| 221840188 || 谭泽晖
|-
| 502023330043 || 吕铸恒
|-
| 502024330003 || 陈思睿
|-
| 502024330013 || 杭业晟
|-
| 502024330020 || 蒋承欢
|-
| 502024330022 || 蒋裕成
|-
| 502024330030 || 梁梓豪
|-
| 502024330047 || 王恺予
|-
| 502024330048 || 王力
|-
| 502024330065 || 张天泽
|-
| 502024330075 || 周灿
|-
| 502024370027 || 史浩宇
|-
| 502024370054 || 尹力
|-
| 522024330036 || 李尚达
|-
| 522024330070 || 孙昊天
|-
| 522024330109 || 杨林
|-
| 522024330112 || 叶佳
|-
| 522024330118 || 张弛
|-
| 522024330137 || 朱英杰
|-
| 652023330009 || 彭泽
|-
| 652024330007 || 冯烨聪
|-
| 652024330008 || 冯昱达
|-
| 652024330011 || 侯哲
|-
| 652024330012 || 姜振宇
|-
| 652024330022 || 谭森琪
|-
| 652024330033 || 肖依博
|-
| 652024330035 || 杨宇轩
|-
| 652024330040 || 郑翰
|-
| 旁听 || 祝永祺
|}
</center>

高级算法 (Fall 2024)

2024-11-25T08:27:47Z

Zhangyiyao: /* Assignments */

{{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 (单), 4pm-6pm Thursday, 2pm-4pm 仙Ⅰ-206
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = Monday, 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 2024. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

* TBA

= 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''':
** 于逸潇：yixiaoyu@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday (单), 4pm-6pm, 仙Ⅰ-206
** Thursday, 2pm-4pm, 仙Ⅰ-206
* '''Office hour''': Monday, 2pm-4pm, 计算机系 804
* '''QQ群''': 757436140

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

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

=== Course materials ===
* [[高级算法 (Fall 2024) / 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 2024)/Problem Set 1|Problem Set 1]] 请在 2024/10/14 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A1.pdf'). [[高级算法 (Fall 2024)/第一次作业提交名单|第一次作业提交名单]]

*[[高级算法 (Fall 2024)/Problem Set 2|Problem Set 2]] 请在 2024/11/25 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'学号_姓名_A2.pdf'). [[高级算法 (Fall 2024)/第二次作业提交名单|第二次作业提交名单]]

= Lecture Notes =
# [[高级算法 (Fall 2024)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2024/Cut.pdf slides])
#* [[高级算法 (Fall 2024)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2024)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2024/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2024)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2024)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2024/Hashing.pdf slides])
#* [[高级算法 (Fall 2024)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2024)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2024)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2024/Concentration.pdf slides])
#* [[高级算法 (Fall 2024)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2024)/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]
# 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/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 2024)/第二次作业提交名单

2024-11-25T08:27:22Z

Zhangyiyao:

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220076 || 杨景越
|-
| 211220152 || 吴振宇
|-
| 211250001 || 鞠哲
|-
| 211250044 || 朱家辰
|-
| 211250182 || 胡皓明
|-
| 211502020 || 周相羽
|-
| 211820282 || 彭钰朝
|-
| 211830008 || 缪天顺
|-
| 221220002 || 沈均文
|-
| 221502010 || 梁志浩
|-
| 221840186 || 陈端锐
|-
| 221840188 || 谭泽晖
|-
| 502023330043 || 吕铸恒
|-
| 502024330003 || 陈思睿
|-
| 502024330013 || 杭业晟
|-
| 502024330020 || 蒋承欢
|-
| 502024330022 || 蒋裕成
|-
| 502024330030 || 梁梓豪
|-
| 502024330047 || 王恺予
|-
| 502024330048 || 王力
|-
| 502024330065 || 张天泽
|-
| 502024330075 || 周灿
|-
| 502024370027 || 史浩宇
|-
| 502024370054 || 尹力
|-
| 522024330036 || 李尚达
|-
| 522024330112 || 叶佳
|-
| 522024330118 || 张弛
|-
| 522024330137 || 朱英杰
|-
| 652023330009 || 彭泽
|-
| 652024330007 || 冯烨聪
|-
| 652024330008 || 冯昱达
|-
| 652024330011 || 侯哲
|-
| 652024330012 || 姜振宇
|-
| 652024330022 || 谭森琪
|-
| 652024330033 || 肖依博
|-
| 652024330035 || 杨宇轩
|-
| 652024330040 || 郑翰
|-
| 旁听 || 祝永祺
|}
</center>

高级算法 (Fall 2024)/第二次作业提交名单

2024-11-25T08:23:37Z

Zhangyiyao: Created page with " 如有错漏请邮件联系助教. <center> {| class="wikitable" |- ! 学号 !! 姓名 |- | 211220076 || 杨景越 |- | 211220152 || 吴振宇 |- | 211250001 || 鞠哲 |- | 211250044 || 朱家辰 |- | 211250182 || 胡皓明 |- | 211502020 || 周相羽 |- | 211820202 || 彭钰朝 |- | 211830008 || 缪天顺 |- | 221220002 || 沈均文 |- | 221502010 || 梁志浩 |- | 221840186 || 陈端锐 |- | 221840188 || 谭泽晖 |- | 502023330043 || 吕铸恒 |- | 50202..."

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 211220076 || 杨景越
|-
| 211220152 || 吴振宇
|-
| 211250001 || 鞠哲
|-
| 211250044 || 朱家辰
|-
| 211250182 || 胡皓明
|-
| 211502020 || 周相羽
|-
| 211820202 || 彭钰朝
|-
| 211830008 || 缪天顺
|-
| 221220002 || 沈均文
|-
| 221502010 || 梁志浩
|-
| 221840186 || 陈端锐
|-
| 221840188 || 谭泽晖
|-
| 502023330043 || 吕铸恒
|-
| 502024330003 || 陈思睿
|-
| 502024330013 || 杭业晟
|-
| 502024330020 || 蒋承欢
|-
| 502024330022 || 蒋裕成
|-
| 502024330030 || 梁梓豪
|-
| 502024330047 || 王恺予
|-
| 502024330048 || 王力
|-
| 502024330065 || 张天泽
|-
| 502024330075 || 周灿
|-
| 502024370027 || 史浩宇
|-
| 502024370054 || 尹力
|-
| 522024330036 || 李尚达
|-
| 522024330112 || 叶佳
|-
| 522024330118 || 张弛
|-
| 522024330137 || 朱英杰
|-
| 652023330009 || 彭泽
|-
| 652024330007 || 冯烨聪
|-
| 652024330008 || 冯昱达
|-
| 652024330011 || 侯哲
|-
| 652024330012 || 姜振宇
|-
| 652024330022 || 谭森琪
|-
| 652024330033 || 肖依博
|-
| 652024330035 || 杨宇轩
|-
| 652024330040 || 郑翰
|-
| 旁听 || 祝永祺
|}
</center>