本科低年级Computation计划中
Algorithm design and analysis
Recursion and divide and conquer, greedy algorithms, dynamic programming, graph algorithms (breadth- and depth-first search, shortest paths, spanning trees), asymptotic analysis and correctness proofs.
math.comp.algorithm-design
本主题的课程尚未编写。下面的提纲是课程地图的一部分，尚未经过审校。
前置知识
18 项必需的前置知识（一直追溯到底）
你将学会
- Design divide-and-conquer algorithms and analyse them with recurrences, as for mergesort.
- Prove the correctness of greedy algorithms such as Kruskal's algorithm and Dijkstra's algorithm with non-negative weights.
- Design dynamic-programming algorithms for problems such as longest common subsequence.
定义
- Divide and conquer splits a problem into smaller instances, solves them recursively and combines the results.
- Dynamic programming solves a problem by combining solutions of overlapping subproblems, storing them to avoid recomputation.
定理
- Mergesort runs in O(n log n) time.
- Dijkstra's algorithm finds shortest paths from a source vertex when all edge weights are non-negative.
- Kruskal's algorithm finds a minimum spanning tree of a connected weighted graph.
常见误解
- Using Dijkstra's algorithm when some edge weights are negative.
- Assuming a greedy algorithm is correct without a proof.
通向
可选发现
- Graph theory Matching and network-flow algorithms are algorithmic counterparts of theorems such as Hall's and Menger's.
- ← Dots and lines: networks and puzzles
学习路径
延伸阅读
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms
- Jon Kleinberg and Éva Tardos, Algorithm Design (2005)