新南威尔士大学COMP3121期末考试复习攻略

新南威尔士大学的COMP3121课程不仅仅是让同学浏览一些要记忆和实现的著名算法。相反，同学要学习的是如何使用各种设计技术(贪婪、动态规划、分治等)来“从零开始”设计解决新问题的新算法，并研究这些技术的应用，例如在图算法和字符串匹配算法中的应用。因此，算法设计才是COMP3121考试的重点。为了便于同学做好考试准备，我们总结了这份复习攻略。详情如下。

一、COMP3121考试复习重点

1、算法分析：证明算法的正确性；稳定匹配问题。

2、分治方法：渐近行为，递归，求和，估计；称量硬币；主定理及其应用。

3、贪婪方法：Activity Selection问题；离散(0-1)背包问题；文件压缩(霍夫曼代码)；有向无环图和拓扑排序；Dijkstra算法；最小生成树。

4、动态编程方法：最长上升子序列；流水线调度；矩阵乘法链；最长公共子序列；编辑距离；Bellman - Ford算法；Floyd - Warshall算法。

5、网络流算法：网络流；Ford - Fulkerson算法及更多。

6、字符串匹配算法：" Naïve "字符串匹配算法；Rabin - Karp哈希算法；使用有限自动机进行字符串匹配。

7、线性规划：制定线性程序；线性规划和整数线性规划。

8、棘手问题和近似算法：算法可行性；多项式时间问题，NP问题，棘手问题；NP完全问题和NP困难问题；使用贪婪方法和DP近似解。

二、COMP3121考试评估重点

1、使用各种设计技术(贪婪、动态规划、分治等)设计新算法来解决新问题；

2、评估算法的效率并证明其正确性；

3、展示改进的问题解决技能。

新南威尔士大学COMP3121期末考试将使用INSPERA在线进行，时长是三个小时，涵盖了八个选择题和四个算法设计问题。希望我们的重点总结对同学的考前复习有帮助。