高级算法 (Spring 2025)
| 任课教师 | |
|---|---|
| 刘明谋 | |
| 电子邮件 | lmm@nju.edu.cn |
| 办公室 | 南雍-东207 |
| 课程时间地点 | |
| 教室 |
周三, 2pm-5pm 南雍-西446 |
| 答疑时间 |
周二, 8pm-10pm, 南雍-东207 |
| 教材 | |
 | |
|
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 2025. Students who take this class should check this page periodically for content updates and new announcements.
通知
- (2025/2/19) 第一堂课
课程信息
- 任课教师:
- 刘明谋：<lmm@nju.edu.cn>，南雍-东207
- 助教:
- TBA
- 课程时间地点:
- 周三, 2pm-5pm, 南雍-西446
- 答疑时间: 周二, 7pm-9pm, 南雍-东207
- QQ群: 1029885231
教学大纲
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。
课程内容分为五大部分：
- 基于哈希的大数据算法
- 哈希表与面向大数据的现代计算场景
- 测度的集中与处理高维数据
- 最大流与线性/整数规划
- 其他重要话题
先修课程
- 必须：离散数学，概率论，线性代数。
- 推荐：算法设计与分析。
课程教材
成绩
- 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
- 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。
学术诚信
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。
作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。
本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 ACM Policy on Plagiarism的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。
学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。
课后作业
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.
TBA
课件及相关阅读资料
Related Online Courses
- 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.
- The "Foundations of Data Science" book by Avrim Blum, John Hopcroft, and Ravindran Kannan.