2017级--学期安排 (第二学期)

来自问题求解
跳转至: 导航搜索

基本要求

  • 理解数据抽象,理解并能够应用常用的数据结构
  • 掌握重要算法设计策略以及算法分析的基本方法
  • 理解并能够应用支持上述内容的离散数学工具与方法
  • 程序设计能力

考核方法

所有形式的考核,均不准抄袭。

  • 作业 (10%)
  • OJ (10%)
  • Open topics (10%)
    • 成绩: A (10), B (8), C (6) 三档
    • 每人至少做一次
    • 做多次报告,取最高分
    • 不做计 0 分
  • 期末: (70%)
    • 机试 (20%)
    • 笔试 (50%)

2017-2-final-exam.pdf ( 2017-2-final-exam-src.zip)

指定教材

推荐课外阅读材料

(可参照习题课扩展材料部分所给出的阅读建议)

  • Kenneth H. Rosen: Discrete Mathematics and Its Applications, 7th Edition. McGraw-Hill, 2011

更多阅读材料将随课堂进度添加。

学习周历

日期 论题 学习目的 阅读材料 引导要点 书面作业 Open Topics
2018-03-07
  • 理解并能够区分算法错误与程序错误
  • 理解算法正确性的概念及其证明方法
  • DH第5章
  • 算法正确性证明与一般数学定理证明的异同
  • DH 第5章练习 6, 9, 10, 12
  • 证明 Euclid (欧几里德) 算法的部分正确性
  • Insertion Sort
  1. 刘恩萌
  2. 姜勇刚
  3. 张天昀
  • Cyclic Hanoi
  1. 李凯旭
  2. 郑奘巍
  3. 董杨静

2018-03-14

  • 理解算法的时间复杂性的概念与渐近表示方式
  • DH第6章
  • TC 2.1节, 2.2节, 3.1节
  • 从无限与有限的角度正确理解算法复杂度
  • DH 第6章练习 1, 8, 10, 13, 18
  • Algorithmic Gap
  1. 王腾
  2. 李顶为
  3. 肖江
  • Asymptotic Notations
  1. 马常风
  2. 黄秉焜
  3. 吕云哲

2018-03-21

  • 掌握在算法分析中常用的计数原理与方法
  • CS第1章
  • 为什么算法分析中需要计数
  • CS 1.1 节 13
  • CS 1.2 节 5, 15
  • CS 1.5 节 4, 12, 14
  • The twelvefold way (1)
  1. 高天朗
  2. 谢逸
  3. 何伟
  • The twelvefold way (2)
  1. 张廷昊
  2. 匡舒磊
  3. 殷天润

2018-03-28

  • 掌握利用分治法设计算法的思路
  • 深入理解递归在算法设计中的作用
  • TC第4章
  • 策略在计算机算法设计中的意义
  • TC第4.1节练习5
  • TC第4.3节练习3
  • TC第4.4节练习2
  • TC第4.5节练习3
  • TC第4章问题4
  • 证明 The Master Theorem
  1. 兰兆炜
  2. 邱凯 (改次)
  3. 吕云哲
  • 介绍 Akra–Bazzi Method
  1. 李博文
  2. 何润雨 (改次)
  3. 刘寒

2018-04-04

  • 进一步理解递归的数学基础
  • 更深入地掌握递归算法的分析方法
  • 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
  • Josephus Problem
  1. 裴一凡
  2. 戴若石
  3. 毕秋宇
  • Generating Function
  1. 张灵毓
  2. 何润雨
  3. 丁保荣

2018-04-09

  • 通过具体示例了解算法设计的基本策略
  • DH第4章
  • 理解复杂算法背后的简单原理
  • DH 第4章练习 1, 8, 9, 12, 14
  • Alpha-Beta 剪枝
  1. 张博乔
  2. 郑奘巍
  3. 张天昀
  • SAT 求解算法
  1. 袁彦
  2. 李顶为
  3. 杨欣然

2018-04-18

  • 理解离散概率的基本概念
  • 掌握简单离散概率计算的基本方法
  • 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

2018-04-25

  • 理解概率在算法设计中的作用
  • 掌握基于概率的算法分析的基本方法
  • 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
  • Monty Hall Problem
  1. 李博文
  2. 毛一鸣
  3. 毕秋宇
  • TC Problem 5.2: Searching an unsorted array
  1. 许致明
  2. 何润雨
  3. 殷兆恒

2018-05-02

  • 深入理解快速排序算法的设计思想与分析方法
  • 通过排序理解问题复杂度的下界,并探索一些线性排序算法
  • 掌握以中位数为代表的统计算法
  • 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
  • TC Problem 7.4
  1. 徐臣
  2. 陈昱名
  3. 谢乃容
  • Random-Selection 算法的期望时间复杂度
  1. 鄢振宇
  2. 张扬播
  3. 韩博

2018-05-09

  • 掌握堆栈、队列、链表、指针、根树的概念、实现以及在算法设计中的应用
  • 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
  • A stack, two queues
  1. 杜星亮 (改次)
  2. 陶绍诚
  3. 丁保荣 (改次)
  • 正确性
  1. 姜勇刚

2018-05-14

  • 理解并掌握堆的结构、实现以及算法应用
  • 通过堆的应用与实现理解抽象数据类型的基本概念以及分层抽象的思想
  • 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
  • Heapsort vs. Quicksort 性能
  1. 张灵毓
  2. 凌晨宇
  3. 廖玺然
  • Binary tree => Heap => Priority queue
  1. 马常风
  2. 邱凯
  3. 肖江

2018-05-21

  • 掌握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
  • Universal Hashing
  1. 周涛
  • Hash 故事会
  1. 陈巍

2018-06-04

  • 掌握利用树结构存储与搜索数据的方法
  • 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
  • Splay tree
    • 杜星亮 (一班)
    • 孙旭东 (一班)
  • 中序遍历的正确性
    • 银加 (二班)
    • 鄢振宇 (一班)

2018-06-11

  • 掌握 B 树的基本性质及其操作
  • TC第18章
  • 如何在经典数据结构的基础上,针对应用特征,优化设计,提高效率
  • TC 练习 18.1.1,18.1.4
  • TC 练习 18.2.3,18.2.4
  • TC 练习 18.3.1
  • B 树插入算法对高度的影响
    • 殷兆恒 (三班)
    • 黄秉焜 (二班)
  • 介绍 B* 树
    • 邱凯 (二班)
    • 谢乃容 (三班)