|
所在平台: Udemy |
课程主页: https://www.udemy.com/course/dsa-and-algorithms-practice-tests/
课程评论：没有评论
**Coursera 数据结构与算法课程总结** 本课程深入探讨了数据结构与算法的核心概念，为学习者提供了扎实的理论基础和实践技能。 **课程内容概览:** * **预备知识:** 课程要求掌握离散数学或同等水平的知识。 * **抽象数据类型:** 涵盖了列表、栈、队列、树、堆等基本抽象数据类型，深入剖析了它们的结构和操作。 * **证明技术:** 学习了基本的数学证明技术，为理解算法的正确性打下基础。 * **排序算法:** 详细讲解了冒泡排序、选择排序、插入排序、计数排序、基数排序、桶排序、归并排序和快速排序等多种排序算法，并分析了它们的效率。 * **搜索算法:** 重点讲解了二分查找。 * **图论:** 深入学习了图的表示方法以及图的遍历（DFS、BFS）及其应用、最短路径算法（Dijkstra、Bellman-Ford、Floyd-Warshall）和最小生成树算法（Prim、Kruskal）。 * **算法分析:** 介绍了渐进符号用于分析算法的执行时间，学习了递归关系的建立与求解，包括递归树法、代入法和主定理。 * **摊还分析:** 学习了摊还成本的概念。 * **分治法:** 详细讲解了分治策略在归并排序、快速排序、二分查找、线性时间选择、Strassen矩阵乘法以及二维点最近对问题中的应用。 * **动态规划:** 深入学习了动态规划在斐波那契数列、最长公共子串、最长公共子序列、0/1背包问题、矩阵链乘法、派对规划和比特路径TSP问题中的应用。 * **贪心算法:** 介绍了贪心算法在活动选择问题和分数背包问题中的应用。 * **最大流问题:** 学习了最大流问题的概念、Ford-Fulkerson方法、Edmonds-Karp算法以及最大流最小割定理。 * **NP完全性:** 介绍了NP完全性理论，以及3SAT、团问题、顶点覆盖和最大独立集等NP完全问题的归约。 **推荐参考书目:** 本课程参考了多本经典算法著作，包括： * *Introduction to Algorithms* (CLRS) by Cormen, Leiserson, Rivest, and Stein * *Fundamentals of Algorithmics* by Brassard and Bratley * *Algorithm Design* by Kleinberg and Tardos * *Problems on Algorithms* by Parberry * *Algorithms* by Dasgupta, Papadimitriou, and Vazirani 本课程为学习者提供了全面的数据结构与算法知识体系，是计算机科学专业人士必备的学习内容。
Discrete Mathematics or equivalent. Abstract data types: lists, stacks, queues, trees, heaps. Basic proof techniques. Bubble, selection, insertion, counting, radix, bucket, merge and quick sorts; binary search. Graphs: representation and algorithms.· Introduction, Asymptotic notation for Execution time analysis. Function hierarchy. Forming and solving recurrences. Recursion tree and substitution method. Master theorem. Amortized cost.· Inversions and sorting. Sorting algorithms: bubble, selection, insertion, counting, radix, and bucket. A lower bound for sorting by comparison. Heap sort.· Divide and conquer: merge sort, quick sort, binary search, linear time rank, Strassen's matrix multiplication, Closest pair of points in 2D.· Dynamic programming: Fibonacci numbers, longest common substring, longest common subsequence, 0-1 Knapsack, matrix-chain multiplication, party planning and bitonic TSP.· Greedy algorithms: Activity selection, Fractional Knapsack.· Graphs: Representation. Graph explorations: DFS, BFS and their applications. Shortest paths: BFS, Dijkstra, Bellman-Ford, Floyd-Warshall. Minimum spanning trees: Prim's and Kruskal's.· Maximum flow problems. Introduction, Ford Fulkerson method, Edmonds Karp algorithm, max flow min cut theorem. Applications.· Introduction to NP-completeness. NP-Complete reductions 3SAT, clique, vertex Cover, maximum independent set.· Introduction to Algorithms, 3rd ed., Cormen, Leiserson, Rivest, and Stein. MIT Press.· Brassard, Gilles, and Paul Bratley. Fundamentals of algorithmics. Vol. 524. Englewood Cliffs: Prentice Hall, 1996.· Jon Kleinberg, Éva Tardos. Algorithm Design.· Problems on algorithms. Ian Parberry.· Dasgupta, Sanjoy, Christos H. Papadimitriou, and Umesh Virkumar Vazirani. Algorithms. McGraw-Hill Higher Education, 2008.
