量子计算 (Fall 2019) and 高级算法 (Fall 2019): Difference between pages
(Difference between pages)
imported>Qinminglong |
imported>Etone |
||
| Line 2: | Line 2: | ||
|name = Infobox | |name = Infobox | ||
|bodystyle = | |bodystyle = | ||
|title = <font size=3> | |title = <font size=3>高级算法 | ||
<br> | <br>Advanced Algorithms</font> | ||
|titlestyle = | |titlestyle = | ||
| Line 19: | Line 19: | ||
|header2 = | |header2 = | ||
|label2 = | |label2 = | ||
|data2 = | |data2 = 尹一通 | ||
|header3 = | |header3 = | ||
|label3 = Email | |label3 = Email | ||
|data3 = | |data3 = yinyt@nju.edu.cn chaodong@nju.edu.cn | ||
|header4 = | |header4 = | ||
|label4= | |label4= office | ||
|data4= 计算机系 | |data4= 计算机系 804 | ||
|header5 = Class | |header5 = Class | ||
|label5 = | |label5 = | ||
| Line 31: | Line 31: | ||
|header6 = | |header6 = | ||
|label6 = Class meetings | |label6 = Class meetings | ||
|data6 = | |data6 = Wednesday, 10am-12pm <br> 仙I-108 | ||
|header7 = | |header7 = | ||
|label7 = Place | |label7 = Place | ||
| Line 37: | Line 37: | ||
|header8 = | |header8 = | ||
|label8 = Office hours | |label8 = Office hours | ||
|data8 = | |data8 = Wednesday, 4pm-6pm <br>804 | ||
|header9 = Textbooks | |header9 = Textbooks | ||
|label9 = | |label9 = | ||
| Line 43: | Line 43: | ||
|header10 = | |header10 = | ||
|label10 = | |label10 = | ||
|data10 = | |data10 = [[File:MR-randomized-algorithms.png|border|100px]] | ||
|header11 = | |header11 = | ||
|label11 = | |label11 = | ||
|data11 = | |data11 = Motwani and Raghavan. <br>''Randomized Algorithms''.<br> Cambridge Univ Press, 1995. | ||
|header12 = | |header12 = | ||
| | |label12 = | ||
| | |data12 = [[File:Approximation_Algorithms.jpg|border|100px]] | ||
| | |header13 = | ||
| | |label13 = | ||
| | |data13 = Vazirani. <br>''Approximation Algorithms''. <br> Springer-Verlag, 2001. | ||
|belowstyle = background:#ddf; | |belowstyle = background:#ddf; | ||
|below = | |below = | ||
}} | }} | ||
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 = | = Announcement = | ||
*<font size=5 color=red>由于学校网络中心没有开放外网对Mathoid端口的访问权，因此目前讲义只能在校内访问时正常显示数学公式。</font> | |||
* (2019/9/6) 第一课的lecture notes和slides已经发布。 | |||
= Course info = | = Course info = | ||
* '''Instructor ''': | * '''Instructor ''': 尹一通 ([http://tcs.nju.edu.cn/yinyt/ homepage]) | ||
* ''' | :*'''email''': yinyt@nju.edu.cn | ||
* '''Class meeting''': | * '''Class meeting''': Wednesday 10am-12pm, 仙I-108. | ||
* '''Office hour''': | * '''Office hour''': Wednesday 4pm-6pm, 计算机系 804. | ||
= Course materials = | = Syllabus = | ||
* [ | 随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。 | ||
* [ | |||
=== 先修课程 Prerequisites === | |||
* 必须：离散数学，概率论，线性代数。 | |||
* 推荐：算法设计与分析。 | |||
=== Course materials === | |||
* [[高级算法 (Fall 2019) / Course materials|<font size=3>教材和参考书</font>]] | |||
=== 成绩 Grades === | |||
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩 (≥ 60%) 和期末考试成绩 (≤ 40%) 综合得出。 | |||
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。 | |||
=== <font color=red> 学术诚信 Academic Integrity </font>=== | |||
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。 | |||
作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。 | |||
本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为，<font color=red> 抄袭和被抄袭双方的成绩都将被取消</font>。因此请主动防止自己的作业被他人抄袭。 | |||
学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。 | |||
= Assignments = | = Assignments = | ||
* | *[[高级算法 (Fall 2019)/Problem Set 1|Problem Set 1]] due on 2019/10/09 00:00am, submitted to njuadvalg@163.com. | ||
= 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)/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]] | |||
* | = 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. | |||
Revision as of 04:54, 24 September 2019
| 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
- 由于学校网络中心没有开放外网对Mathoid端口的访问权，因此目前讲义只能在校内访问时正常显示数学公式。
- (2019/9/6) 第一课的lecture notes和slides已经发布。
Course info
- Instructor : 尹一通 (homepage)
- email: yinyt@nju.edu.cn
- 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/09 00:00am, submitted to njuadvalg@163.com.
Lecture Notes
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.