美国纽约大学计算机算法分析作业和考试的重点是什么？

最佳答案

• 

  课程顾问-小管家 2022-08-24 14:39:58

  立即咨询

  纽约大学计算机算法分析课程主要涵盖了以下主题：递归方程和分治；线性时间算法(基数排序、字典排序、选择)；散列法；平衡树及其扩充；平摊分析(斐波那契堆，Union-Find)；图形算法(DFS，路径问题，MST，利用约简进行算法设计)；动态规划；随机选择；NP完全性。除了上面列出的主题外，课程还旨在提高同学用算法解决问题的技能。为了帮助同学更好地完成作业和考试，我们对课程涵盖的主要内容进行了更加细致的总结。

  1、基本数据结构：数组，链表，归并排序列表

  2、堆排序，分治法：合并排序，递推关系

  3、分治法：寻找中间值，快速排序

  4、分治法：逆序计数，下界排序，基数排序

  5、分治法：快速傅里叶变换，多项式乘法

  6、贪婪算法：区间调度，区间划分

  7、贪婪算法：最小生成树

  8、动态规划：有界整数子集和、矩阵链乘法、最长公共子序列

  9、动态规划：加权区间调度，最短路径，树中的最大独立集

  10、平摊分析：堆栈、二进制计数器、二项式堆

  

  11、平摊分析：斐波那契堆

  12、二分搜索法树，2-3棵树，广度优先搜索

  13、非循环图，拓扑排序，强连通图，强连通分量，深度优先搜索

  14、Dijkstra：最短路径，最大流

  15、最大流：Max-flow = Min-cut, Ford-Fulkerson算法

  16、最大流：霍尔定理的应用

  17、随机算法：概率基础

  18、随机算法：联合界，Ramsey；数字(概率方法的应用)

  19、随机算法：独立性，竞争解决

  20、随机算法：期望，随机快速排序，MAX-CUT

  21、随机化算法：哈希

  22、图灵机，运行时间，P，非确定性，NP

  23、NP-完全性：归约

  24、Cook-Levin定理

  以上即为美国纽约大学计算机算法分析课程所涵盖的关键主题，无论是在作业中，还是在考试中，这些主题都会有所涉及，因此同学一定要掌握全部的内容。

其他答案