卡尔顿大学 计算机科学

COMP3804 算法设计和分析

卡尔顿大学计算机科学专业的COMP3804算法设计和分析课程详细介绍了分而治之、动态编程、线性编程、贪婪算法、图算法、NP完备性等方面的内容。

具体来说，COMP3804算法设计和分析课程涵盖了以下关键主题：

1、引言：什么是算法、Big-O 符号、递推关系。

2、分而治之：两个n位整数相乘、合并排序、矩阵乘法、中值。

3、图形：表示、遍历- DFS和BFS、最短路径。

4、贪婪算法：最小生成树、哈夫曼编码。

5、动态编程：编辑距离、最长公共序列。

6、NP-完备性：搜索问题、多项式时间还原、库克斯定理的思想。

7、近似算法、穷举搜索和搜索启发法。