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

2020-02-20

• 1-13: 布尔代数

• 理解布尔代数基本概念
• 理解布尔代数与格的联系与区别
• 布尔代数表达式的化简

• SM第15章

• 布尔代数

• 1-13-boolean-algebra

• [布尔代数与算法正确性]

• 2-1: 算法的正确性

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

• DH第5章

• 循环不变式

• 2-1-correctness

• [热身专题]

2020-03-05

2-2：算法的效率

• 2019-2-2-efficiency
• 2019-2-2-efficiency-handout

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

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

• 如何做算法复杂度分析

• 2-2-efficiency

2020-03-12

2-3：组合与计数

• 2019-2-3-counting
• 2019-2-3-counting-handout

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

• CS第1章

• 组合计数技巧与常见形式

• 2-3-counting

2019-03-19

• 2-4: 分治法与递归 (OLD)

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

• TC 第2.3节
• TC 第4章

• 算法设计中的分治思想

• 2-4-recurrence

2019-03-26

• 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章

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

• 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