2024秋季 数据结构与算法

课程信息

• 教师：钮鑫涛 (niuxintao@nju.edu.cn)
• 助教：刘理为 (522023720004@smail.nju.edu.cn)
• 时间：周五 5-7节 1-17周
• 地点：南雍-西311
• QQ群：329361578（申请加入需提供院系、姓名、学号）
• 课程OJ：https://iseoj.nju.edu.cn/
• Piazza的access code：avfgrbklziv

前导知识

• 程序设计基础 (C和JAVA)
• 离散数学

课程简介

"To measure is to know. If you cannot measure it, you cannot improve it."
——  Lord Kelvin

“计算因何而易，又为何而难？”
——  尹一通

"Make It Work, Make It Right, Make It Fast."
——  Kent Beck

算法是计算机科学的核心（没有之一），其良定义了解决问题的计算步骤。算法的学习有两条线索， 一个是其处理的对象，即数据结构，如数字、集合、树、图等，另一个是算法的设计思想，如贪婪、分治、动态规划、线性规划等。这两个方面的主题彼此相对独立，但在解决问题时又互相作用。 通过学习本课程，学生在了解常见数据结构、了解经典算法设计与分析技术的基础上，能够初步学会设计并使用合适的数据结构及算法去有效地求解各类问题。本课程为学生学习其他高级专业课程提供了重要基础。

本课程主要教学内容包含三大部分：数据结构、算法设计与分析技术、以及若干经典算法。

• 数据结构部分：掌握常见数据结构的逻辑结构、实现方式、支持的操作及其复杂性。通过学习数据结构在算法中的应用，理解数据结构对算法设计和性能的影响，进而做到依据问题实际和所设计的算法合理选择数据结构。
• 算法设计与分析技术部分：理解分治、贪心、动态规划等常见算法设计技术，并在此基础上初步学会合理利用这些技术设计算法。能够对算法进行正确性分析和复杂度分析。
• 经典算法部分：学习并掌握若干经典算法，包括其正确性、复杂性、以及所涉及的算法设计思想和分析技术。能够较为熟练地使用这些算法及其变种解决实际问题。

课程安排

理论作业(课外)

由于今年增加了实验作业的量，故理论作业不作要求。这里提供2023年秋季的理论作业，供感兴趣的同学研究：

• Assignment 1
• Assignment 2
• Assignment 3

课本和参考材料

• 课本：算法导论(Introduction to Algorithms), 第三版或第四版, by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clidfford Stein（即著名的CLRS）
• 参考书：
  • 数据结构与算法分析(Data Structures and Algorithm Analysis, 第三版), JAVA语言描述或C++语言描述, by Mark Allen Weiss
  • 算法(Algorithms, 第四版), 也称“红宝书”, by Robert Sedgewick, Kevin Wayne
  • 数据结构(第三版), 邓俊辉, 清华大学出版社
  • Algorithm Design, by Jon Kleinberg and Éva Tardos
  • Algorithms, by Jeff Erickson
• 在线参考课程：
  • CS61B (UC Berkeley)
  • Algorithms Part1 & Part2 (Princeton)

学术诚信

• 作业完成的原则：署你名字的工作必须是你个人的贡献，因此请尽量独立完成所有作业和编程题。
• 在完成作业的过程中，如果确实需要，允许讨论，但要在作业中致谢(acknowledge)所有参与讨论的人。
• 不要在网上搜索答案（也不要用ChatGPT等类似工具）。

致谢（Acknowledgement）

感谢郑朝栋老师提供专业的大纲、课件、以及耐心的指导

感谢Kevin Wayne博士提供的课件和指导
We appreciate Dr. Kevin Wayne for his kindly sharing of his slides for the book Algorithm Design.

感谢魏恒峰老师提供的指导和课件