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

来自问题求解
Wu讨论 | 贡献2014年11月17日 (一) 09:23的版本 2014年11月12日

跳转至: 导航搜索

2014年9月5日

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

2014年9月12日

[课件下载]

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

2014年9月17日

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

2014年9月22日

[课件下载]

    • 贪心策略的作业反馈(最优子结构、贪心选择属性、简单的均摊分析练习)
    • Havel-Hakimi定理的证明(度序列的可图化的充分必要条件)

2014年9月28日

[课件下载]

    • 并查集的作业反馈

2014年10月10日

[课件下载]

    • 图的基本概念作业反馈
    • 讨论:Prim算法和Kruskal算法的正确性分析(CZ的证明和TC的证明)

2014年10月15日

[课件下载]

    • 图的计算机表示及遍历(BFS,DFS,拓扑排序,计算强连通分支)

2014年10月22日

[课件下载]

    • 树的性质
    • 讨论:如何找出所有的最短路径树

2014年11月3日

[课件下载]

    • 反馈:单源最短路径算法习题(Bellman-Ford, DAG-Shortest-Path, Dijkstra)

2014年11月12日

[课件下载]

    • 反馈:多源最短路径算法习题(Floyd-Warshall, John's Algorithm)

2014年11月19日

[课件下载]

    • 反馈: