“2019级--学期安排 (第二学期)”的版本间的差异

• 2-1: 算法正确性

• 理解并能够区分算法错误与程序错误
• 理解算法正确性的概念及其证明方法

• DH第5章

• 算法正确性证明与一般数学定理证明的异同

• DH 第5章练习 6, 9, 10, 12
• 证明 Euclid (欧几里德) 算法的部分正确性

2019-xx-xx

• 2-2: 算法的效率

• 理解算法的时间复杂性的概念与渐近表示方式

• DH第6章
• TC 2.1节, 2.2节, 3.1节

• 从无限与有限的角度正确理解算法复杂度

• DH 第6章练习 1, 8, 10, 13, 18

2019-xx-xx

• 2-3: 组合与计数

• 掌握在算法分析中常用的计数原理与方法

• CS第1章

• 为什么算法分析中需要计数

• CS 1.1 节 13
• CS 1.2 节 5, 15
• CS 1.5 节 4, 12, 14

2019-xx-xx

• 2-4: 分治法与递归

• 掌握利用分治法设计算法的思路
• 深入理解递归在算法设计中的作用

• TC第4章

• 策略在计算机算法设计中的意义

• TC第4.1节练习5
• TC第4.3节练习3
• TC第4.4节练习2
• TC第4.5节练习3
• TC第4章问题4

2019-xx-xx

• 2-5: 递归及其数学基础

• 进一步理解递归的数学基础
• 更深入地掌握递归算法的分析方法

• CS第4章

• 如何解递归式

• CS第4.1节问题 16, 17
• CS第4.2节问题 8, 11
• CS第4.3节问题 9
• CS第4.4节问题 1, 6
• CS第4.5节问题 8, 9, 10

2019-xx-xx

• 2-6: 算法方法

• 通过具体示例了解算法设计的基本策略

• DH第4章

• 理解复杂算法背后的简单原理

• DH 第4章练习 1, 8, 9, 12, 14

2019-xx-xx

• 2-7: 离散概率基础

• 理解离散概率的基本概念
• 掌握简单离散概率计算的基本方法

• CS第5章: 5.1, 5.2, 5.3, 5.4 节

• 正确理解“期望”的概念，为理解平均情况时间复杂度分析建立基础

• CS第5.1节问题 10, 12
• CS第5.2节问题 4, 10
• CS第5.3节问题 2, 6, 12
• CS第5.4节问题 4, 10, 12 ("Solve Problem 10" 改为 "Solve Problem 11"), 15

2019-xx-xx

• 2-8: 概率分析与随机算法

• 理解概率在算法设计中的作用
• 掌握基于概率的算法分析的基本方法

• TC第5章
• CS第5章: 5.6, 5.7节

• 随机变量在算法分析中的意义

• CS第5.6节问题 4, 8
• CS第5.7节问题 2, 4, 6, 12
• TC第5.2节练习 4, 5
• TC第5.3节练习 2, 3, 4

2019-xx-xx

• 2-9: 排序与选择

• 深入理解快速排序算法的设计思想与分析方法
• 通过排序理解问题复杂度的下界，并探索一些线性排序算法
• 掌握以中位数为代表的统计算法

• TC第7、8、9章

• 如何证明问题复杂度的下界

• TC 第七章:
  • Exercises: 7.1-3, 7.2-4, 7.3-2, 7.4-2
  • Problem: 7.5
• TC 第八章:
  • Exercises: 8.1-4, 8.2-4, 8.3-4, 8.4-2
  • Problem: 8.2
• TC 第九章
  • Exercises: 9.1-1, 9.3-7

2019-xx-xx

• 2-10: 基本数据结构

• 掌握堆栈、队列、链表、指针、根树的概念、实现以及在算法设计中的应用

• TC第10章
• MA第2, 3章

• 数据结构的算法支撑(???)与实现效率的平衡

• MA 2.6 (只要求考察 Push 操作)
• TC第10.1节练习 4、5、6
• TC第10.2节练习 1、2、3、6
• TC第10.3节练习 4、5
• TC第10.4节练习 2、3、4
• TC第10章问题 3

2019-xx-xx

• 2-11: 堆与堆排序

• 理解并掌握堆的结构、实现以及算法应用
• 通过堆的应用与实现理解抽象数据类型的基本概念以及分层抽象的思想

• TC第6章
• SB第2章

• 从数据结构到抽象数据类型的思想发展

• TC第6.1节练习 2、4、7
• TC第6.2节练习 2、5、6
• TC第6.3节练习 3
• TC第6.4节练习 2、4
• TC第6.5节练习 5、7、9

2019-xx-xx

• 2-12: Hashing方法

• 掌握Hashing方法的原理、处理冲突的方法以及分析方法

• TC第11章
• CS第5章第5节

• Hashing方法中的冲突处理

• CS第5.5节问题 8、14
• TC第11.2节练习 3、6
• TC第11.3节练习 3、4
• TC第11.4节练习 2、3
• TC第11章问题 1、2

2019-xx-xx

• 2-13：搜索树

• 掌握利用树结构存储与搜索数据的方法

• TC第12、13章

• 树的平衡与搜索效率的关系

• TC第12.1节练习 2、5
• TC第12.2节练习 5、9
• TC第12.3节练习 5
• TC第13.1节练习 5、7
• TC第13.2节练习 2
• TC第13.3节练习 1、5
• TC第13.4节练习 1、7

2019-xx-xx

• 2-14：B 树

• 掌握 B 树的基本性质及其操作

• TC第18章

• 如何在经典数据结构的基础上，针对应用特征，优化设计，提高效率

• TC 练习 18.1.1,18.1.4
• TC 练习 18.2.3,18.2.4
• TC 练习 18.3.1