2023秋季 数据结构与算法

课程信息

• 教师：钮鑫涛 (niuxintao@nju.edu.cn)
• 助教：
  • 陈宏楠 (MG21330010@smail.nju.edu.cn)
  • 谢润烁 (幕后)
• 时间：周四 5-7节
• 地点：南雍-西311
• QQ群：892855425（申请加入需提供院系、姓名、学号）
• 课程OJ （仅校园网访问）
• 理论作业平台：SELearning
  • 智能软件与工程学院 数据结构与算法
  • 选课码：2023
• Office Hour （什么是Office Hour?）
  • 周三下午 2:00~4:00
  • 周四上午 10:00~12:00
• Piazza
  由于QQ群现在的匿名机制不好用，以及在QQ群问问题容易被忽略，我们这学期尝试用Piazza作为课程的论坛。我们不强制要求必须使用，但是我们非常推荐使用，因为Piazza有如下的好处：
  • 可以匿名提问或反馈
    可以选择仅对同学们匿名（也就是说对老师助教不匿名），或者对所有人（包括老师和助教）都匿名
  • 问题可以用Markdown书写，并且支持LaTeX书写数学公式
  • 问题可以被分门别类，查找起来非常方便
  • 只要po了一个新问题，参与者都会收到一封通知邮件（可以手动关闭）
  • 老师和助教会对其中涉及课程内容进行回答（环境等问题可能不回答），可能在piazza上回答，也可能在课上讲
    加入Piazza的方法：
  • 用Signup Link找到课程
  • 用Access Code: isedsa2023加入课程（此时需要输入邮箱，然后系统会自动帮你注册一个新的账号）

前导知识

• 程序设计基础 (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

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

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

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

课程安排

作业

• Assignment 1, ddl: 2023/9/22 24:00
• Assignment 2, ddl: 2023/10/1 23:59
• Assignment 3, ddl: 2023/10/8 23:59
• Assignment 4 , ddl: 2023/10/22 23:59
• Assignment 5 , ddl: 2023/11/8 23:59
• Assignment 6 , ddl: 2023/11/19 23:59
• Assignment 7, ddl: 2023/12/10 23:59
• Assignment 8, ddl: 2023/12/17 23:59

课本和参考材料

• 课本：算法导论(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)

评分准则

• 期末考试(40%) + 平时作业(30%) + 编程实践(30%)

学术诚信

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

致谢（Acknowledgement）

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

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

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