高级算法 (Spring 2026)

From TCS Wiki
Jump to navigation Jump to search
高级算法
Advanced Algorithms
任课教师
刘明谋
电子邮件 lmm@nju.edu.cn
办公室 南雍-西229
课程时间地点
教室 周一，9am-12pm
苏教B207
答疑时间 周五，2pm-5pm
南雍-西229
教材
Motwani and Raghavan.
Randomized Algorithms.
Cambridge Univ Press, 1995.
Vazirani.
Approximation Algorithms.
Springer-Verlag, 2001.
v · d · e

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

通知

  • (2026/3/2) 第一堂课
  • (2026/3/23) 请大家严格遵守《关于本科生规范使用生成式人工智能工具的指导意见（试行）》！
  • (2026/4/6) 是清明节假期，停课一次。
  • (2026/5/3) Feistel cipher / Feistel permutation 的正确定义是 [math]\displaystyle{ (x_1,x_2) \mapsto (f(x_2)\oplus x_1,x_2) }[/math]。第二次作业原本的题面写错了。
  • (2026/5/4) 是五一假期，停课一次。
  • (2026/5/11) 第一节课（9am-10am）期中考试
  • (2026/6/1) 老师出差，停课一次
  • (2026/6/13) 18：30-21:30补上一次停的课

课程信息

  • 任课教师:
  • 助教:
  • 课程时间地点:
    • 周一，9am-12pm，苏教B207
  • 答疑时间: 周五, 2pm-5pm, 南雍-西229
  • QQ群: 1083465754

教学大纲

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

课程内容分为五大部分：

  • 基于哈希的大数据算法
  • 哈希表与面向大数据的现代计算场景
  • 测度的集中与处理高维数据
  • 最大流与线性规划
  • 其他重要话题

先修课程

  • 必须：离散数学，概率论，线性代数。
  • 推荐：算法设计与分析。

课程教材

本门课较为前沿，大部分课程内容还没有进入任何教材。以下教材和参考书仅作为参考。

更多的内容也可以参考其他学者的同类课程。

成绩

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

学术诚信 Academic Integrity

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

作业完成的原则：署你名字的工作必须是你个人的贡献，任何不是由你完成的部分都必须明确标注，特别是由AI生成的部分，否则就涉嫌抄袭。在完成作业的过程中，允许讨论，前提是讨论的所有参与者均处于同等完成度。但关键想法的执行、以及作业文本的写作必须独立完成，并在作业中致谢（acknowledge）所有参与讨论的人。符合规则的讨论与致谢将不会影响得分。不允许其他任何形式的合作——尤其是与已经完成作业的同学“讨论”。

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

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

课后作业

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

请大家严格遵守《关于本科生规范使用生成式人工智能工具的指导意见（试行）》！

（如果你提交过作业之后想重新提交，可以通过更改“版本”字段换一个文件名提交）

  • 作业1 请在 2026/04/06 上课前（9am UTC+8）上传到 南大云盘 (文件名为'学号_姓名_版本.pdf').
  • 作业2 请在 2026/05/11 上课前（9am UTC+8）上传到 南大云盘 (文件名为'学号_姓名_版本.pdf')。
  • 大作业。 暂定7月30日截止，将本作业的在线访问链接填写到表格中供老师和助教检查和验收。

课件及相关阅读资料

  1. Fingerprinting
    • Polynomial Identity Testing
    • Communication Complexity (Equality)
    • Application: Bipartite Perfect Matching, Checking Matrix Multiplication
    • Karp-Rabin Algorithm (string-searching), Lipton’s Algorithm (checking identity of multisets)
  2. Sketching
    • Morris' Algorithm
      • mean trick, median trick
    • Counting Distinct Elements: min sketch, Flajolet-Martin algorithm, bottom-[math]\displaystyle{ k }[/math] algorithm, HyperLogLog
    • Heavy Hitter & Point Query: count-min sketch
    • 2nd Frequency Moments Estimator: count sketch
      • [math]\displaystyle{ \ell_2 }[/math] point query with count sketch
    • Approximate Membership: Bloom filter
  3. Hashing
    • Load Balancing: maximum load, power of two choices
    • Perfect Hashing: birthday paradox, FKS perfect hashing
    • Modern Hash Table: Cuckoo hashing, succinct dictionaries
    • Hashing in Practice: Chernoff Bound with limited independence, tabulation hashing
  4. Dimensionality reduction
    • Johnson-Lindenstrauss Transformation:
      • Intuition: In high-dimensional spaces, a uniformly random vector is almost certainly nearly orthogonal to any fixed vector
      • Constructions: independent Gaussian entries, projection onto uniform random subspace, i.i.d. -1/+1 entries
      • Modern applications: TurboQuant versus RaBitQ versus Quantized JL
      • Fast Johnson-Lindenstrauss Transformation
    • Approximate Nearest Neighbor Search: by dimensionality reduction, by Locality Sensitive Hashing (LSH)
    • Oblivious Subspace Embedding (OSE): net argument
      • Application: linear regression by sketch-and-solve via OSE, linear regression by fast iteration with OSE
      • Sparse Oblivious Subspace Embedding: count sketch
  5. Network flow & Linear programming
    • Maximum flow: max-flow min-cut theorem, Ford-Fulkerson algorithm, scaling algorithm, Edmonds–Karp algorithm, Dinitz's algorithm
      • Application & Extension: multi-source multi-sink, maximum bipartite matching, counting disjoint paths, global min cut, [math]\displaystyle{ P }[/math]-completeness, minimum-cost flow problem
    • Linear programming: Simplex, Interior Point Method, Elipsoid Method, [math]\displaystyle{ P }[/math]-completeness
      • Duality and primal-dual methods
      • Integer programming: randomized rounding for approximate algorithms

Related Online Courses

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