算法与数据结构COMP26120

课程内容：

本课程涵盖了计算机科学中有关算法及其正确性和性能的基础内容。这是一门为期两个学期的实践课程，包含一些视频和阅读资源、大量实践经验和实验室支持。学生需要寻找材料来支持课程的学习，从而促进“算法素养”的发展。算法的实现用 C、Java 和 Python 进行说明。

课程目标：

1、通过鼓励主动学习和以最有效的方式传递信息，充分利用现有的学习时间。

2、让学生意识到算法问题在现实生活的计算机科学情境中的重要性。

3、强调实际问题，而不是数学分析。

4、使学生对各种数据结构和算法充满信心，并能将其应用于实际任务中。

教学大纲：

1、算法：是什么以及如何表达（用伪代码和选定的编程语言：Java、C 或 Python）。

2、设计、评估和使用算法的实践经验：来自广泛应用领域的实例；寻找适当的算法和数据结构；发明适当的算法和数据结构。

3、"算法素养"方面的实际经验：知道如何使用有关算法的大量文献，识别在应用中使用的算法并评估其效用。

4、一系列基本数据结构：数组、列表、树（包括有序树、平衡树和堆）以及各种图。基本数据结构在编程语言中的表示。

5、一系列基本算法：搜索和排序算法、树遍历和操作算法、一些基本图算法。还将通过实际例子探讨其他算法领域。

6、算法性能：空间和时间要求，最坏情况、平均情况和最佳情况估计。测量和预测性能的实际经验和技术：计数操作。

7、算法推理：对算法进行非正式推理以确定其正确性的经验。

学习成果：

成功完成本课程后，学生将能够：

1、分析问题，确定并实施最合适的算法解决方案。

2、定义渐近复杂性的标准概念，并利用这些概念推理算法的复杂性。

3、使用伪代码表示算法，并对其正确性进行非正式推理 。

4、回忆基本数据结构的定义和表示方法，以及对其进行操作的复杂性。

5、使用实际应用的例子，解释来自不同数据结构的排序和搜索、图形操作和数论的标准算法问题。

6、从一组教过的算法中找出在特定情况下应采用的算法，解释应如何采用，并将解决方案与可能的替代方案进行比较 。

7、解释分而治之、动态编程、贪婪算法和线性编程等算法技术，讨论何时适合使用这些技术，并应用其解决问题。

8、回顾并解释可操作性和 NP-完备性的概念，特别关注经典的NP-完备性问题，并应用这些概念来证明新问题的 NP-完备性。