File:计算方法3-2026.pdf

2026-03-18T05:45:56Z

Liuexp:

计算方法3-2026

计算方法 Numerical method (Spring 2026)

2026-03-11T02:04:37Z

Liuexp: /* Lecture Notes */

File:计算方法2-2026.pdf

2026-03-11T02:04:19Z

Liuexp:

计算方法2-2026

Main Page

2026-03-04T08:45:27Z

Liuexp: /* Home Pages for Courses and Seminars */

This is a course/seminar wiki run by the [http://tcs.nju.edu.cn theory group] in the Department of Computer Science and Technology at Nanjing University.

== Home Pages for Courses and Seminars==
;Current semester
* [[高级算法 (Spring 2026)|高级算法 Advanced Algorithms (Spring 2026, Suzhou)]]

* [[组合数学 (Spring 2026)|组合数学 Combinatorics (Spring 2026)]]

* [[计算复杂性 (Spring 2026)|计算复杂性 Computational Complexity (Spring 2026)]]

* [[计算方法 Numerical method (Spring 2026)|计算方法 Numerical method (Spring 2026)]]

* [[概率论与数理统计 (Spring 2026)|概率论与数理统计 Probability Theory (Spring 2026)]]

;Past courses

* Advanced Algorithms: [[高级算法 (Fall 2025)|Fall 2025]], [[高级算法 (Spring 2025)|Spring 2025(Suzhou)]], [[高级算法 (Fall 2024)|Fall 2024]], [[高级算法 (Fall 2023)|Fall 2023]], [[高级算法 (Fall 2022)|Fall 2022]], [[高级算法 (Fall 2021)|Fall 2021]], [[高级算法 (Fall 2020)|Fall 2020]], [[高级算法 (Fall 2019)|Fall 2019]], [[高级算法 (Fall 2018)|Fall 2018]], [[高级算法 (Fall 2017)|Fall 2017]], [[随机算法 \ 高级算法 (Fall 2016)|Fall 2016]].

*Algorithm Design and Analysis: [https://tcs.nju.edu.cn/shili/courses/2024spring-algo/ Spring 2024]

* Combinatorics: [[组合数学 (Spring 2025)|Spring 2025]], [[组合数学 (Spring 2024)|Spring 2024]], [[组合数学 (Spring 2023)|Spring 2023]], [[组合数学 (Fall 2019)|Fall 2019]], [[组合数学 (Fall 2017)|Fall 2017]], [[组合数学 (Fall 2016)|Fall 2016]], [[组合数学 (Fall 2015)|Fall 2015]], [[组合数学 (Spring 2014)|Spring 2014]], [[组合数学 (Spring 2013)|Spring 2013]], [[组合数学 (Fall 2011)|Fall 2011]], [[Combinatorics (Fall 2010)|Fall 2010]].

* Computational Complexity: [[计算复杂性 (Spring 2025)|Spring 2025]], [[计算复杂性 (Spring 2024)|Spring 2024]], [[计算复杂性 (Spring 2023)|Spring 2023]], [[计算复杂性 (Fall 2019)|Fall 2019]], [[计算复杂性 (Fall 2018)|Fall 2018]].

* Foundations of Data Science: [[数据科学基础 (Fall 2025)|Fall 2025]], [[数据科学基础 (Fall 2024)|Fall 2024]]

* Numerical Method: [[计算方法 Numerical method (Spring 2025)|Spring 2025]], [[计算方法 Numerical method (Spring 2024)|Spring 2024]], [[计算方法 Numerical method (Spring 2023)|Spring 2023]], [https://liuexp.github.io/numerical.html Spring 2022].

* Probability Theory: [[概率论与数理统计 (Spring 2025)|Spring 2025]], [[概率论与数理统计 (Spring 2024)|Spring 2024]], [[概率论与数理统计 (Spring 2023)|Spring 2023]].

* Quantum Computation: [[量子计算 (Spring 2022)|Spring 2022]], [[量子计算 (Spring 2021)|Spring 2021]], [[量子计算 (Fall 2019)|Fall 2019]].

* Randomized Algorithms: [[随机算法 (Fall 2015)|Fall 2015]], [[随机算法 (Spring 2014)|Spring 2014]], [[随机算法 (Spring 2013)|Spring 2013]], [[随机算法 (Fall 2011)|Fall 2011]], [[Randomized Algorithms (Spring 2010)|Spring 2010]].

;Past seminars, workshops and summer schools
*计算理论之美暑期学校: [[计算理论之美 (Summer 2025)|2025]], [[计算理论之美 (Summer 2024)|2024]], [[计算理论之美 (Summer 2023)|2023]], [[计算理论之美 (Summer 2021)|2021]]
*[[Theory Seminar|理论计算机科学讨论班]]
*[[Study Group|理论计算机科学学习小组]]
*[[TCSPhD2020| 理论计算机科学优秀博士生论坛2020]]
*[[Quantum|量子算法与物理实现研讨会]]
*Theory Day: [[Theory@Suzhou 2025 | 2025 (Suzhou)]], [[Theory@Nanjing 2019|2019]], [[Theory@Nanjing 2018|2018]], [[Theory@Nanjing 2017|2017]]
*[[\Delta Seminar on Logic, Philosophy, and Computer Science|Δ Seminar on Logic, Philosophy, and Computer Science]]
*[[近似算法讨论班 (Fall 2011)|近似算法 Approximation Algorithms, Fall 2011.]]

; 其它链接
* [[General Circulation(Fall 2025)|大气环流 General Circulation of the Atmosphere, Fall 2025]]
* [[General Circulation(Fall 2024)|大气环流 General Circulation of the Atmosphere, Fall 2024]]

* [[概率论 (Summer 2014)| 概率与计算 (上海交大 Summer 2014)]]

计算方法 Numerical method (Spring 2026)

2026-03-04T05:50:45Z

Liuexp: /* Lecture Notes */

File:计算方法1-2026.pdf

2026-03-04T05:50:22Z

Liuexp:

课程简介，函数求根

计算方法 Numerical method (Spring 2026)

2026-03-02T06:32:07Z

Liuexp: /* Course info */

MediaWiki:Sidebar

2026-02-28T09:03:56Z

Liuexp:

MediaWiki:Sidebar

2026-02-28T09:03:45Z

Liuexp:

2025-10-20T05:39:25Z

Liuexp: /* Lecture Notes */

{{Infobox
|name = Infobox
|bodystyle =
|title = 高级算法
 Advanced Algorithms
|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 =
|label5 =
|data5 = '''栗师'''
|header6 =
|label6 = Email
|data6 = shili@nju.edu.cn
|header7 =
|label7= office
|data7= 计算机系 605
|header8 =
|label8 =
|data8 = '''刘景铖'''
|header9 =
|label9 = Email
|data9 = liu@nju.edu.cn
|header10 =
|label10= office
|data10= 计算机系 516
|header11 = Class
|label11 =
|data11 =
|header12 =
|label12 = Class meetings
|data12 = Monday, 2pm-4pm Thursday (双), 2pm-4pm 仙Ⅰ-320
|header13 =
|label13 = Place
|data13 =
|header14 =
|label14 = Office hours
|data14 = TBD, 计算机系 804 
|header15 = Textbooks
|label15 =
|data15 =
|header16 =
|label16 =
|data16 = [[File:MR-randomized-algorithms.png|border|100px]]
|header17 =
|label17 =
|data17 = Motwani and Raghavan. ''Randomized Algorithms''. Cambridge Univ Press, 1995.
|header18 =
|label18 =
|data18 = [[File:Approximation_Algorithms.jpg|border|100px]]
|header19 =
|label19 =
|data19 = Vazirani. ''Approximation Algorithms''. Springer-Verlag, 2001.
|belowstyle = background:#ddf;
|below =
}}

This is the webpage for the ''Advanced Algorithms'' class of fall 2025. Students who take this class should check this page periodically for content updates and new announcements.

= Announcement =
* '''(2025/9/10)''' 本周四（9月11日）课程时间地点不变，为第五、六节在仙I-320。从第四周（9月15日）开始，采用新的上课时间：每周一的第五、六节，以及双周四的第五、六节，地点仍在仙I-320。

= Course info =
* '''Instructor '''（授课时间顺序）:
:* [http://tcs.nju.edu.cn/yinyt/ 尹一通]：[mailto:yinyt@nju.edu.cn <yinyt@nju.edu.cn>]，计算机系 804
:* [https://liuexp.github.io 刘景铖]：[mailto:liu@nju.edu.cn <liu@nju.edu.cn>]，计算机系 516
:*[https://tcs.nju.edu.cn/shili/ 栗师]：[mailto:shili@nju.edu.cn <shili@nju.edu.cn>]，计算机系 605
* '''Teaching Assistant''':
** 侯哲：houzhe@smail.nju.edu.cn
** 张弈垚：zhangyiyao@smail.nju.edu.cn
* '''Class meeting''':
** Monday, 2pm-4pm, 仙Ⅰ-320
** Thursday (双), 2pm-4pm, 仙Ⅰ-320
* '''Office hour''': Wednesday 2pm-3pm, 计算机系 804
* '''QQ群''': 524141453（加群请注明专业学号姓名）

= Syllabus =
随着计算机算法理论的不断发展，现代计算机算法的设计与分析大量地使用非初等的数学工具以及非传统的算法思想。“高级算法”这门课程就是面向计算机算法的这一发展趋势而设立的。课程将针对传统算法课程未系统涉及、却在计算机科学各领域的科研和实践中扮演重要角色的高等算法设计思想和算法分析工具进行系统讲授。

=== 先修课程 Prerequisites ===
* 必须：离散数学，概率论，线性代数。
* 推荐：算法设计与分析。

=== Course materials ===
* [[高级算法 (Fall 2025) / Course materials|教材和参考书]]

=== 成绩 Grades ===
* 课程成绩：本课程将会有若干次作业和一次期末考试。最终成绩将由平时作业成绩和期末考试成绩综合得出。
* 迟交：如果有特殊的理由，无法按时完成作业，请提前联系授课老师，给出正当理由。否则迟交的作业将不被接受。

=== 学术诚信 Academic Integrity ===
学术诚信是所有从事学术活动的学生和学者最基本的职业道德底线，本课程将不遗余力的维护学术诚信规范，违反这一底线的行为将不会被容忍。

作业完成的原则：署你名字的工作必须是你个人的贡献。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

本课程将对剽窃行为采取零容忍的态度。在完成作业过程中，对他人工作（出版物、互联网资料、其他人的作业等）直接的文本抄袭和对关键思想、关键元素的抄袭，按照 [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism]的解释，都将视为剽窃。剽窃者成绩将被取消。如果发现互相抄袭行为， 抄袭和被抄袭双方的成绩都将被取消。因此请主动防止自己的作业被他人抄袭。

学术诚信影响学生个人的品行，也关乎整个教育系统的正常运转。为了一点分数而做出学术不端的行为，不仅使自己沦为一个欺骗者，也使他人的诚实努力失去意义。让我们一起努力维护一个诚信的环境。

= Assignments =
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.

*[[高级算法 (Fall 2025)/Problem Set 1|Problem Set 1]] 请在 2025/10/30 上课之前(14:00 UTC+8) 提交到 [mailto:njuadvalg25@163.com njuadvalg25@163.com] (文件名为'学号_姓名_A1.pdf').

= Lecture Notes =
# [[高级算法 (Fall 2025)/Min Cut, Max Cut, and Spectral Cut|Min Cut, Max Cut, and Spectral Cut]] ([http://tcs.nju.edu.cn/slides/aa2025/Cut.pdf slides])
#* [[高级算法 (Fall 2025)/Probability Basics|Probability basics]]
# [[高级算法 (Fall 2025)/Fingerprinting| Fingerprinting]] ([http://tcs.nju.edu.cn/slides/aa2025/Fingerprinting.pdf slides])
#* [[高级算法 (Fall 2025)/Finite Field Basics|Finite field basics]]
# [[高级算法 (Fall 2025)/Hashing and Sketching|Hashing and Sketching]] ([http://tcs.nju.edu.cn/slides/aa2025/Hashing.pdf slides])
#* [[高级算法 (Fall 2025)/Limited independence|Limited independence]]
#* [[高级算法 (Fall 2025)/Basic deviation inequalities|Basic deviation inequalities]]
# [[高级算法 (Fall 2025)/Concentration of measure|Concentration of measure]] ([http://tcs.nju.edu.cn/slides/aa2025/Concentration.pdf slides])
#* [[高级算法 (Fall 2025)/Conditional expectations|Conditional expectations]]
# [[高级算法 (Fall 2025)/Dimension Reduction|Dimension Reduction]] ([http://tcs.nju.edu.cn/slides/aa2025/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]
# ''Lovász'' Local Lemma ([http://tcs.nju.edu.cn/slides/aa2025/LLL.pdf slides])
#* [https://theory.stanford.edu/~jvondrak/MATH233A-2018/Math233-lec02.pdf Professor Jan Vondrák's Lecture Notes on LLL]
#* [https://www.cc.gatech.edu/~vigoda/6550/Notes/Lec16.pdf Professor Eric Vigoda's Lecture Notes on Algorithmic LLL]
# Spectral graph theory and Cheeger's inequality ([[Media:Spectral-graph-theory-AA-2024.pdf|slides]])

= Related Online Courses=
* [https://www.cs.cmu.edu/~15850/ Advanced Algorithms] by Anupam Gupta at CMU.
* [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/fall18/cos521/ Advanced Algorithm Design] by Pravesh Kothari and Christopher Musco 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.
* [https://www.cs.cmu.edu/~odonnell/papers/cs-theory-toolkit-lecture-notes.pdf CS Theory Toolkit] by Ryan O'Donnell at CMU.
* [https://cs.uwaterloo.ca/~lapchi/cs860/index.html Eigenvalues and Polynomials] by Lap Chi Lau at University of Waterloo.
* The [https://www.cs.cornell.edu/jeh/book.pdf "Foundations of Data Science" book] by Avrim Blum, John Hopcroft, and Ravindran Kannan.

高级算法 (Fall 2025)

2025-10-13T09:13:36Z

Liuexp:

计算方法 Numerical method (Spring 2025)

2025-06-04T09:14:07Z

Liuexp: /* Lecture Notes */

{{Infobox
|name = Infobox
|bodystyle =
|title = 计算方法
 Numerical method
|titlestyle =

|image =
|imagestyle =
|caption =
|captionstyle =
|headerstyle = background:#ccf;
|labelstyle = background:#ddf;
|datastyle =

|header1 =Instructor
|label1 =
|data1 =
|header2 =
|label2 =
|data2 = 刘景铖
|header3 =
|label3 = Email
|data3 = liu [at] nju [dot] edu [dot] cn
|header4 =
|label4= Office
|data4= 计算机系 516
|header5 = Class
|label5 =
|data5 =
|header6 =
|label6 = Class meetings
|data6 = 周三 14:00-16:00 仙 Ⅱ- 405
|header7 =
|label7 = Place
|data7 =
|header8 =
|label8 =
|data8 =
|header9 = Textbooks
|label9 =
|data9 =
|header10 =
|label10 =
|data10 =
|header11 =
|label11 =
|data11 = Timothy Sauer 数值分析（Numerical Analysis）（原书第2版）. 机械工业出版社.
|header12 = Teaching Assistants
|data13= 侯哲，于逸潇
|label14= Email
|data14= {houzhe, yixiaoyu} [at] smail [dot] nju [dot] edu [dot] cn
|label15= Office
|data15=计算机系 410
|belowstyle = background:#ddf;
|below =
}}
=Announcement=
*Welcome
=Course info=
*'''Instructor''': 刘景铖 ( liu [at] nju [dot] edu [dot] cn )

*'''Teaching assistants''': 侯哲，于逸潇
*'''TA email''': {houzhe, yixiaoyu} [at] smail [dot] nju [dot] edu [dot] cn
*'''Homework email''': nm_nju_2025@163.com
*'''Class meeting''':周三 14:00-16:00，仙 Ⅱ- 405
*'''Office hour''': 周二 16:00-18:00?, 计算机系516 (subject to change)
*'''QQ群''': 1019649082.(加入时需报姓名、专业、学号)

=Textbooks and Readings=
*数值分析（Numerical Analysis）（原书第2版）. Timothy Sauer. 机械工业出版社.
*[https://people.csail.mit.edu/jsolomon/share/book/numerical_book.pdf Numerical Algorithms: Methods for Computer Vision, Machine Learning, and Graphics. Justin Solomon. CRC Press]
*[https://www.cs.yale.edu/homes/vishnoi/Lxb-Web.pdf Lx=b, Laplacian Solver and Their Algorithmic Applications. Nisheeth K. Vishnoi.]
如果在获取教材方面有困难可以联系助教。(仅限英文版)

= Collaboration on Homework =
You are welcome to work on homework problems in study groups of no more than 3 people; however, you must always write up the solutions on your own, listing all collaborators at the top. Similarly, you may use books or online resources to help solve homework problems, but you must always credit all such sources in your writeup and you must never copy material verbatim.

We believe that most students can distinguish between helping other students and cheating. You may discuss approaches but your solution must be written by you and you only. You should acknowledge everyone whom you have worked with or who has given you any significant ideas about the homework.

Further, it is your responsibility to ensure that your solutions will not be visible to other students. If you use Github or another source control system to store your solutions electronically, you must ensure your account is configured so your solutions are not publicly visible. Many popular version control systems provide free repositories to students.

As a final note, we’d like to point out that collaboration on homework, while permitted, can be detrimental to your learning if misused. In particular, avoid collaborations where you do not contribute enough to your own satisfaction. Such a collaboration not only cheats you out of an opportunity to learn through homework, but can also affect your confidence. If you feel that you are not contributing enough to your group, then try to spend time thinking about the problems alone before working with your group. If you end up solving the problem all by yourself, that’s great! And if not, you’ll still be better prepared to contribute to your group.

See also [http://www.acm.org/publications/policies/plagiarism_policy ACM Policy on Plagiarism].

=Assignments=
Late policy: In general, we will accomodate late submission requests ONLY IF you made such requests ahead of time.
# [[Media:Computational Method 2025 Assignments 1.pdf| Homework1]] 请在2025年03月04日23点59分之前提交到 nm_nju_2025@163.com (文件名为'学号_姓名_A1.pdf') [[计算方法 Numerical method (Spring 2025)/Homework1 提交名单|Homework1 提交名单]]
# [[Media:Computational Method 2025 Assignments 2.pdf| Homework2]] 请在2025年03月18日23点59分之前提交到 nm_nju_2025@163.com (文件名为'学号_姓名_A2.pdf') [[计算方法 Numerical method (Spring 2025)/Homework2 提交名单|Homework2 提交名单]]
# [[Media:Computational Method 2025 Assignments 3.pdf| Homework3]] 请在2025年04月01日23点59分之前提交到 nm_nju_2025@163.com (文件名为'学号_姓名_A3.pdf') [[计算方法 Numerical method (Spring 2025)/Homework3 提交名单|Homework3 提交名单]]
# [[Media:Computational Method 2025 Assignments 4.pdf| Homework4]] 请在2025年04月22日23点59分之前提交到 nm_nju_2025@163.com (文件名为'学号_姓名_A4.pdf') [[计算方法 Numerical method (Spring 2025)/Homework4 提交名单|Homework4 提交名单]]
# [[Media:Computational Method 2025 Assignments 5.pdf| Homework5]] 请在2025年05月06日23点59分之前提交到 nm_nju_2025@163.com (文件名为'学号_姓名_A5.pdf') [[计算方法Numerical method (Spring 2025)/Homework5_提交名单|Homework5 提交名单]]
# [[Media:Computational Method 2025 Assignments 6 v3.pdf| Homework6]] 请在2025年05月20日23点59分之前提交到 nm_nju_2025@163.com (文件名为'学号_姓名_A6.pdf') [[计算方法Numerical method (Spring 2025)/Homework6_提交名单|Homework6 提交名单]]
# [[Media:Computational Method 2025 Assignments 7 v2.pdf| Homework7]] 请在2025年06月03日23点59分之前提交到 nm_nju_2025@163.com (文件名为'学号_姓名_A7.pdf') [[计算方法Numerical method (Spring 2025)/Homework7_提交名单|Homework7 提交名单]]
# [[Media:Computational Method 2025 Assignments 8.pdf| Homework8]] 作为练习题，不计分，不需要提交

=Lecture Notes=
如果有下载课件的问题请及时联系助教。

# [[Media:计算方法1-2025.pdf|课程简介，函数求根]]
# [[Media:计算方法2-2025.pdf|牛顿法，插值，秘密分享，自纠错码]]
# [[Media:计算方法3-2025.pdf|Chebyshev插值与Chebyshev多项式，范数]]
# [[Media:计算方法4-2025.pdf|最小二乘法，Gram-Schmidt正交化与QR分解]]
# [[Media:计算方法5-2025.pdf|FFT，高斯消元与LU分解]]
# [[Media:计算方法6-2025.pdf|算子范数，条件数和迭代法]]
# [[Media:计算方法 7-特征值与幂迭代.pdf|特征值与幂迭代]]
# [[Media:计算方法 8-特征值的其它迭代方法与SVD.pdf|特征值的其它迭代方法与SVD]]
#* Further reading: [https://web.stanford.edu/class/cs168/l/l9.pdf lecture note by Tim Roughgarden and Greg Valiant on matrix completions]
# [[Media:计算方法9.pdf|迭代法解线性方程组：梯度下降方法与共轭梯度]]
# [[Media:计算方法10.pdf|幂迭代的特例：随机游走与马尔可夫链]]
# [[Media:计算方法11.pdf|谱图论]]
# [[Media:计算方法12.pdf|电阻电路网络，碰撞时间和遍历时间]]
# [[Media:计算方法13.pdf|线性规划入门]]
# [[Media:计算方法14.pdf|LP顶点，对偶性和零和游戏]]
# [[Media:计算方法15.pdf|LP强对偶性，课程回顾]]

File:计算方法15.pdf

2025-06-04T09:13:07Z

Liuexp:

计算方法15

File:Stat02-2025.pdf

2025-05-28T05:50:53Z

Liuexp: Liuexp uploaded a new version of File:Stat02-2025.pdf

Stat02-2025