高级算法 (Spring 2026): Difference between revisions
Jump to navigation
Jump to search
Liumingmou (talk | contribs) |
Liumingmou (talk | contribs) |
||
| (5 intermediate revisions by the same user not shown) | |||
| Line 59: | Line 59: | ||
}} | }} | ||
This is the webpage for the ''Advanced Algorithms'' class of spring | This is the webpage for the ''Advanced Algorithms'' class of spring 2026. Students who take this class should check this page periodically for content updates and new announcements. | ||
= 通知 = | = 通知 = | ||
| Line 68: | Line 68: | ||
= 课程信息 = | = 课程信息 = | ||
* '''任课教师''': | * '''任课教师''': | ||
:* [https://liumingmou.github.io 刘明谋]：[mailto:lmm@nju.edu.cn | :* [https://liumingmou.github.io 刘明谋]：[mailto:lmm@nju.edu.cn 📧]，南雍-西229 | ||
* '''助教''': | * '''助教''': | ||
** | ** 王思齐：[mailto:siqi_wang@smail.nju.edu.cn 📧] | ||
** | ** 齐世毅：[mailto:1083951258@qq.com 📧] | ||
* '''课程时间地点''': | * '''课程时间地点''': | ||
** 周一，9am-12pm，苏教B207 | ** 周一，9am-12pm，苏教B207 | ||
| Line 84: | Line 84: | ||
* 哈希表与面向大数据的现代计算场景 | * 哈希表与面向大数据的现代计算场景 | ||
* 测度的集中与处理高维数据 | * 测度的集中与处理高维数据 | ||
* | * 最大流与线性规划 | ||
* 其他重要话题 | * 其他重要话题 | ||
| Line 109: | Line 109: | ||
= 课后作业 = | = 课后作业 = | ||
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time. | Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time. | ||
*[[高级算法_(Spring_2026)/作业1|作业1]]（每堂课之后更新）DDL to be announced. | |||
= 课件及相关阅读资料 = | = 课件及相关阅读资料 = | ||
# Fingerprinting | # [https://box.nju.edu.cn/f/980d814e4ad64285a640/ Fingerprinting] | ||
#* Polynomial Identity Testing | #* Polynomial Identity Testing | ||
#* Communication Complexity (Equality) | #* Communication Complexity (Equality) | ||
#* Application: Bipartite Perfect Matching, Checking Matrix Multiplication | #* Application: Bipartite Perfect Matching, Checking Matrix Multiplication | ||
#* Karp-Rabin Algorithm (string-searching), Lipton’s Algorithm (checking identity of multisets) | #* Karp-Rabin Algorithm (string-searching), Lipton’s Algorithm (checking identity of multisets) | ||
# [https://box.nju.edu.cn/f/fcf9e2b3051e443fb324/ Sketching] | |||
#* Morris' Algorithm | |||
#** mean trick, median trick | |||
#* Counting Distinct Elements: min sketch, Flajolet-Martin algorithm, bottom-<math>k</math> algorithm, HyperLogLog | |||
#* Heavy Hitter & Point Query: count-min sketch | |||
#* 2nd Frequency Moments Estimator: count sketch | |||
#** <math>\ell_2</math> point query with count sketch | |||
#* Approximate Membership: Bloom filter | |||
= Related Online Courses= | = Related Online Courses= | ||
Latest revision as of 12:51, 8 March 2026
| 任课教师 | |
|---|---|
| 刘明谋 | |
| 电子邮件 | lmm@nju.edu.cn |
| 办公室 | 南雍-西229 |
| 课程时间地点 | |
| 教室 |
周一，9am-12pm 苏教B207 |
| 答疑时间 |
周五，2pm-5pm 南雍-西229 |
| 教材 | |
 | |
|
Motwani and Raghavan. Randomized Algorithms. Cambridge Univ Press, 1995. | |
 | |
|
Vazirani. Approximation Algorithms. Springer-Verlag, 2001. | |
This is the webpage for the Advanced Algorithms class of spring 2026. Students who take this class should check this page periodically for content updates and new announcements.
通知
- (2026/3/2) 第一堂课
课程信息
- 任课教师:
教学大纲
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。
课程内容分为五大部分：
- 基于哈希的大数据算法
- 哈希表与面向大数据的现代计算场景
- 测度的集中与处理高维数据
- 最大流与线性规划
- 其他重要话题
先修课程
- 必须：离散数学，概率论，线性代数。
- 推荐：算法设计与分析。
课程教材
本门课较为前沿，大部分课程内容还没有进入任何教材。以下教材和参考书仅作为参考。
成绩
- 课程成绩：本课程将会有若干次作业和一次期末考核。最终成绩将由平时作业成绩和期末考核成绩综合得出。
- 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。
学术诚信 Academic Integrity
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。
作业完成的原则：署你名字的工作必须是你个人的贡献，任何不是由你完成的部分都必须明确标注，特别是由AI生成的部分，否则就涉嫌抄袭。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。符合规则的讨论与致谢将不会影响得分。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。
本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 ACM Policy on Plagiarism的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。
学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。
课后作业
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.
- 作业1（每堂课之后更新）DDL to be announced.
课件及相关阅读资料
- Fingerprinting
- Polynomial Identity Testing
- Communication Complexity (Equality)
- Application: Bipartite Perfect Matching, Checking Matrix Multiplication
- Karp-Rabin Algorithm (string-searching), Lipton’s Algorithm (checking identity of multisets)
- Sketching
- Morris' Algorithm
- mean trick, median trick
- Counting Distinct Elements: min sketch, Flajolet-Martin algorithm, bottom-[math]\displaystyle{ k }[/math] algorithm, HyperLogLog
- Heavy Hitter & Point Query: count-min sketch
- 2nd Frequency Moments Estimator: count sketch
- [math]\displaystyle{ \ell_2 }[/math] point query with count sketch
- Approximate Membership: Bloom filter
- Morris' Algorithm
Related Online Courses
- Advanced Algorithms by Alexandr Andoni at Columbia University.
- Advanced Approximation Algorithms by Anupam Gupta at CMU.
- Advanced Algorithms by Ankur Moitra at MIT.
- Advanced Algorithms by David Karger at MIT.
- Algorithms for Big Data by David Woodruff at CMU.
- Sketching Algorithms by Jelani Nelson at UC Berkeley.
- The Modern Algorithmic Toolbox by Tim Roughgarden and Gregory Valiant at Stanford.
- Advanced Algorithm Design by Pravesh Kothari and Christopher Musco at Princeton.
- Linear and Semidefinite Programming (Advanced Algorithms) by Anupam Gupta and Ryan O'Donnell at CMU.
- CS Theory Toolkit by Ryan O'Donnell at CMU.
- Eigenvalues and Polynomials by Lap Chi Lau at University of Waterloo.