高级算法 (Fall 2021) and File:7b8c359ae1af6bda4ed78a7721bd4338.png: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
imported>Etone
 
(== Summary == Importing file)
Tag: Server-side upload
 
Line 1: Line 1:
{{Infobox
== Summary ==
|name        = Infobox
Importing file
|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
|data4= 计算机系 804
|header5 = Class
|label5  =
|data5  =
|header6 =
|label6  = Class meetings
|data6  = Tuesday, 2pm-5pm <br> 腾讯会议：598 944 8767
|header7 =
|label7  = Place
|data7  =
|header8 =
|label8  = Office hours
|data8  = Wednesday, 4pm-6pm <br>804
|header9 = Textbooks
|label9  =
|data9  =
|header10 =
|label10  =
|data10  = [[File:MR-randomized-algorithms.png|border|100px]]
|header11 =
|label11  =
|data11  = Motwani and Raghavan. <br>''Randomized Algorithms''.<br> Cambridge Univ Press, 1995.
|header12 =
|label12  =
|data12  = [[File:Approximation_Algorithms.jpg|border|100px]]
|header13 =
|label13  =
|data13  =  Vazirani. <br>''Approximation Algorithms''. <br> Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}
 
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 上课之前提交到 [mailto:njuadvalg21@163.com njuadvalg21@163.com] (文件名为'<font color=red >学号_姓名_A1.pdf</font>').
 
= Course info =
* '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage])
:*'''email''': yinyt@nju.edu.cn
* '''Teaching Assistant''':
** 陈小羽([mailto:chenxiaoyu233@smail.nju.edu.cn chenxiaoyu233@smail.nju.edu.cn])
** 吴旭东 ([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 =
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。
 
=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。
 
=== Course materials ===
* [[高级算法 (Fall 2020) / Course materials|<font size=3>教材和参考书</font>]]
 
=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。
 
=== <font color=red> 学术诚信 Academic Integrity </font>===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。
 
作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。
 
本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为，<font color=red> 抄袭和被抄袭双方的成绩都将被取消</font>。因此请主动防止自己的作业被他人抄袭。
 
学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。
 
= Assignments =
*[[高级算法 (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)/第一次作业提交名单|第一次作业提交名单]].
* '''Reading assignment''': Mitzenmacher and Upfal, ''Probability and Computing, second edition'', '''Chapter 17''' "Balanced Allocations and Cuckoo Hashing", 请在一周内读完
* [[高级算法 (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)/第二次作业提交名单|第二次作业提交名单]], [https://chenxiaoyu233.github.io/algadv21-assiment-slides/assiment-1-2.pdf 前两次作业习题课slides]
* [[高级算法 (Fall 2021)/Problem Set 3|Problem Set 3]] 请在 2021/12/7 上课之前提交到 [mailto:njuadvalg21@163.com njuadvalg21@163.com] (文件名为'<font color=red >学号_姓名_A3.pdf</font>').
 
= Lecture Notes =
# [[高级算法 (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 2021)/Probability Basics|Probability basics]]
#  [[高级算法 (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 2021)/Finite Field Basics|Finite field basics]]
#  [[高级算法 (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 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 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 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.csail.mit.edu/gregory/annbook/introduction.pdf An introduction of LSH]
#  [[高级算法 (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])
#: [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
# 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])
#:  [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]
 
= Related Online Courses=
* [http://people.csail.mit.edu/moitra/854.html Advanced Algorithms] by Ankur Moitra at MIT.
* [http://courses.csail.mit.edu/6.854/current/ Advanced Algorithms] by David Karger and Aleksander Mądry at MIT.
* [http://web.stanford.edu/class/cs168/index.html The Modern Algorithmic Toolbox] by Tim Roughgarden and Gregory Valiant at Stanford.
* [https://www.cs.princeton.edu/courses/archive/fall15/cos521/ Advanced Algorithm Design] by Sanjeev Arora at Princeton.
* [http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15859-f11/www/ Linear and Semidefinite Programming (Advanced Algorithms)] by Anupam Gupta and Ryan O'Donnell at CMU.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.

Latest revision as of 12:42, 30 August 2022

Summary

Importing file

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=高级算法_(Fall_2021)&oldid=9781"