2015级--讨论记录 (第三学期)

2016年9月5日

1. 讨论主题：动态规划
   1. 矩阵相乘
   2. 例题讲解：通信系统构建
2. 习题3-1讲解

2016年9月12日

1. 讨论主题：贪心算法
   1. 组成最大整数
   2. 证明哈夫曼编码是前缀码
2. 习题3-2讲解

2016年9月26日

1. 讨论主题：B树
   1. B树的delete算法
   2. 证明B树插入操作的正确性
2. 习题3-3讲解

2016年10月10日

1. 讨论主题：图的基本概念
   1. 图最长路径查找
   2. k-稳定图的构建
2. 习题3-4讲解

2016年10月17日

1. 讨论主题：图的遍历
   1. DFS算法正确性
   2. 带边label的DFS
2. 习题3-6讲解

2016年10月24日

1. 讨论主题：树的基本概念
   1. 如果用相邻矩阵来表示一个图，你如何判断这个图是否是树？
   2. 设计一种用相邻矩阵表示权图的方案，并在这个方案基础上设计一个构造最小生成树的算法。
2. 图与软件工程（许畅）

2016年10月31日

1. 讨论主题：单源最短路
   1. Dijkstra算法与Prim算法的区别与联系
2. C++ STL使用
3. 习题3-7,3-8讲解

2016年11月7日

1. 讨论主题：多源最短路
   1. Floyd-warshall算法构造最短路
   2. 应用：炼钢厂选址

2016年11月14日

1. 讨论主题：图的连通性
   1. 2-连通图等价特性证明
   2. Menger定理（边版本）证明
2. 习题3-9讲解

2016年11月21日

1. 讨论主题：图上的旅行
   1. 证明：竞赛图一定含有有向哈密尔顿通路
   2. 一种合理的循环赛排名方法
2. 习题3-10，3-11讲解

2016年11月28日

1. 讨论主题：最大匹配
   1. 定理8.8证明。在证明中，请你给出以下思考：关于点覆盖/独立的所有相关定理，是否在边覆盖/独立讨论范畴内，均有相应的定理？你能“杜撰”出几条吗？
   2. 二分图最大匹配算法——匈牙利算法

2016年12月05日

1. 讨论主题：网络流
   1. 写出标号算法。用标号法求解流网络
   2. 利用最大流算法，证明hall定理
2. 习题3-13讲解

2016年12月12日

1. 讨论主题：平面图与着色
   1. 非连通图中的欧拉公式
   2. Brooks theorem 证明

2016年12月19日

1. 讨论主题：矩阵计算
   1. Hill CIPher介绍
   2. Brooks theorem 证明
   3. 如何用PLU分解求矩阵的行列式
2. 习题3-15讲解