高级算法 (Fall 2019): Difference between revisions
Jump to navigation
Jump to search
imported>Etone |
imported>Etone |
||
| (48 intermediate revisions by 3 users not shown) | |||
| Line 60: | Line 60: | ||
= Announcement = | = Announcement = | ||
*<font | * (2019/9/6) 第一课的lecture notes和slides已经发布。 | ||
* (2019/10/21)外网数学符号显示已经正常。 | |||
* (2019/11/04)11月6日按原定计划上习题课。教服系统中的“停课”指的是：正常新内容的授课暂停一次，原授课时间段改为上习题课。 | |||
* (2019/11/30)提醒：12月1日星期日下午4点在仙I-108（原上课教室）补课。 | |||
* (2020/1/8)1月11日下午4点半在仙I-207期末考试。考试为<font color=red size=4>闭卷考试</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''': 凤维明，夏瑞，陈劭源 | |||
:*提交作业email: <font color=blue>njuadvalg@163.com</font> | |||
* '''Class meeting''': Wednesday 10am-12pm, 仙I-108. | * '''Class meeting''': Wednesday 10am-12pm, 仙I-108. | ||
* '''Office hour''': Wednesday 4pm-6pm, 计算机系 804. | * '''Office hour''': Wednesday 4pm-6pm, 计算机系 804. | ||
| Line 92: | Line 98: | ||
= Assignments = | = Assignments = | ||
*[[高级算法 (Fall 2019)/Problem Set 1|Problem Set 1]] due on 2019/10/08, before 23:59, submitted to <font color=blue>njuadvalg@163.com</font>. | |||
*[[高级算法 (Fall 2019)/Problem Set 2|Problem Set 2]] due on 2019/11/05, before 23:59, submitted to <font color=blue>njuadvalg@163.com</font>. | |||
*[[高级算法 (Fall 2019)/Problem Set 3|Problem Set 3]] due on 2019/11/26, before 23:59, submitted to <font color=blue>njuadvalg@163.com</font>. | |||
*[[高级算法 (Fall 2019)/Problem Set 4|Problem Set 4]] due on 2020/1/17, before 23:59, submitted to <font color=blue>njuadvalg@163.com</font>. | |||
= Lecture Notes = | = Lecture Notes = | ||
# [[高级算法 (Fall 2019)/Min-Cut and Max-Cut|Min-Cut and Max-Cut]] ([http://tcs.nju.edu.cn/slides/aa2019/Cut.pdf slides]) | # [[高级算法 (Fall 2019)/Min-Cut and Max-Cut|Min-Cut and Max-Cut]] ([http://tcs.nju.edu.cn/slides/aa2019/Cut.pdf slides]) | ||
#: [[高级算法 (Fall 2019)/Probability Basics|Probability basics]] | #: [[高级算法 (Fall 2019)/Probability Basics|Probability basics]] | ||
# [[高级算法 (Fall 2019)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2019/Fingerprinting.pdf slides]) | |||
#: [[高级算法 (Fall 2019)/Finite Field Basics|Finite field basics]] | |||
# [[高级算法 (Fall 2019)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2019/Hashing.pdf slides]) | |||
#: [[高级算法 (Fall 2019)/Basic tail inequalities|Basic tail inequalities]] | |||
# [[高级算法 (Fall 2019)/Balls into bins|Balls into bins]] ([http://tcs.nju.edu.cn/slides/aa2019/BallsIntoBins.pdf slides]) | |||
# [[高级算法 (Fall 2019)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2019/Concentration.pdf slides]) | |||
#: [[高级算法 (Fall 2019)/Conditional expectations|Conditional expectations]] | |||
# [[高级算法 (Fall 2019)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2019/NNS.pdf slides]) | |||
#: [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] | |||
# [[高级算法 (Fall 2019)/Greedy and Local Search|Greedy and Local Search]] ([http://tcs.nju.edu.cn/slides/aa2019/Greedy.pdf slides]) | |||
# Rounding Linear Programs ([http://tcs.nju.edu.cn/slides/aa2019/LP.pdf slides]) | |||
#: [http://tcs.nju.edu.cn/notes/LP.Note.pdf Vazirani book Chap. 14, 16] | |||
# The Primal-Dual Schema ([http://tcs.nju.edu.cn/slides/aa2019/PrimalDual.pdf slides]) | |||
#: [http://tcs.nju.edu.cn/notes/DualityNote.pdf Vazirani book Chap. 12, 15] | |||
#: [http://tcs.nju.edu.cn/notes/FacilityLocation.pdf Vazirani book Chap. 24, 25] | |||
# Semidefinite Programs ([http://tcs.nju.edu.cn/slides/aa2019/SDP.pdf slides]) | |||
#: [http://tcs.nju.edu.cn/notes/SDP.Note.pdf Vazirani book Chap. 26] | |||
#:[http://www.sumofsquares.org/public/index.html SoS SDP course] Lecture [http://www.sumofsquares.org/public/lec01-1_introduction.pdf 1.1], [http://www.sumofsquares.org/public/lec01-2_definitions.pdf 1.2], [http://www.sumofsquares.org/public/lec02-1_maxcut.pdf 2.1] | |||
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2019/LLL.pdf slides]) | |||
# Markov Chain Monte Carlo (MCMC) methods ([http://tcs.nju.edu.cn/slides/aa2019/MCMC.pdf slides]) | |||
= Related Online Courses= | = Related Online Courses= | ||
Latest revision as of 08:36, 8 January 2020
| Instructor | |
|---|---|
| 尹一通 | |
| yinyt@nju.edu.cn chaodong@nju.edu.cn | |
| office | 计算机系 804 |
| Class | |
| Class meetings |
Wednesday, 10am-12pm 仙I-108 |
| 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 2019. Students who take this class should check this page periodically for content updates and new announcements.
Announcement
- (2019/9/6) 第一课的lecture notes和slides已经发布。
- (2019/10/21)外网数学符号显示已经正常。
- (2019/11/04)11月6日按原定计划上习题课。教服系统中的“停课”指的是：正常新内容的授课暂停一次，原授课时间段改为上习题课。
- (2019/11/30)提醒：12月1日星期日下午4点在仙I-108（原上课教室）补课。
- (2020/1/8)1月11日下午4点半在仙I-207期末考试。考试为闭卷考试。
Course info
- Instructor : 尹一通 (homepage)
- email: yinyt@nju.edu.cn
- Teaching Assistant: 凤维明，夏瑞，陈劭源
- 提交作业email: njuadvalg@163.com
- Class meeting: Wednesday 10am-12pm, 仙I-108.
- Office hour: Wednesday 4pm-6pm, 计算机系 804.
Syllabus
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。
先修课程 Prerequisites
- 必须：离散数学，概率论，线性代数。
- 推荐：算法设计与分析。
Course materials
成绩 Grades
- 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。
- 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。
学术诚信 Academic Integrity
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。
作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。
本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 ACM Policy on Plagiarism的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。
学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。
Assignments
- Problem Set 1 due on 2019/10/08, before 23:59, submitted to njuadvalg@163.com.
- Problem Set 2 due on 2019/11/05, before 23:59, submitted to njuadvalg@163.com.
- Problem Set 3 due on 2019/11/26, before 23:59, submitted to njuadvalg@163.com.
- Problem Set 4 due on 2020/1/17, before 23:59, submitted to njuadvalg@163.com.
Lecture Notes
- Min-Cut and Max-Cut (slides)
- Fingerprinting (slides)
- Hashing and Sketching (slides)
- Balls into bins (slides)
- Concentration of measure (slides)
- Dimension Reduction (slides)
- Greedy and Local Search (slides)
- Rounding Linear Programs (slides)
- The Primal-Dual Schema (slides)
- Semidefinite Programs (slides)
- Vazirani book Chap. 26
- 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.