高级算法 (Fall 2024): Difference between revisions
Jump to navigation
Jump to search
Created page with "{{Infobox |name = Infobox |bodystyle = |title = <font size=3>高级算法 <br>Advanced Algorithms</font> |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..." |
Zhangyiyao (talk | contribs) |
||
| (18 intermediate revisions by 4 users not shown) | |||
| Line 87: | Line 87: | ||
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516 | :* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516 | ||
* '''Teaching Assistant''': | * '''Teaching Assistant''': | ||
** | ** 于逸潇：yixiaoyu@smail.nju.edu.cn | ||
** | ** 张弈垚：zhangyiyao@smail.nju.edu.cn | ||
* '''Class meeting''': | * '''Class meeting''': | ||
** Monday (单), 4pm-6pm, 仙Ⅰ-206 | ** Monday (单), 4pm-6pm, 仙Ⅰ-206 | ||
| Line 119: | Line 119: | ||
= Assignments = | = 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] (文件名为'<font color=red >学号_姓名_A1.pdf</font>'). [[高级算法 (Fall 2024)/第一次作业提交名单|第一次作业提交名单]] | |||
*[[高级算法 (Fall 2024)/Problem Set 2|Problem Set 2]] 请在 2024/11/25 上课之前(16:00 UTC+8)提交到 [mailto:njuadvalg24@163.com njuadvalg24@163.com] (文件名为'<font color=red >学号_姓名_A2.pdf</font>'). | |||
= Lecture Notes = | = Lecture Notes = | ||
# [[高级算法 (Fall 2024)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] | # [[高级算法 (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)/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]) | |||
= Related Online Courses= | = Related Online Courses= | ||
Revision as of 07:12, 10 November 2024
| Instructor | |
|---|---|
| 尹一通 | |
| yinyt@nju.edu.cn | |
| office | 计算机系 804 |
| 栗师 | |
| shili@nju.edu.cn | |
| office | 计算机系 605 |
| 刘景铖 | |
| liu@nju.edu.cn | |
| office | 计算机系 516 |
| Class | |
| Class meetings |
Monday (单), 4pm-6pm Thursday, 2pm-4pm 仙Ⅰ-206 |
| Office hours |
Monday, 2pm-4pm, 计算机系 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 2024. Students who take this class should check this page periodically for content updates and new announcements.
Announcement
- TBA
Course info
- Instructor :
- 尹一通：<yinyt@nju.edu.cn>，计算机系 804
- 栗师：<shili@nju.edu.cn>，计算机系 605
- 刘景铖：<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
成绩 Grades
- 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
- 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。
学术诚信 Academic Integrity
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。
作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。
本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 ACM Policy on Plagiarism的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。
学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。
Assignments
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.
- Problem Set 1 请在 2024/10/14 上课之前(16:00 UTC+8)提交到 njuadvalg24@163.com (文件名为'学号_姓名_A1.pdf'). 第一次作业提交名单
- Problem Set 2 请在 2024/11/25 上课之前(16:00 UTC+8)提交到 njuadvalg24@163.com (文件名为'学号_姓名_A2.pdf').
Lecture Notes
- Min Cut, Max Cut, and Spectral Cut (slides)
- Fingerprinting (slides)
- Hashing and Sketching (slides)
- Concentration of measure (slides)
- Dimension Reduction (slides)
- Greedy Algorithms (slides, slides-handout)
- Linear Programming (slides, slides-handout)
- Linear Programming Rounding (slides, slides-handout)
- Linear Programming Duality (slides, slides-handout)
- Primal-Dual Algorithms (slides, slides-handout)
- Semi-Definite Programming and Max-Cut (slides, slides-handout)
- Multiplicative Weight Update Method (slides, slides-handout)
- Extension Complexity (slides, slides-handout)
Related Online Courses
- Advanced Algorithms by Anupam Gupta at CMU.
- 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 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.