参考资料
公开课 6.046J Design and Analysis of Algorithms (Spring 2015)
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/
书籍 Introduction to Algorithm (淘宝打印)
算法复杂度 http://bigocheatsheet.com/
基础知识
五种渐进标记 O, o, $\theta$, $\omega$, $\Omega$.
主定理 （用于辅助判断递归方程的时间复杂度）
coding 基础知识
常见 bit operation
基本思想
分治
贪心
递归
宏观原则： 把一个N规模的问题的求解，转换成若干个规模小于N的问题的求解。
不断递归之后，最终求解的问题规模会变成1,求解会非常简单。
八皇后问题
2-SUM
3-SUM
Median of Median
随机算法
引入伪随机数或随机数的概率算法。
Miller-Rabin 素数测试
其他算法导论示例。
常见排序算法
- 快速排序 双指针 pivot
- 冒泡排序
- 选择排序
- 归并排序(Merge sort)
线性时间的排序算法
- 计数排序(Counting Sort)
- 基数排序(Radix Sort)
- 桶排序
高级数据结构
优先队列(堆)
优先队列是一种功能上的概念，而堆则是优先队列的实现。
- 二叉堆 (Binary Heap) SIFT UP， SIFT DOWN …etc
- 二项堆 (Binomial Heap)
- Fibonacci 堆 (Fibonacci Heap)
二叉搜索树(BST)
- 二叉搜索树
- 红黑树
RB-tree 程序仿真 可视化
http://www.cs.armstrong.edu/liang/animation/web/RBTree.html
http://gauss.ececs.uc.edu/RedBlack/redblack.html
红黑树是平衡的二叉搜索树，注意红黑树的5个基本性质。
并查集 (Union-Find)
暂略。
动态规划 (Dynamic Programming)
动态规划的核心是状态转移方程,另一个重要思想是 Memoization .
背包问题(背包九讲)
图算法
图遍历
- 深度优先搜索(DFS) 开始时间结束时间标记，拓扑排序，强联通分量
- 广度优先搜索(BFS)
拓扑排序就是 按 结束时间逆序。
强联通分量则是按 开始时间 结束时间 是否包含在另一个 点的开始时间，结束时间的区间内。
最小生成树 (Minimum Spanning Tree)
- Prim
- Kruskal
最短路径
最短路径算法的核心思想是 Relaxation
- Dijkstra
- Floyd-Warshall 可以有负边，不可有负环，本质是一个DP
- Bellman-Ford 一直可检测负环
树遍历
- 前序遍历
- 中序遍历
- 后序遍历
网络流
最大流最小割定理(Min cut/Max flow)
Ford-Fulkerson (根据字典序DFS选择増广路径)
Edmonds-Karp (每次在残余网络 Residual Network 选择 hops 数 最短的 増广路经 Argumented Path )
2d-match (二分匹配问题 boy meet girl) 可用该方法解决。
数论
可以在现代密码学中再次复习。
中国剩余定理
生日悖论
等
线性规划
略
NP完全问题
NP问题是图灵机的计算模型中能解决的问题的一种，在图灵机上课解的问题，依据其计算复杂度，可以归为如下若干类 P, NP, PSPACE, EXPTIME, EXPSPACE …
https://en.wikipedia.org/wiki/PSPACE
并且，并非所有问题都是图灵机可以计算出结果的，存在着一部分物理体系或者其他问题，它们无法用图灵机的有限步运算步骤进行模拟和重现，即存在图灵不可计算的物理现象。
实际中可能遇到较少。
P : 存在一种算法能在 多项式时间内 告诉你结果的问题。
NP (Nondetermistic Problem)： 如果你随便猜测一个输入，存在一种算法，能在多项式时间内告诉你，这个输入是正确的还是错误的。(但这个算法不能直接解决问题)
NP-hard: 所有比NP问题更困难的问题都是 NP-hard的问题，但一个NP-hard问题不一定是一个NP问题，它可能是一个PSPACE的问题，或者更困难。
NPC (NP Complete)： NP问题中最困难的问题， 处于NP与PSPACE的边界，是一个NP问题。
常见 NPC 问题
- SAT
- 3SAT
- ILP (Integer Linear Programming)
- 3D-match
- ZOE (Zero One Equation)
- Subset Sum
- Vertex Cover
- Independent Set
- Clique
- Set Cover
- Hanmiltonian Path
- TSP
证明一个问题P是NPC
- 证明该问题是NP
- 证明该问题是NP-hard
证明该问题是 NP -> 找到一个 polynomial时间 的 verifier.
证明该问题是 NP-hard -> i将一个 已知的 NPC 问题 reduce 到该问题P。 转化已知问题的输入到P的输入，转化时间也必须是 polynomial的。
数据结构实现
TastyLib https://github.com/stevennL/TastyLib
