TCS Wiki - User contributions [en]

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

2026-11-07T11:02:31Z

Zhangyiyao: Created page with " 如有错漏请邮件联系助教. <center> {| class="wikitable" |- ! 学号 !! 姓名 |- | 2026330030 || 林新晨 |- | 221220052 || 周宇轩 |- | 231220001 || 陈梓睿 |- | 231300082 || 王鹭天 |- | 231502015 || 胡子豪 |- | 231502019 || 陈祉翰 |- | 231870073 || 朱伟鹏 |- | 241220003 || 沈琪皓 |- | 241220004 || 张宸源 |- | 241220073 || 王子墨 |- | 241220146 || 潘祖凯 |- | 241502001 || 马修齐 |- | 241840240 || 李味鸿 |- | 241880488 || 扶..."

如有错漏请邮件联系助教.
<center>
{| class="wikitable"
|-
! 学号 !! 姓名
|-
| 2026330030 || 林新晨
|-
| 221220052 || 周宇轩
|-
| 231220001 || 陈梓睿
|-
| 231300082 || 王鹭天
|-
| 231502015 || 胡子豪
|-
| 231502019 || 陈祉翰
|-
| 231870073 || 朱伟鹏
|-
| 241220003 || 沈琪皓
|-
| 241220004 || 张宸源
|-
| 241220073 || 王子墨
|-
| 241220146 || 潘祖凯
|-
| 241502001 || 马修齐
|-
| 241840240 || 李味鸿
|-
| 241880488 || 扶嘉年
|-
| 251220169 || 许家旗
|-
| 251275003 || 翟悦凯
|-
| 502024330038 || 马一鸣
|-
| 502025370067 || 易昌恒
|-
| 502026330010 || 冯浚哲
|-
| 502026330011 || 高诗豪
|-
| 502026330012 || 耿天成
|-
| 502026330019 || 黄霖
|-
| 502026330020 || 黄祈玮
|-
| 502026330027 || 李恒济
|-
| 502026330050 || 童思源
|-
| 502026330051 || 汪宗元
|-
| 502026330054 || 王一萌
|-
| 502026330072 || 周凡淇
|-
| 502026330080 || 胡更泓
|-
| 502026370007 || 董少德
|-
| 502026370008 || 冯中信
|-
| 502026370014 || 韩永琦
|-
| 502026370025 || 郦恒仪
|-
| 502026370031 || 钱昱
|-
| 502026370042 || 汪恬
|-
| 502026370053 || 熊福京
|-
| 502026370055 || 许兆霖
|-
| 502026370059 || 姚岐周
|-
| 502026370060 || 叶文彬
|-
| 502026370066 || 张瑞
|-
| 502026370077 || 邹品聪
|-
| 522024330109 || 杨林
|-
| 522026330014 || 陈一诺
|-
| 522026330015 || 陈雨航
|-
| 522026330016 || 程星智
|-
| 522026330019 || 邓乔
|-
| 522026330026 || 范思民
|-
| 522026330030 || 高兴
|-
| 522026330040 || 霍泉如
|-
| 522026330059 || 梁星宇
|-
| 522026330061 || 刘天一
|-
| 522026330065 || 刘子羊
|-
| 522026330077 || 彭圣轩
|-
| 522026330080 || 沈均文
|-
| 522026330082 || 石大川
|-
| 522026330083 || 石浩
|-
| 522026330091 || 闻嘉迅
|-
| 522026330094 || 王启瑞
|-
| 522026330099 || 吴承迅
|-
| 522026330105 || 徐浩然
|-
| 522026330111 || 严宇恒
|-
| 522026330120 || 张长雄
|-
| 522026330121 || 张昊飞
|-
| 522026330136 || 支宇航
|-
| 522026370001 || 安星哲
|-
| 522026370002 || 陈昊
|-
| 652026330001 || 陈端锐
|-
| 652026330002 || 陈力峥
|-
| 652026330005 || 陈正道
|-
| 652026330008 || 杜沛键
|-
| 652026330023 || 王鹏超
|-
| 652026330024 || 王天宇
|-
| 652026330029 || 杨元东
|-
| 652026330033 || 张天钰
|-
| 652026330038 || 周锐奔
|-
| MG1933Z09 || 支原
|}
</center>

高级算法 (Fall 2026)

2026-11-07T11:02: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 = 周一 5-6节 (单) 仙Ⅰ-319
周三 5-6节仙Ⅰ-319
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = 周一4-5pm（尹一通 804） 
周四4-5pm（刘景铖 516） 
By appointment
|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 2026. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

