高级算法 (Fall 2021)
| Instructor | |
|---|---|
| 尹一通 | |
| yinyt@nju.edu.cn | |
| office | 计算机系 804 |
| Class | |
| Class meetings |
Tuesday, 2pm-5pm 逸B-207 |
| Office hours |
Wednesday, 4pm-6pm 804 |
| Textbooks | |
 | |
|
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 fall 2020. Students who take this class should check this page periodically for content updates and new announcements.
Announcement
- (2020/09/30) 第一次作业已发布，10月14日星期三课上交。
- (2020/11/04) 第二次作业已发布，11月18日星期三课上交。
- (2020/11/20) 此前几节课的slides已经更新为2020最新版
- (2020/11/20) 11月9日课上有同学遗失无线耳机一副，请该同学课间来找老师
- (2020/12/09) 第三次作业已发布，12月23日星期三课上交。
- (2020/12/23) 第四次作业已发布，1月3日星期日习题课上交。
- (2020/12/30) 1月3日星期日晚18:30在上课教室仙I-319上习题课。
- (2020/01/05) 1月5日星期二早8:00-10:00进行期末考试，本科生考试地点为仙2-116，研究生考试地点为图123
Course info
- Instructor : 尹一通 (homepage)
- email: yinyt@nju.edu.cn
- Teaching Assistant: 王天行 (wangtx@smail.nju.edu.cn), 王淳扬 (wcysai@foxmail.com)
- Class meeting: Wednesday 10am-12pm, 仙I-319; Monday (biweekly) 8am-10am, 仙I-319.
- Office hour: Wednesday 4pm-6pm, 计算机系 804.
Syllabus
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。
先修课程 Prerequisites
- 必须：离散数学，概率论，线性代数。
- 推荐：算法设计与分析。
Course materials
成绩 Grades
- 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
- 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。
学术诚信 Academic Integrity
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。
作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。
本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 ACM Policy on Plagiarism的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。
学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。
Assignments
- Problem Set 1 due on 2020/10/14 课上交纸质版作业（可以打印电子稿）. 第一次作业提交名单
- Problem Set 2 due on 2020/11/18 课上交纸质版作业（可以打印电子稿）. 第二次作业提交名单
- Problem Set 3 due on 2020/12/23 课上交纸质版作业（可以打印电子稿）. 第三次作业提交名单
- Problem Set 4 due on 2020/1/3 习题课上交纸质版作业（可以打印电子稿）. 第四次作业提交名单
Lecture Notes
- Min-Cut and Max-Cut (slides)
- Balls into bins and Chernoff bound (slides)
- Concentration of measure (slides)
- Fingerprinting (slides)
- Hashing and Sketching (slides)
- Dimension Reduction (slides)
- Greedy and Local Search (slides)
- Rounding Dynamic Programs (slides)
- Rounding Linear Programs (slides)
- The Primal-Dual Schema (slides)
- SDP based algorithms and UGC hardness(slides)
- Vazirani book Chap. 26
- UGC-hardness of MAX-CUT (Prof. Penghui Yao's slides and DIMACS notes on PCP theory)
- Sum-of-Squares (SoS) Proofs (slides)
- SoS SDP course Lecture 1.1, 1.2, 2.1
- Lovász Local Lemma (slides)
- Markov Chain Monte Carlo (MCMC) methods (slides)
Related Online Courses
- Advanced Algorithms by Ankur Moitra at MIT.
- Advanced Algorithms by David Karger and Aleksander Mądry at MIT.
- The Modern Algorithmic Toolbox by Tim Roughgarden and Gregory Valiant at Stanford.
- Advanced Algorithm Design by Sanjeev Arora at Princeton.
- Linear and Semidefinite Programming (Advanced Algorithms) by Anupam Gupta and Ryan O'Donnell at CMU.
- The "Foundations of Data Science" book by Avrim Blum, John Hopcroft, and Ravindran Kannan.