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

2014年9月5日

1. • 讨论最长公共子串问题(LCS）（用于衡量两个序列的相似性）
   • 讨论最优二分搜索树问题（给定关键字的概率，建立最优二分搜索树，使得搜索的期望代价最小）

2014年9月12日

[课件下载]

1. • 讨论动态规划习题（子问题图中节点数和边数的计算、是否具有最优子结构的问题、求最长单调递增序列的问题）
   • 讨论构建最优前缀码（Huffman Codes)的算法的原理（如何证明问题具有最优子结构）

2014年9月17日

1. • 并查集在路径压缩和按秩合并两种方法下操作的均摊分析证明。
   • 试举使用并查集解题的例子。 （1）堆栈合并