= Course info =
* '''Instructor ''':
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
* '''Teaching Assistant''':
** 于逸潇：[mailto:yixiaoyu@smail.nju.edu.cn <yixiaoyu@smail.nju.edu.cn>]
** 张弈垚：[mailto:zhangyiyao@smail.nju.edu.cn <zhangyiyao@smail.nju.edu.cn>]
* '''Class meeting''':
** 周一 5-6节 1-17周(单) 仙Ⅰ-319
** 周三 5-6节 1-18周仙Ⅰ-319
* '''Office hour''':
** 周一4-5pm（尹一通 804）
** 周四4-5pm（刘景铖 516）
** By appointment
* '''QQ群''': 1098567018

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

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

=== Course materials ===
* [[高级算法 (Fall 2026) / 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.

请在指定时间之前将 pdf 格式的作业严格按命名规范命名，提交到对应网盘链接中，推荐使用 Markdown / LaTeX

# [[Media:AA26-Homework1.pdf|Homework1]] 请在2026年10月14日23点59分之前提交到 [https://box.nju.edu.cn/u/d/df40465a1620457faf29/ 网盘链接] (文件名为'学号_姓名_A1.pdf') [[高级算法 (Fall 2026)/第一次作业提交名单|第一次作业提交名单]]
# [[Media:AA26-Homework2.pdf|Homework2]] 请在2026年11月25日23点59分之前提交到 [https://box.nju.edu.cn/u/d/aa9c58ab365a40eaaf73/ 网盘链接] (文件名为'学号_姓名_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/aa2026/Cut.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-cuts-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-cuts-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2026)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2026/Fingerprinting.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-fingerprinting-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-fingerprinting-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2026)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2026)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2026/Hashing.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-hashing-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-hashing-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2026)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2026)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2026)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2026/Concentration.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-concentration-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-concentration-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2026)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2026)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2026/NNS.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-JLT-LSH-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-JLT-LSH-zh.pdf AI生成讲义])
#* [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/aa2026/LLL.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-LLL-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-LLL-zh.pdf AI生成讲义])
# 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

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

2026-11-04T12:19:09Z

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 = 周一 5-6节 (单) 仙Ⅰ-319
周三 5-6节仙Ⅰ-319
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = 周一4-5pm（尹一通 804） 
周四4-5pm（刘景铖 516） 
By appointment
|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 2026. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

= Course info =
* '''Instructor ''':
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
* '''Teaching Assistant''':
** 于逸潇：[mailto:yixiaoyu@smail.nju.edu.cn <yixiaoyu@smail.nju.edu.cn>]
** 张弈垚：[mailto:zhangyiyao@smail.nju.edu.cn <zhangyiyao@smail.nju.edu.cn>]
* '''Class meeting''':
** 周一 5-6节 1-17周(单) 仙Ⅰ-319
** 周三 5-6节 1-18周仙Ⅰ-319
* '''Office hour''':
** 周一4-5pm（尹一通 804）
** 周四4-5pm（刘景铖 516）
** By appointment
* '''QQ群''': 1098567018

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

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

=== Course materials ===
* [[高级算法 (Fall 2026) / 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.

请在指定时间之前将 pdf 格式的作业严格按命名规范命名，提交到对应网盘链接中，推荐使用 Markdown / LaTeX

# [[Media:AA26-Homework1.pdf|Homework1]] 请在2026年10月14日23点59分之前提交到 [https://box.nju.edu.cn/u/d/df40465a1620457faf29/ 网盘链接] (文件名为'学号_姓名_A1.pdf')
# [[Media:AA26-Homework2.pdf|Homework2]] 请在2026年11月25日23点59分之前提交到 [https://box.nju.edu.cn/u/d/aa9c58ab365a40eaaf73/ 网盘链接] (文件名为'学号_姓名_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/aa2026/Cut.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-cuts-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-cuts-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2026)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2026/Fingerprinting.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-fingerprinting-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-fingerprinting-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2026)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2026)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2026/Hashing.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-hashing-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-hashing-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2026)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2026)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2026)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2026/Concentration.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-concentration-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-concentration-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2026)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2026)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2026/NNS.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-JLT-LSH-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-JLT-LSH-zh.pdf AI生成讲义])
#* [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/aa2026/LLL.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-LLL-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-LLL-zh.pdf AI生成讲义])
# 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

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

2026-11-04T12:18:45Z

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 = 周一 5-6节 (单) 仙Ⅰ-319
周三 5-6节仙Ⅰ-319
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = 周一4-5pm（尹一通 804） 
周四4-5pm（刘景铖 516） 
By appointment
|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 2026. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =

= Course info =
* '''Instructor ''':
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
* '''Teaching Assistant''':
** 于逸潇：[mailto:yixiaoyu@smail.nju.edu.cn <yixiaoyu@smail.nju.edu.cn>]
** 张弈垚：[mailto:zhangyiyao@smail.nju.edu.cn <zhangyiyao@smail.nju.edu.cn>]
* '''Class meeting''':
** 周一 5-6节 1-17周(单) 仙Ⅰ-319
** 周三 5-6节 1-18周仙Ⅰ-319
* '''Office hour''':
** 周一4-5pm（尹一通 804）
** 周四4-5pm（刘景铖 516）
** By appointment
* '''QQ群''': 1098567018

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

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

=== Course materials ===
* [[高级算法 (Fall 2026) / 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.

请在指定时间之前将 pdf 格式的作业严格按命名规范命名，提交到对应网盘链接中，推荐使用 Markdown / LaTeX

# [[Media:AA26-Homework1.pdf|Homework1]] 请在2026年10月14日23点59分之前提交到 [https://box.nju.edu.cn/u/d/df40465a1620457faf29/ 网盘链接] (文件名为'学号_姓名_A1.pdf')

# [[Media:AA26-Homework2.pdf|Homework2]] 请在2026年11月25日23点59分之前提交到 [https://box.nju.edu.cn/u/d/aa9c58ab365a40eaaf73/ 网盘链接] (文件名为'学号_姓名_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/aa2026/Cut.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-cuts-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-cuts-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2026)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2026/Fingerprinting.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-fingerprinting-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-fingerprinting-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2026)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2026)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2026/Hashing.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-hashing-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-hashing-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2026)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2026)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2026)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2026/Concentration.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-concentration-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-concentration-zh.pdf AI生成讲义])
#* [[高级算法 (Fall 2026)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2026)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2026/NNS.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-JLT-LSH-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-JLT-LSH-zh.pdf AI生成讲义])
#* [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/aa2026/LLL.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2026/AA26-note-LLL-en.pdf AI-generated lecture note], [http://tcs.nju.edu.cn/slides/aa2026/AA26-note-LLL-zh.pdf AI生成讲义])
# 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

= 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:AA26-Homework2.pdf

2026-11-04T12:17:41Z

Zhangyiyao:

高级算法 (Fall 2026)/Dimension Reduction

2026-10-22T15:22:58Z

Zhangyiyao: /* Concentration of \chi^2-distribution */

= Metric Embedding=
A '''metric space''' is a pair <math>(X,d)</math>, where <math>X</math> is a set and <math>d</math> is a '''metric''' (or '''distance''') on <math>X</math>, i.e., a function
:<math>d:X^2\to\mathbb{R}_{\ge 0}</math>
such that for any <math>x,y,z\in X</math>, the following axioms hold:
# (identity of indiscernibles) <math>d(x,y)=0\Leftrightarrow x=y</math>
# (symmetry) <math>d(x,y)=d(y,x)</math>
# (triangle inequality) <math>d(x,z)\le d(x,y)+d(y,z)</math>

Let <math>(X,d_X)</math> and <math>(Y,d_Y)</math> be two metric spaces. A mapping
:<math>\phi:X\to Y</math>
is called an '''embedding''' of metric space <math>X</math> into <math>Y</math>. The embedding is said to be with '''distortion''' <math>\alpha\ge1</math> if for any <math>x,y\in X</math> it holds that
:<math>\frac{1}{\alpha}\cdot d(x,y)\le d(\phi(x),\phi(y))\le \alpha\cdot d(x,y)</math>.

In Computer Science, a typical scenario for the metric embedding is as follows. We want to solve some difficult computation problem on a metric space <math>(X,d)</math>. Instead of solving this problem directly on the original metric space, we embed the metric into a new metric space <math>(Y,d_Y)</math> (with low distortion) where the computation problem is much easier to solve.

One particular important case for the metric embedding is to embed a high-dimensional metric space to a new metric space whose dimension is much lower. This is called dimension reduction. This can be very helpful because various very common computation tasks can be very hard to solve on high-dimensional space due to the [https://en.wikipedia.org/wiki/Curse_of_dimensionality curse of dimensionality].

= The Johnson-Lindenstrauss Theorem =
The '''Johnson-Lindenstrauss Theorem''' or '''Johnson-Lindenstrauss Transformation''' (both shorten as '''JLT''') is a fundamental result for dimension reduction in Euclidian space.

Recall that in Euclidian space <math>\mathbf{R}^d</math>, for any two points <math>x,y\in\mathbf{R}^d</math>, the Euclidian distance between them is given by <math>\|x-y\|=\sqrt{(x_1-y_1)^2+(x_2-y_2)^2+\cdots +(x_d-y_d)^2}</math>, where <math>\|\cdot\|=\|\cdot\|_2</math> denotes the Euclidian norm (a.k.a. the <math>\ell_2</math>-norm).

The JLT says that in Euclidian space, it is always possible to embed a set of <math>n</math> points in ''arbitrary'' dimension to <math>O(\log n)</math> dimension with constant distortion. The theorem itself is stated formally as follows.

{{Theorem
|Johnson-Lindenstrauss Theorem, 1984|
:For any <math>0<\epsilon<1/2</math> and any positive integer <math>n</math>, there is a positive integer <math>k=O(\epsilon^{-2}\log n)</math> such that the following holds:
:For any set <math>S\subset\mathbf{R}^d</math> with <math>|S|=n</math>, where <math>d</math> is arbitrary, there is an embedding <math>\phi:\mathbf{R}^d\rightarrow\mathbf{R}^k</math> such that
::<math>\forall x,y\in S,\quad (1-\epsilon)\|x-y\|^2\le\|\phi(x)-\phi(y)\|^2\le(1+\epsilon)\|x-y\|^2</math>.
}}

The Johnson-Lindenstrauss Theorem is usually stated for the <math>\ell_2^2</math>-norm <math>\|\cdot\|^2</math> instead of the Euclidian norm <math>\|\cdot\|</math> itself. Note that this does not change anything other than the constant faction in <math>k=O(\epsilon^{-2}\log n)</math> because <math>(1\pm\epsilon)^{\frac{1}{2}}=1\pm\Theta(\epsilon)</math>. The reason for stating the theorem in <math>\ell_2^2</math>-norm is because <math>\|\cdot\|^2</math> is a sum (rather than a square root) which is easier to analyze.

In fact, the embedding <math>\phi:\mathbf{R}^d\rightarrow\mathbf{R}^k</math> can be as simple as a linear transformation <math>A\in\mathbf{R}^{k\times d}</math> so that <math>\phi(x)=Ax</math> for any <math>x\in\mathbf{R}^{d}</math>.
Therefore, the above theorem can be stated more precisely as follows.

{{Theorem
|Johnson-Lindenstrauss Theorem (linear embedding)|
:For any <math>0<\epsilon<1/2</math> and any positive integer <math>n</math>, there is a positive integer <math>k=O(\epsilon^{-2}\log n)</math> such that the following holds:
:For any set <math>S\subset\mathbf{R}^d</math> with <math>|S|=n</math>, where <math>d</math> is arbitrary, there is a linear transformation <math>A\in\mathbf{R}^{k\times d}</math> such that
::<math>\forall x,y\in S,\quad (1-\epsilon)\|x-y\|^2\le\|Ax-Ay\|^2\le(1+\epsilon)\|x-y\|^2</math>.
}}

The theorem is proved by the probabilistic method. Specifically, we construct a random matrix <math>A\in\mathbf{R}^{k\times d}</math> and show that with high probability (<math>1-O(1/n)</math>) it is a good embedding satisfying:
:<math>\forall x,y\in S,\quad (1-\epsilon)\|x-y\|\le\|Ax-Ay\|\le(1+\epsilon)\|x-y\|</math>.
Therefore, if such random matrix <math>A</math> is efficient to construct, it immediately gives us an efficient randomized algorithm for dimension reduction in the Euclidian space.

There are several such constructions of the random matrix <math>A\in\mathbf{R}^{k\times d}</math>, including:
* projection onto uniform random <math>k</math>-dimensional subspace of <math>\mathbf{R}^{d}</math>; (the original construction of Johnson and Lindenstrauss in 1984; a simplified analysis due to [https://cseweb.ucsd.edu/~dasgupta/papers/jl.pdf Dasgupta and Gupta in 1999])
* random matrix with i.i.d. Gaussian entries; (due to [https://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/IndykM-curse.pdf Indyk and Motwani in 1998])
* random matrix with i.i.d. -1/+1 entries; (due to [https://www.sciencedirect.com/science/article/pii/S0022000003000254?via%3Dihub#BIB8 Achlioptas in 2003])

It was proved by [https://arxiv.org/abs/1609.02094 Kasper Green Larsen and Jelani Nelson in 2016] that the JLT is optimal: there is a set of <math>n</math> points from <math>\mathbf{R}^d</math> such that any embedding <math>\phi:\mathbf{R}^d\rightarrow\mathbf{R}^k</math> having the distortion asserted in the JLT must have dimension <math>k</math> of the target space satisfy <math>k=\Omega(\epsilon^{-2}\log n)</math>.

==JLT via Gaussian matrix==
Here we prove the Johnson-Lindenstrauss theorem with the second construction, by the random matrix <math>A\in\mathbf{R}^{k\times d}</math> with i.i.d. Gaussian entries. The construction of <math>A</math> is very simple:
:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;"
|
*Each entry of <math>A\in\mathbf{R}^{k\times d}</math> is drawn independently from the Gaussian distribution <math>\mathcal{N}(0,1/k)</math>.
|}
Recall that a [https://en.wikipedia.org/wiki/Normal_distribution Gaussian distribution] <math>\mathcal{N}(\mu,\sigma^2)</math> is specified by its mean <math>\mu</math> and standard deviation <math>\sigma</math> such that for a random variable <math>X</math> distributed as <math>\mathcal{N}(\mu,\sigma^2)</math>, we have
:<math>\mathbf{E}[X]=\mu</math> and <math>\mathbf{Var}[X]=\sigma^2</math>,
and the probability density function is given by <math>p(x)=\frac{1}{\sqrt{2\pi\sigma^2}}\mathrm{e}^{-\frac{(x-\mu)^2}{2\sigma^2}}</math>, therefore
:<math>\Pr[X\le t]=\int_{-\infty}^t\frac{1}{\sqrt{2\pi\sigma^2}}\mathrm{e}^{-\frac{(x-\mu)^2}{2\sigma^2}}\,\mathrm{d}x</math>.

Fix any two points <math>x,y</math> out of the <math>n</math> points in <math>S\subset \mathbf{R}^d</math>, if we can show that
:<math>\Pr\left[(1-\epsilon)\|x-y\|^2\le\|Ax-Ay\|^2\le(1+\epsilon)\|x-y\|^2\right]\ge 1-\frac{1}{n^3}</math>,
then by the union bound, the following event
:<math>\forall x,y\in S,\quad (1-\epsilon)\|x-y\|^2\le\|Ax-Ay\|^2\le(1+\epsilon)\|x-y\|^2</math>
holds with probability <math>1-O(1/n)</math>. The Johnson-Lindenstrauss theorem follows.

Furthermore, dividing both sides of the inequalities <math>(1-\epsilon)\|x-y\|^2\le\|Ax-Ay\|^2\le(1+\epsilon)\|x-y\|^2</math> by the factor <math>\|x-y\|^2</math> gives us
:<math>(1-\epsilon)\le\frac{\|Ax-Ay\|^2}{\|x-y\|^2}=\left\|A\frac{(x-y)}{\|x-y\|^2}\right\|^2\le(1+\epsilon)</math>,
where <math>\frac{(x-y)}{\|x-y\|^2}</math> is a unit vector.

Therefore, the Johnson-Lindenstrauss theorem is proved once the following theorem on the unit vector is proved.
{{Theorem
|Theorem (JLT on unit vector)|
:For any positive <math>\epsilon,\delta<1/2</math> there is a positive integer <math>k=O\left(\epsilon^{-2}\log \frac{1}{\delta}\right)</math> such that for the random matrix <math>A\in\mathbf{R}^{k\times d}</math> with each entry drawn independently from the Gaussian distribution <math>\mathcal{N}(0,1/k)</math>, for any unit vector <math>u\in\mathbf{R}^d</math> with <math>\|u\|=1</math>,
::<math>\Pr\left[\left|\|Au\|^2-1\right|>\epsilon\right]<\delta</math>.
}}

For any <math>u\in\mathbf{R}^d</math>, we have <math>\|Au\|^2=\sum_{i=1}^k(Au)_i^2</math>, where the <math>(Au)_i</math>'s are independent of each other, because each
:<math>(Au)_i=\langle A_{i\cdot},u\rangle=\sum_{j=1}^dA_{ij}u_j</math>
is determined by a distinct row vector <math>A_{i\cdot}</math> of the matrix <math>A</math> with independent entries.

Moreover, since each entry <math>A_{ij}\sim\mathcal{N}(0,1/k)</math> independently and recall that for any two independent Gaussian random variables <math>X_1\sim \mathcal{N}(\mu_1,\sigma_1^2)</math> and <math>X_2\sim \mathcal{N}(\mu_2,\sigma_2^2)</math>, their weighted sum <math>aX_1+bX_2</math> follows the Gaussian distribution <math>\mathcal{N}(a\mu_1+b\mu_2,a^2\sigma_1^2+b^2\sigma_2^2)</math>, therefore <math>(Au)_i=\langle A_{i\cdot},u\rangle=\sum_{j=1}^dA_{ij}u_j</math> follows the Gaussian distribution
:<math>(Au)_i\sim\mathcal{N}\left(0,\sum_{j=1}^d\frac{u_j^2}{k}\right)</math>,
which is precisely <math>\mathcal{N}\left(0,\frac{1}{k}\right)</math> if <math>u\in\mathbf{R}^d</math> is a unit vector, i.e. <math>\|u\|^2=\sum_{j=1}^du_j^2=1</math>.

In summary, the random variable <math>\|Au\|^2</math> that we are interested in, can be represented as a sum-of-square form
:<math>\|Au\|^2=\sum_{i=1}^kY_i^2</math>,
where each <math>Y_i=(Au)_i</math> independently follows the Gaussian distribution <math>\mathcal{N}\left(0,\frac{1}{k}\right)</math>.

==Concentration of <math>\chi^2</math>-distribution ==
By the above argument, the Johnson-Lindenstrauss theorem is proved by the following concentration inequality for the sum of the squares of <math>k</math> Gaussian distributions.
{{Theorem
|Chernoff bound for sum-of-squares of Gaussian distributions|
:For any positive <math>\epsilon,\delta<1/2</math> there is a positive integer <math>k=O\left(\epsilon^{-2}\log \frac{1}{\delta}\right)</math> such that for i.i.d. Gaussian random variables <math>Y_1,Y_2,\ldots,Y_k\sim\mathcal{N}(0,1/k)</math>,
::<math>\Pr\left[\left|\sum_{i=1}^kY_i^2-1\right|>\epsilon\right]<\delta</math>.
}}

First, we see that this is indeed a concentration inequality that bounds the deviation of a random variable from its mean.

For each <math>Y_i\sim\mathcal{N}\left(0,\frac{1}{k}\right)</math>, we know that <math>\mathbf{E}[Y_i]=0</math> and <math>\mathbf{Var}[Y_i]=\mathbf{E}[Y_i^2]-\mathbf{E}[Y_i]^2=\frac{1}{k}</math>, thus
:<math>\mathbf{E}[Y_i^2]=\mathbf{Var}[Y_i]+\mathbf{E}[Y_i]^2=\frac{1}{k}</math>.
By linearity of expectation, it holds that
:<math>\mathbf{E}\left[\sum_{i=1}^kY_i^2\right]=\sum_{i=1}^k\mathbf{E}\left[Y_i^2\right]=1</math>.

We prove an equivalent concentration bound stated for the [https://en.wikipedia.org/wiki/Chi-squared_distribution '''<math>\chi^2</math>-distribution'''] (sum of the squares of <math>k</math> '''standard''' Gaussian distributions).

{{Theorem
|Chernoff bound for the <math>\chi^2</math>-distribution|
:For i.i.d. standard Gaussian random variables <math>X_1,X_2,\ldots,X_k\sim\mathcal{N}(0,1)</math>, for <math>0<\epsilon<1</math>,
:*<math>\Pr\left[\sum_{i=1}^kX_i^2>(1+\epsilon)k\right]<\mathrm{e}^{-\epsilon^2k/8}</math>,
:*<math>\Pr\left[\sum_{i=1}^kX_i^2<(1-\epsilon)k\right]<\mathrm{e}^{-\epsilon^2k/8}</math>.
}}

Note that this indeed implies the above concentration bound by setting <math>X_i=\sqrt{k}\cdot Y_i</math> and <math>\delta\ge\mathrm{e}^{-\epsilon^2k/8}</math>.

{{Proof|
We first prove the upper tail. Let <math>\lambda>0</math> be a parameter to be determined.
:<math>
\begin{align}
\Pr\left[\sum_{i=1}^kX_i^2>(1+\epsilon)k\right]
&=\Pr\left[\mathrm{e}^{\lambda \sum_{i=1}^kX_i^2}>\mathrm{e}^{(1+\epsilon)\lambda k}\right]\\
&< \mathrm{e}^{-(1+\epsilon)\lambda k}\cdot \mathbf{E}\left[\mathrm{e}^{\lambda \sum_{i=1}^kX_i^2}\right] && \text{(Markov's inequality)}\\
&= \mathrm{e}^{-(1+\epsilon)\lambda k}\cdot \prod_{i=1}^k \mathbf{E}\left[\mathrm{e}^{\lambda X_i^2}\right]. && \text{(independence)}
\end{align}
</math>
{{Theorem|Proposition|
:For standard Gaussian <math>X\sim\mathcal{N}(0,1)</math>, <math>\mathbf{E}\left[\mathrm{e}^{\lambda X^2}\right]=\frac{1}{\sqrt{1-2\lambda}}</math>.
}}
{{Proof|
:<math>
\begin{align}
\mathbf{E}\left[\mathrm{e}^{\lambda X^2}\right]
&=
\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\mathrm{e}^{\lambda x^2}\mathrm{e}^{-x^2/2}\,\mathrm{d}x\\
&=
\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\mathrm{e}^{-(1-2\lambda)x^2/2}\,\mathrm{d}x\\
&=
\frac{1}{\sqrt{1-2\lambda}}\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\mathrm{e}^{-y^2/2}\,\mathrm{d}y &&(\text{set }y=\sqrt{1-2\lambda}x)\\
&=\frac{1}{\sqrt{1-2\lambda}}.
\end{align}
</math>
The last equation is because <math>\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}\mathrm{e}^{-y^2/2}\,\mathrm{d}y</math> is the total probability mass of a standard Gaussian distribution (which is obviously 1).
}}
Then continue the above calculation:
:<math>
\begin{align}
\Pr\left[\sum_{i=1}^kX_i^2>(1+\epsilon)k\right]
&<
\mathrm{e}^{-(1+\epsilon)\lambda k}\cdot \left(\frac{1}{\sqrt{1-2\lambda}}\right)^k\\
&=
\mathrm{e}^{-\epsilon\lambda k}\cdot \left(\frac{\mathrm{e}^{-\lambda}}{\sqrt{1-2\lambda}}\right)^k\\
&\le
\mathrm{e}^{-\epsilon\lambda k + 2\lambda^2 k} && (\text{for }\lambda<1/4)\\
&=
\mathrm{e}^{-\epsilon^2 k/8}. && (\text{by setting the stationary point }\lambda=\epsilon/4)
\end{align}
</math>
This proved the upper tail. The lower tail can be symmetrically proved by optimizing over a parameter <math>\lambda<0</math>.
}}

As we argued above, this finishes the proof of the Johnson-Lindenstrauss Theorem.

= Nearest Neighbor Search (NNS)=
{{Theorem|Nearest Neighbor Search (NNS)|
*'''Data''': a set <math>S</math> of <math>n</math> points <math>y_1,y_2,\ldots,y_n\in X</math> from a metric space <math>(X,\mathrm{dist})</math>;
*'''Query''': a point <math>x\in X</math>;
*'''Answer''': a nearest neighbor of the query point <math>x</math> among all data points, i.e. a data point <math>y_{i^*}\in S</math> such that <math>\mathrm{dist}(x,y_{i^*})=\min_{y_i\in S}\mathrm{dist}(x,y_i)</math>.
}}

{{Theorem|<math>c</math>-ANN (Approximate Nearest Neighbor)|
:<math>c>1</math> is an approximate ratio.
*'''Data''': a set <math>S</math> of <math>n</math> points <math>y_1,y_2,\ldots,y_n\in X</math> from a metric space <math>(X,\mathrm{dist})</math>;
*'''Query''': a point <math>x\in X</math>;
*'''Answer''': a <math>c</math>-approximate nearest neighbor of the query point <math>x</math> among all data points, i.e. a data point <math>y_{i^*}\in S</math> such that <math>\mathrm{dist}(x,y_{i^*})\le c\, \min_{y_i\in S}\mathrm{dist}(x,y_i)</math>.
}}

{{Theorem|<math>(c,r)</math>-ANN (Approximate ''Near'' Neighbor)|
:<math>c>1</math> is an approximate ratio; <math>r>0</math> is a radius;
*'''Data''': a set <math>S</math> of <math>n</math> points <math>y_1,y_2,\ldots,y_n\in X</math> from a metric space <math>(X,\mathrm{dist})</math>;
*'''Query''': a point <math>x\in X</math>;
*'''Answer''': <math>
\begin{cases}
\text{a data point }y_{i^*}\in S\text{ such that }\mathrm{dist}(x,y_{i^*})\le c\cdot r & \text{if }\exists y_i\in S, \mathrm{dist}(x,y_{i})\le r,\\
\bot & \text{if }\forall y_i\in S, \mathrm{dist}(x,y_{i})>c\cdot r,\\
\text{arbitrary} & \text{otherwise}.
\end{cases}
</math>
}}

{{Theorem|Theorem|
:For any instance <math>S=\{y_1,y_2,\ldots,y_n\}</math> of the nearest neighbor problem, let <math>D_{\min}\triangleq\min_{y_i,y_j\in S}\mathrm{dist}(y_i,y_j)</math>, <math>D_{\max}\triangleq\max_{y_i,y_j\in S}\mathrm{dist}(y_i,y_j)</math> and <math>R\triangleq \frac{D_{\max}}{D_{\min}}</math>.
:Suppose that for any <math>r>0</math> there always exists a data structure for the <math>(c,r)</math>-ANN problem, using space at most <math>s</math>, answering each query in time <math>t</math>, correctly with probability <math>1-\delta</math>.
:Then there exists a data structure for the <math>c</math>-ANN problem, using space <math>O(s\log_c R)</math>, answering each query in time <math>O(t\log\log_c R)</math>, correctly with probability <math>1-O(\delta\log\log_c R)</math>.
}}

==Solving ANN by dimension reduction==

= Locality-Sensitive Hashing (LSH)=

高级算法 (Fall 2026)

2026-08-20T06:44:18Z

Zhangyiyao: /* Course info */

Main Page

2026-08-20T06:33:12Z

Zhangyiyao:

This is a course/seminar wiki run by the [http://tcs.nju.edu.cn theory group] in the Department of Computer Science and Technology at Nanjing University.

== Home Pages for Courses and Seminars==
;Current semester & Summer school
* '''<big>[[计算理论之美 (Summer 2026) | 计算理论之美暑期学校 2026]]</big>'''

* [[高级算法 (Fall 2026)|高级算法 Advanced Algorithms (Fall 2026)]]

* [[高级算法 (Spring 2026)|高级算法 Advanced Algorithms (Spring 2026, Suzhou)]]

* [[组合数学 (Spring 2026)|组合数学 Combinatorics (Spring 2026)]]

* [[计算复杂性 (Spring 2026)|计算复杂性 Computational Complexity (Spring 2026)]]

* [[计算方法 Numerical method (Spring 2026)|计算方法 Numerical method (Spring 2026)]]

* [[概率论与数理统计 (Spring 2026)|概率论与数理统计 Probability Theory (Spring 2026)]]

;Past courses

* Advanced Algorithms: [[高级算法 (Fall 2026)|Fall 2026]], [[高级算法 (Fall 2025)|Fall 2025]], [[高级算法 (Spring 2025)|Spring 2025(Suzhou)]], [[高级算法 (Fall 2024)|Fall 2024]], [[高级算法 (Fall 2023)|Fall 2023]], [[高级算法 (Fall 2022)|Fall 2022]], [[高级算法 (Fall 2021)|Fall 2021]], [[高级算法 (Fall 2020)|Fall 2020]], [[高级算法 (Fall 2019)|Fall 2019]], [[高级算法 (Fall 2018)|Fall 2018]], [[高级算法 (Fall 2017)|Fall 2017]], [[随机算法 \ 高级算法 (Fall 2016)|Fall 2016]].

*Algorithm Design and Analysis: [https://tcs.nju.edu.cn/shili/courses/2024spring-algo/ Spring 2024]

* Combinatorics: [[组合数学 (Spring 2025)|Spring 2025]], [[组合数学 (Spring 2024)|Spring 2024]], [[组合数学 (Spring 2023)|Spring 2023]], [[组合数学 (Fall 2019)|Fall 2019]], [[组合数学 (Fall 2017)|Fall 2017]], [[组合数学 (Fall 2016)|Fall 2016]], [[组合数学 (Fall 2015)|Fall 2015]], [[组合数学 (Spring 2014)|Spring 2014]], [[组合数学 (Spring 2013)|Spring 2013]], [[组合数学 (Fall 2011)|Fall 2011]], [[Combinatorics (Fall 2010)|Fall 2010]].

* Computational Complexity: [[计算复杂性 (Spring 2025)|Spring 2025]], [[计算复杂性 (Spring 2024)|Spring 2024]], [[计算复杂性 (Spring 2023)|Spring 2023]], [[计算复杂性 (Fall 2019)|Fall 2019]], [[计算复杂性 (Fall 2018)|Fall 2018]].

* Foundations of Data Science: [[数据科学基础 (Fall 2025)|Fall 2025]], [[数据科学基础 (Fall 2024)|Fall 2024]]

* Numerical Method: [[计算方法 Numerical method (Spring 2025)|Spring 2025]], [[计算方法 Numerical method (Spring 2024)|Spring 2024]], [[计算方法 Numerical method (Spring 2023)|Spring 2023]], [https://liuexp.github.io/numerical.html Spring 2022].

* Probability Theory: [[概率论与数理统计 (Spring 2025)|Spring 2025]], [[概率论与数理统计 (Spring 2024)|Spring 2024]], [[概率论与数理统计 (Spring 2023)|Spring 2023]].

* Quantum Computation: [[量子计算 (Spring 2022)|Spring 2022]], [[量子计算 (Spring 2021)|Spring 2021]], [[量子计算 (Fall 2019)|Fall 2019]].

* Randomized Algorithms: [[随机算法 (Fall 2015)|Fall 2015]], [[随机算法 (Spring 2014)|Spring 2014]], [[随机算法 (Spring 2013)|Spring 2013]], [[随机算法 (Fall 2011)|Fall 2011]], [[Randomized Algorithms (Spring 2010)|Spring 2010]].

;Past seminars, workshops and summer schools
*计算理论之美暑期学校: [[计算理论之美 (Summer 2025)|2025]], [[计算理论之美 (Summer 2024)|2024]], [[计算理论之美 (Summer 2023)|2023]], [[计算理论之美 (Summer 2021)|2021]]
*[[Theory Seminar|理论计算机科学讨论班]]
*[[Study Group|理论计算机科学学习小组]]
*[[TCSPhD2020| 理论计算机科学优秀博士生论坛2020]]
*[[Quantum|量子算法与物理实现研讨会]]
*Theory Day: [[Theory@Suzhou 2025 | 2025 (Suzhou)]], [[Theory@Nanjing 2019|2019]], [[Theory@Nanjing 2018|2018]], [[Theory@Nanjing 2017|2017]]
*[[\Delta Seminar on Logic, Philosophy, and Computer Science|Δ Seminar on Logic, Philosophy, and Computer Science]]
*[[近似算法讨论班 (Fall 2011)|近似算法 Approximation Algorithms, Fall 2011.]]

; 其它链接
* [[General Circulation(Fall 2025)|大气环流 General Circulation of the Atmosphere, Fall 2025]]
* [[General Circulation(Fall 2024)|大气环流 General Circulation of the Atmosphere, Fall 2024]]

* [[概率论 (Summer 2014)| 概率与计算 (上海交大 Summer 2014)]]

高级算法 (Fall 2026) / Course materials

2026-08-20T06:31:00Z

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 2026)

2026-08-20T06:30:23Z

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

高级算法 (Fall 2025)

2025-08-23T06:32:01Z

高级算法 (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>