高级算法 (Fall 2021): Difference between revisions
Jump to navigation
Jump to search
imported>Etone Created page with "{{Infobox |name = Infobox |bodystyle = |title = <font size=3>高级算法 <br>Advanced Algorithms</font> |titlestyle = |image = |imagestyle =..." |
|||
| (87 intermediate revisions by 3 users not shown) | |||
| Line 31: | Line 31: | ||
|header6 = | |header6 = | ||
|label6 = Class meetings | |label6 = Class meetings | ||
|data6 = Tuesday, 2pm-5pm <br> | |data6 = Tuesday, 2pm-5pm <br> 腾讯会议：598 944 8767 | ||
|header7 = | |header7 = | ||
|label7 = Place | |label7 = Place | ||
| Line 57: | Line 57: | ||
}} | }} | ||
This is the webpage for the ''Advanced Algorithms'' class of fall | This is the webpage for the ''Advanced Algorithms'' class of fall 2021. Students who take this class should check this page periodically for content updates and new announcements. | ||
= Announcement = | = Announcement = | ||
* ( | * (2021/08/31) 今天在线课程的slides和录屏视频已经上传，参见lecture notes部分。 | ||
* ( | * (2021/09/15) 第一次作业已发布，请在 2021/9/28 上课之前提交到 [mailto:njuadvalg21@163.com njuadvalg21@163.com] (文件名为'<font color=red >学号_姓名_A1.pdf</font>'). | ||
* (2021/11/25) 下周（11月30日）开始，课程改为线上，线上腾讯会议号仍为 598 944 8767。 | |||
* (2021/12/21) <font color=red size=4> 2022年1月4日，下午2点，进行一次线上作业讲解和答疑。线上腾讯会议号仍为 598 944 8767。</font> | |||
* ( | |||
* ( | |||
= Course info = | = Course info = | ||
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage]) | * '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage]) | ||
:*'''email''': yinyt@nju.edu.cn | :*'''email''': yinyt@nju.edu.cn | ||
* '''Teaching Assistant''': | * '''Teaching Assistant''': | ||
* '''Class meeting''': | ** 陈小羽([mailto:chenxiaoyu233@smail.nju.edu.cn chenxiaoyu233@smail.nju.edu.cn]) | ||
* '''Office hour''': | ** 吴旭东 ([mailto:xdwu@smail.nju.edu.cn xdwu@smail.nju.edu.cn]) | ||
* '''Mailbox for Homework''': [mailto:njuadvalg21@163.com njuadvalg21@163.com] | |||
* '''Class meeting''': Tuesday, 2pm-5pm | |||
:* '''线上直播''': 腾讯会议 598 944 8767 | |||
:* '''线下''': 逸B-207 | |||
* '''Office hour''': 待定 | |||
:* '''QQ群''': 893909781 | |||
= Syllabus = | = Syllabus = | ||
| Line 100: | Line 102: | ||
= Assignments = | = Assignments = | ||
*[[高级算法 (Fall | *[[高级算法 (Fall 2021)/Problem Set 1|Problem Set 1]] 请在 2021/9/28 上课之前提交到 [mailto:njuadvalg21@163.com njuadvalg21@163.com] (文件名为'<font color=red >学号_姓名_A1.pdf</font>'). [[高级算法 (Fall 2021)/第一次作业提交名单|第一次作业提交名单]]. | ||
*[[高级算法 (Fall | * '''Reading assignment''': Mitzenmacher and Upfal, ''Probability and Computing, second edition'', '''Chapter 17''' "Balanced Allocations and Cuckoo Hashing", 请在一周内读完 | ||
*[[高级算法 (Fall | * [[高级算法 (Fall 2021)/Problem Set 2|Problem Set 2]] 请在 2021/11/2 上课之前提交到 [mailto:njuadvalg21@163.com njuadvalg21@163.com] (文件名为'<font color=red >学号_姓名_A2.pdf</font>'). [[高级算法 (Fall 2021)/第二次作业提交名单|第二次作业提交名单]]. | ||
*[[高级算法 (Fall | * [[高级算法 (Fall 2021)/Problem Set 3|Problem Set 3]] 请在 2021/12/7 上课之前提交到 [mailto:njuadvalg21@163.com njuadvalg21@163.com] (文件名为'<font color=red >学号_姓名_A3.pdf</font>'). [[高级算法 (Fall 2021)/第三次作业提交名单|第三次作业提交名单]]. | ||
* [[高级算法 (Fall 2021)/Problem Set 4|Problem Set 4]] 请在 2022/1/3 23：59之前提交到 [mailto:njuadvalg21@163.com njuadvalg21@163.com] (文件名为'<font color=red >学号_姓名_A4.pdf</font>'). [[高级算法 (Fall 2021)/第四次作业提交名单|第四次作业提交名单]]. | |||
= Lecture Notes = | = Lecture Notes = | ||
# [[高级算法 (Fall | # [[高级算法 (Fall 2021)/Min-Cut and Max-Cut|Min-Cut and Max-Cut]] ([http://tcs.nju.edu.cn/slides/aa2021/Cut.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_0.1.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_0.2.mp4 video2] [http://tcs.nju.edu.cn/slides/aa2021/meeting_0.3.mp4 video3]) | ||
#: [[高级算法 (Fall | #: [[高级算法 (Fall 2021)/Probability Basics|Probability basics]] | ||
# [[高级算法 (Fall | # [[高级算法 (Fall 2021)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2021/Fingerprinting.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_1.1.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_1.2.mp4 video2] [http://tcs.nju.edu.cn/slides/aa2021/meeting_1.3.mp4 video3]) | ||
#: [[高级算法 (Fall | #: [[高级算法 (Fall 2021)/Finite Field Basics|Finite field basics]] | ||
# [[高级算法 (Fall | # [[高级算法 (Fall 2021)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2021/Hashing.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_2.1.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_2.2.mp4 video2] [http://tcs.nju.edu.cn/slides/aa2021/meeting_2.3.mp4 video3] [http://tcs.nju.edu.cn/slides/aa2021/meeting_3.1.mp4 video4] [http://tcs.nju.edu.cn/slides/aa2021/meeting_3.2.mp4 video5]) | ||
#: [[高级算法 (Fall | #: [[高级算法 (Fall 2021)/Basic tail inequalities|Basic tail inequalities]] | ||
# | # [[高级算法 (Fall 2021)/Balls into bins|Balls into bins]] ([http://tcs.nju.edu.cn/slides/aa2021/Balls2bins.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_3.3.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_4.1.mp4 video2] [http://tcs.nju.edu.cn/slides/aa2021/meeting_4.2.mp4 video3] [http://tcs.nju.edu.cn/slides/aa2021/meeting_4.3.mp4 video4]) | ||
#: [[高级算法 (Fall | #: [[高级算法 (Fall 2021)/Limited independence|Limited independence]] | ||
# | # [[高级算法 (Fall 2021)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2021/Concentration.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_5.1.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_5.2.mp4 video2] [http://tcs.nju.edu.cn/slides/aa2021/meeting_5.3.mp4 video3]) | ||
# [[高级算法 (Fall | #: [[高级算法 (Fall 2021)/Conditional expectations|Conditional expectations]] | ||
# [[高级算法 (Fall 2021)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2021/NNS.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_6.1.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_6.2.mp4 video2] [http://tcs.nju.edu.cn/slides/aa2021/meeting_6.3.mp4 video3] [http://tcs.nju.edu.cn/slides/aa2021/meeting_7.1.mp4 video4] [http://tcs.nju.edu.cn/slides/aa2021/meeting_7.2.mp4 video5]) | |||
#: [http://people.seas.harvard.edu/~minilek/madalgo2015/index.html Jelani Nelson's note on Johnson-Lindenstrauss Theorem] | #: [http://people.seas.harvard.edu/~minilek/madalgo2015/index.html Jelani Nelson's note on Johnson-Lindenstrauss Theorem] | ||
#: [http://people.csail.mit.edu/gregory/annbook/introduction.pdf An introduction of LSH] | #: [http://people.csail.mit.edu/gregory/annbook/introduction.pdf An introduction of LSH] | ||
# [[高级算法 (Fall | # [[高级算法 (Fall 2021)/Greedy and Local Search|Greedy and Local Search]] ([http://tcs.nju.edu.cn/slides/aa2021/Greedy.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_8.1.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_8.2.mp4 video2] [http://tcs.nju.edu.cn/slides/aa2021/meeting_8.3.mp4 video3] [http://tcs.nju.edu.cn/slides/aa2021/meeting_9.1.mp4 video4]) | ||
# Rounding Dynamic Programs ([http://tcs.nju.edu.cn/slides/ | #: [https://theory.stanford.edu/~jvondrak/CS369P/lec16.pdf Jan Vondrák's notes] and [https://theory.stanford.edu/~jvondrak/data/submod-tutorial-1.pdf slides] on submodular optimization | ||
#: [http://tcs.nju.edu.cn/notes/DP.Note.pdf Vazirani book Chap. 8 | # Rounding Dynamic Programs ([http://tcs.nju.edu.cn/slides/aa2021/DP.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_9.2.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_9.3.mp4 video2]) | ||
# Rounding Linear Programs ([http://tcs.nju.edu.cn/slides/ | #: [http://tcs.nju.edu.cn/notes/DP.Note.pdf Vazirani book Chap. 8] | ||
# Rounding Linear Programs ([http://tcs.nju.edu.cn/slides/aa2021/LP.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_10.1.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_10.2.mp4 video2] [http://tcs.nju.edu.cn/slides/aa2021/meeting_10.3.mp4 video3]) | |||
#: [http://tcs.nju.edu.cn/notes/LP.Note.pdf Vazirani book Chap. 14, 16] | #: [http://tcs.nju.edu.cn/notes/LP.Note.pdf Vazirani book Chap. 14, 16] | ||
# The Primal-Dual Schema ([http://tcs.nju.edu.cn/slides/ | #: [https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/notes/lpsdp.pdf Notes on LP and SDP by Anupam Gupta and Ryan O’Donnell] | ||
# The Primal-Dual Schema ([http://tcs.nju.edu.cn/slides/aa2021/Primal-Dual.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_11.1.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_11.2.mp4 video2] [http://tcs.nju.edu.cn/slides/aa2021/meeting_11.3.mp4 video3] [http://tcs.nju.edu.cn/slides/aa2021/meeting_12.1.mp4 video4] [http://tcs.nju.edu.cn/slides/aa2021/meeting_12.2.mp4 video5]) | |||
#: [http://tcs.nju.edu.cn/notes/DualityNote.pdf Vazirani book Chap. 12, 15] | #: [http://tcs.nju.edu.cn/notes/DualityNote.pdf Vazirani book Chap. 12, 15] | ||
# | # SDP based algorithms ([http://tcs.nju.edu.cn/slides/aa2021/SDP.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_12.3.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_12.4.mp4 video2]) | ||
#: [http://tcs.nju.edu.cn/notes/SDP.Note.pdf Vazirani book Chap. 26] | #: [http://tcs.nju.edu.cn/notes/SDP.Note.pdf Vazirani book Chap. 26] | ||
# | # ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2021/LLL.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_13.1.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_13.2.mp4 video2] [http://tcs.nju.edu.cn/slides/aa2021/meeting_13.3.mp4 video3]) | ||
#: [https://people.eecs.berkeley.edu/~sinclair/cs271/n22.pdf Alistair Sinclair's Lecture Notes on LLL] | |||
#:[ | #: [https://www.cc.gatech.edu/~vigoda/6550/Notes/Lec16.pdf Alistair Sinclair's Lecture Notes on Algorithmic LLL] | ||
# Markov Chain Monte Carlo (MCMC) methods ([http://tcs.nju.edu.cn/slides/aa2021/MCMC.pdf slides]) ([http://tcs.nju.edu.cn/slides/aa2021/meeting_14.1.mp4 video1] [http://tcs.nju.edu.cn/slides/aa2021/meeting_14.2.mp4 video2] [http://tcs.nju.edu.cn/slides/aa2021/meeting_14.3.mp4 video3]) | |||
= Related Online Courses= | = Related Online Courses= | ||
Latest revision as of 05:54, 11 October 2022
| Instructor | |
|---|---|
| 尹一通 | |
| yinyt@nju.edu.cn | |
| office | 计算机系 804 |
| Class | |
| Class meetings |
Tuesday, 2pm-5pm 腾讯会议：598 944 8767 |
| 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 2021. Students who take this class should check this page periodically for content updates and new announcements.
Announcement
- (2021/08/31) 今天在线课程的slides和录屏视频已经上传，参见lecture notes部分。
- (2021/09/15) 第一次作业已发布，请在 2021/9/28 上课之前提交到 njuadvalg21@163.com (文件名为'学号_姓名_A1.pdf').
- (2021/11/25) 下周（11月30日）开始，课程改为线上，线上腾讯会议号仍为 598 944 8767。
- (2021/12/21) 2022年1月4日，下午2点，进行一次线上作业讲解和答疑。线上腾讯会议号仍为 598 944 8767。
Course info
- Instructor : 尹一通 (homepage)
- email: yinyt@nju.edu.cn
- Teaching Assistant:
- Mailbox for Homework: njuadvalg21@163.com
- Class meeting: Tuesday, 2pm-5pm
- 线上直播: 腾讯会议 598 944 8767
- 线下: 逸B-207
- Office hour: 待定
- QQ群: 893909781
Syllabus
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。
先修课程 Prerequisites
- 必须：离散数学，概率论，线性代数。
- 推荐：算法设计与分析。
Course materials
成绩 Grades
- 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
- 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。
学术诚信 Academic Integrity
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。
作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。
本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 ACM Policy on Plagiarism的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。
学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。
Assignments
- Problem Set 1 请在 2021/9/28 上课之前提交到 njuadvalg21@163.com (文件名为'学号_姓名_A1.pdf'). 第一次作业提交名单.
- Reading assignment: Mitzenmacher and Upfal, Probability and Computing, second edition, Chapter 17 "Balanced Allocations and Cuckoo Hashing", 请在一周内读完
- Problem Set 2 请在 2021/11/2 上课之前提交到 njuadvalg21@163.com (文件名为'学号_姓名_A2.pdf'). 第二次作业提交名单.
- Problem Set 3 请在 2021/12/7 上课之前提交到 njuadvalg21@163.com (文件名为'学号_姓名_A3.pdf'). 第三次作业提交名单.
- Problem Set 4 请在 2022/1/3 23：59之前提交到 njuadvalg21@163.com (文件名为'学号_姓名_A4.pdf'). 第四次作业提交名单.
Lecture Notes
- Min-Cut and Max-Cut (slides) (video1 video2 video3)
- Fingerprinting (slides) (video1 video2 video3)
- Hashing and Sketching (slides) (video1 video2 video3 video4 video5)
- Balls into bins (slides) (video1 video2 video3 video4)
- Concentration of measure (slides) (video1 video2 video3)
- Dimension Reduction (slides) (video1 video2 video3 video4 video5)
- Greedy and Local Search (slides) (video1 video2 video3 video4)
- Jan Vondrák's notes and slides on submodular optimization
- Rounding Dynamic Programs (slides) (video1 video2)
- Rounding Linear Programs (slides) (video1 video2 video3)
- The Primal-Dual Schema (slides) (video1 video2 video3 video4 video5)
- SDP based algorithms (slides) (video1 video2)
- Lovász Local Lemma (slides) (video1 video2 video3)
- Markov Chain Monte Carlo (MCMC) methods (slides) (video1 video2 video3)
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.