"SSCC = ❶statement ❷solution ❸Correctness ❹Complexity"
- Tree
- Tree definition:
- connected simple graph without cycles.(Tree is also a Graph)
- The following are equivalent:
- 1. G is a tree.
- 2. Every two nodes of G are joined by a unique path.
- 3. G is connected and V = E + 1.
- 4. G is acyclic and V = E + 1.
- 5. G is acyclic and if any two non-adjacent nodes are joined by an edge, the resulting graph has exactly one cycle.
- Full tree VS. Complete tree
- full binary tree(两个孩子好): (sometimes proper binary tree or 2-tree) is a tree in which every node other than the leaves has two children
"如图 0
/ \
1 2
/ \
3 4"
- complete binary tree(向左看齐): is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
"如图 0
/ \
1 2
/ \ /
3 4 5
"
- BFS
- 空间需求: Queue, 需要存储当前层的Nodes
- 终止条件：Queue为空，直至没有Nodes存入，所有Node都remove掉
- 执行过程：对Queue中当前size()的Node进行操作：读值、抛出queue
- DFS
- pre-order: current ---> left child --> right child
- in-order: left child ---> current ---> right child
- When applying on 'Binaray Search Tree', the output is in order, due to its inherent order and the search tree structure
- post-order: left child ---> right child ---> current
- Graph
- Why graph ?
- real-life problems usually have more than one (linkedlist) or two (tree) relations between entities, So here naturally comes in Graph, which could represent multiple relations among one another.
- Terms
- Complete Graph: a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge
- Strongly Connected Graph: A directed graph is strongly connected if there is a path between all pairs of vertices.
- Strongly Connected Components: A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph.
- Common Problems & solutions
- 1. Shortest path
- 1.1 BFS | O( E+V ): unweighted + all edges equal to "1" + tolerate "Cycle "
- Problem:
- statement: all edge weights are 1,2,3, how to solve the shortest path problem in linear time.
- solution:
- 1. transform all edges into segment of '1'
"O(n) <= O(3n)"
- 2. run BFS find the shortest path
- BFS : find the levels from starting point to ending point
"1. little trick : think the graph as "balls and strings": hang the starting point, others just hang onto it
http://www.stoimen.com/blog/wp-content/uploads/2012/10/2.-The-Graph-as-Balls-and-Strings.png
2. general idea:
http://www.stoimen.com/blog/2012/10/15/computer-algorithms-dijkstra-shortest-path-in-a-graph/
http://www.stoimen.com/blog/2012/10/08/computer-algorithms-shortest-path-in-a-graph/"
- pseudo code
"0. maintain level as global variable
1. create a Queue to store current level of nodes
2. add starting node into Queue
3. while Queue is not empty
for all nodes of current level, which can be gotten by help of Queue.size( )
remove first node from Queue
if this node is target node
return;
else
add its adjacent nodes into Queue
endif
endfor
level++;
endwhile
return level;
"
- time complexity: O(V+E) or O(V^2)
"1 - 邻接表，每个顶点均需搜索一次，故时间复杂度为O(|V|)，在搜索任一顶点的邻接点时，每条边至少访 问一次，故时间复杂度为O(|E|)，算法总的时间复杂度为O(|V|+|E|)。
2 - 邻接矩阵，查找每个顶点的邻接点所需的时间为O(|V|)，故算法总的时间复杂度为O(|V|^2)。"
- space complexity:
- space for Graph: 邻接表／邻接矩阵
- space for algo: Queue
- 1.2 Topological sort + sequential traversal DAG | O( E+V ): weighted + positive + Acyclic
"不需要像Dijkstra一样维护minHeap，每次选dist最小的点出来。而是直接按照topological order 对每个点进行relaxation即可完成"
- 为什么比Dijkstra要快？？？
- In topologically sorted DAG, there are no back edges from latter nodes to their former nodes; ie. When we do relaxation in topological order, after we find the shortest path from "s" to the former nodes, no need to consider them when we do the follower nodes.
- 上句解释：这也是为什么可以按topo顺序计算dist：因为前边的计算完了就定了，不会收到后边的影响，因为根据Topo Sort定义，后边的点不会在指向前边的点，也就是在计算完前边某点后，其后的点与它之间不会有valid路径。
- 因为这是借助了DAG的特性，在计算某点之前，已经将其所有可能的detour路径计算完毕。所以在做到该点时，大胆放心的进行relaxation即可，不必担心还会有别的detour会比这次relaxation计算出来的dist要近！！
- pseudo code( no need for PQ, just List )
"1. Topologically sort G into L; // O(E+V)
2. Set the distance to the source to 0;
3. Set the distances to all other vertices to infinity;
4. For each vertex u in L
5. -walk through all neighbors v of u;
6. - dist(u) = Min { dist(v) + w(u, v) }
7. - prev(v) = u
end forward "
- 1.3 Dijkstra | O( E*logV ): weighted + only positive + tolerate Cycle
- Dijkstra Algorithm ( only for positive edges, cannot handle negative edges....)
"single-source shortest path "
- 0. 外层循环 ---> extract node with minDist ; 内层循环 ---> update dist value of its adjacent node
- 1. 每步必定会确定出某一点的最短路径
- 2. 每步确定出一个点的最短路径后，也会更新与之毗邻点的距离
- 3. 一步步更新，实际是得到了，由最短路径点构成的union的所有相连点的距离的更新
- 4. 这些值存放在heap中，供下一次选出minDis Node ( dist = ∞ 的不用考虑，说明没有直接连接 ）
- 5. 为什么“负值”不能符合？ -- 因为Dijkstra每一步是从所有与union区域直接相连的点中选取dist最小的Node k ( s -> k )，这样做的前提是：没有别的detour路径( s -> m -> k) 会比这条direct路径更优，因为这个点的 dist(s-k) < dist(s-m), 显然dist(s-k) < dist(s-m)+dist(m-k)更成立！这里的前提假设是dist(m-k)>0!!!!!!!!
- https://www.youtube.com/watch?v=gdmfOwyQlcI
- 形象类比：string-ball （ string是edge，ball是vertex ）
- 将source node提起来，其他node挂在string上
"https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-16-dijkstra/"
- 也是BFS的一个变种，按离sourceNode由近到远的顺序一层一层遍历
- pseudo code: 每次iteration必找到某个点的最短路径。同时，更新其周围点的dist
"G: Graph w: weight s: source vertex dist: distance from this vertex to source vertex
prev: Array for found shortest vertices, recording previous vertex to source vertex
PQ: Priority Queue for unfound vertices, recording distance to source vertex
Dijkstra( G, w, s )
Initializition:
dist[s] = 0; dist[others] = ∞;
L = null;
PQ = distance to source vertex for ALL vertices
while PQ is not empty{
u <-- Extract_min_vertex( PQ ); // delete min_vertices from PQ
for each vertex v is adjacent to u {
Relax( u, v, w ){
if ( dist[v] > dist[u] + w(u,v) )
dist[v] = dist[u] + w(u, v)
update PQ using dist[v]
prev(v) = u
}
}
}
"
- Time complexity: T= V * T(ExtractMin) + E * T(Relaxation)
"http://www.cnblogs.com/gaochundong/p/dijkstra_algorithm.html"
- 1. Array存储dist :
- T= V *V+ E
- T(extractMin) = O(V) loop once to find min; T(decreaseKey) = O(1), find: O(1) then update
- T= V * T(ExtractMin) + E * T(Relaxation)
- 2. Binary heap( PQ)存储dist :
- T= V * O(lgV)+ E * O(lgV)
- T(extractMin) = O(lgV) ; T(decreaseKey) = O(lgV)
- V-1 <= E <= V*(V-1)/2 (connected) => T= O(E*lgV)
- depending on sparse or dense
- sparse: E = O(V) => O(V*lgV)
- dense: E = O(V^2) => O(V^2 * lgV)
- 3. Binomial heap( PQ)存储dist:
- T= V * O(lgV)+ E * O(lgV)
- T(extractMin) = O(lgV) ; T(decreaseKey) = O(lgV)
- V-1 <= E <= V*(V-1)/2 (connected) => T= O(E*lgV)
- depending on sparse or dense
- sparse: E = O(V) => O(V*lgV)
- dense: E = O(V^2) => O(V^2 * lgV)
- 4. Fibonacci heap( PQ)存储dist:
- T= V * O(lgV)+ E
- T(extractMin) = O(lgV) ; T(decreaseKey) = O(1)
- V-1 <= E <= V*(V-1)/2 (connected)
- depending on sparse or dense
- sparse: E = O(V) => T=V * O(lgV) = O(V*lgV)
- dense: E = O(V^2) => T= E = O(V^2)
- space complexity :
- space for Graph:邻接表／邻接矩阵
- space for algo: PriorityQueue( heap) / Array
- 1.4 Bellman-Ford | O( E*V ): weighted + negative/positive + tolerate Cycle
- 0. Floyd vs Bellman
- 1. Bellman-Ford ：
- 不对Edge进行编号，依次计算s->v 之间的最短路由任意i条Edge构成，(i+1)条构成，...
- D(i,v)： 表示 s至v点最短路之间由i条边构成，一条不多一条不少
- 2. Floyd-Warshall：
- 对Vertex进行编号，依次计算s->v之间的最短路由前i号vertex构成，(i+1)号构成，...
- D(i,j,k)：表示i至j点最短路之间由前k个点构成，可以不用kth点，点的数目也可以少于k
- 1. DP思想：
- s点到某u点构成的最短路径，之间最多由V-1条边构成
- DP子问题：D(i,u) - 从s点到u点之间至多可以有i条边的最短路径值
"不是至多由前i条边构成，而是任意i条边！"
- DP递推式：
- 1. 当最短路径中间有1条边时，求s点至所有点最短路
- 当最短路径中间有2条边时，求s点至所有点最短路
- 。。。
- 当最短路径中间有(V-1)条边时，求s点至所有点最短路
- 2. 递归思路：中间由i 条边的最短路有两种情况构成
- 1. 第i条边的确用上了: D(i,u)= min{ D(i-1,t), e(t,u) }, t=adj(u)
- 2. 第i条边加上也没用: D(i,u)= D(i-1,u)
- 2. 流程：
- 找最短：对每条E所连接的两个点中的inbound点，进行relaxation， 共进行 V-1次。若不存在负值环路，一定能收敛得到所有值
- 找负环：之后再对每一个E进行relaxation时，如果有 dist[u] > dist[v] + w(u,v)，表明： 存在achievable negative circle.
- 3. pseudo code:
"BellmanFord( G, w, s )
Initializition:
dist[s] = 0; dist[others] = ∞;
L = null;
PQ = distance to source vertex for ALL vertices
Relaxation:
for i = 1 to |V| - 1 // only count times for iteration
for each v in V
for each u is adjacent to v
Relax( u, v, w ){
if ( dist[v] > dist[u] + w(u,v) )
dist[v] = dist[u] + w(u, v)
prev(v) = u
endif
}
endfor
endfor
endfor
Check negative circle :
for each edge(u, v) belongs to E
if ( dist[v] > dist[u] + w(u,v) )
report : negative circle exist!
"
- 4. Time complexity: O(VE)
- 5. space complexity :
- space for Graph:邻接表／邻接矩阵
- space for algo: PriorityQueue( heap) / Array
- 1.5 Floyd-Warshall | 多到多最短路 | O( V^3 ): weighted + negative + cycle
- 0. Floyd vs Bellman
- 1. Bellman-Ford ：
- 不对Edge进行编号，依次计算s->v 之间的最短路由任意i条Edge构成，(i+1)条构成，...
- D(i,v)： 表示 s至v点最短路之间由i条边构成，一条不多一条不少
- 2. Floyd-Warshall：
- 对Vertex进行编号，依次计算s->v之间的最短路有前i号vertex参与，前(i+1)号参与，...
- D(i,j,k)：表示i至j点最短路之间由前k个点参与，但可以不用kth点，点的数目也可以少于k
- 1. DP思想
- 对所有点进行编号：1,2,3... V；i->j点的最短路径，之间的点一定不会逃出前V号点的范围，ie. 中间点一定由前V号点中的某些构成
- DP子问题：D(i,j,k) - 从i点到j点的最短路，中间点从前k号点中选所构成的最短路
"不是任意k个点，而是顶多从前i个点中选择！"
- DP递推式：
- 1. 当最短路径中间点从前1号点选择时，求i->j最短路
- 当最短路径中间点从前2号点选择时，更新i->j最短路
- 。。。
- 当最短路径中间点从前V号点选择时，更新i->j最短路
- 2. 递归思路：中间点从前i号点中选择所构成的最短路有2种情况
- 1. 第i号点的确用上了:
" ---- D(i, j, k)= D(i, k, k-1) + D(k, j, k-1) "
- 2. 第i号点加上也没用:
" ----- D(i, j, k)= D(i, j, k-1) "
- 2. 流程：
- 找最短：依次更新中间点在前1,2,3,..号点中选择时，任意i、j之间的最短路
- 找负环：在对前k号点计算完所有i->j之间的最短路，检查D(i,i,k)值
- 1. 如果D(i,i,k)=0，目前不存在负环
- 2. 如果D(i,i,k)=负值，存在负环（i到它自身的距离应该是0，如果有负环存在，会优先走负环，使该值越来越小）
- 3. pseudo code - find min value:
" Initializition:
D[i, j, 0] = e(i, j) for all i, j;
D[i, i, k] = 0 for all k;
P[i ,j] = 0; // used to extract path
Relaxation:
for k = 1 to |V| // 从前k号点中选择中间点
// 1-----shortest path from i to j with nodes selected from former k node ---
for i = 1 to |V|
for j = 1 to |V|
temp = D(i, k, k-1) + D(k, j, k-1)
if( temp < D(i, j, k-1) )
D[i, j, k] = temp
P[i, j] = k; // used for extracting path
else
D[i, j, k] = D(i, j, k-1)
endfor
endfor
// 2------Check Negative Cycle -------
if( D(i, i, k) != 0 )
report " Negative Cycle Exist! "
endif
endfor
"
- 4. pseudo code - recover shortest path:
"maintain another table P[i, j], recording "i->j, what's the last kth node was used? "
ie. choosing intermediate nodes from front kth node
find_path( i, j ){
if( p[i, j] == 0 )
output (i, j);
else
find_path( i, p[i, j] );
find_path( p[i, j], j );
}"
- 5. Time complexity: O(V^3)
- 6. space complexity :
- space for Graph:邻接表／邻接矩阵
- space for algo: PriorityQueue( heap) / Array
- 1.6 时间复杂度--比较--（多到多最短路）
- Floyd-Warshall: O( V^3 ) --
- Bellman-Ford: O( E * V^2 ) --
- Dijkstra: O( V( E +V lgV) ) -- 应用FibonacciHeap复杂度
"不适用于negative edges"
- 2. Minimum Spanning Tree - O( E*logV ) | negative + weighted + cycle
- Definition
- Spanning Tree: a tree making every vertex in a Graph(V,E) have connection to any other vertex with no cycle. Surely, the edge of ST is (V-1)
- MST: the overall cost is the minimum among all spanning trees
- Hamiltonian Path is a special case of Minimum Spanning Tree
- Solution
- 1. Prim's Algorithm
- Pseudo code:
- very similar to Dijkstra Algorithm. The only place need to modify is where Relaxation phase in Dijkstra: Dist[u] = Dist[v] + E(u,v). Now it should be modified into Dist[u] = E(u,v)
- Time complexity:
- O( E*logV)
- 2. Kruskal's Algorithm
- Time complexity:
- O( E*logE): 用并查集的find() / union() 总有一个是O(1) 与O(lgn),这里的O(lgn)是针对每条边，检查它的两个端点是否已经连通
- 1. 首先edge按大小排序：O(E*lgE)
- 2. 对每条边循环检查：
- 它的两个端点是否已经属于同一个union ： O(E)
- yes，discard this edge
- no， choose it. And union them : O(lgE)
- 3. Reserve Kruskal's Algorithm
- 2. Graph traversal | O( E+V )
"即便是“unconnected graph”，只要“遍历”，就必须将所有node遍历完！
BFS 与 DFS 都可以达到“全部遍历”的目的"
- BFS / DFS ---> directed / undirected
- 对于directed/ undirected 非联通图，BFS／DFS 先从一点开始遍历，直到没有点可以遍历。 然后，如果依然存在没有被遍历的点，则从该点进行BFS/DFS遍历，直到所有点遍历完，最终形成森林(forest)
- 3. Topological Sort (DAG) | O( E+V )
- 用途：
- 1. course schedule( w/ prerequisite) | task schedule( w/ dependence) . 所以显然不可以有cycle
- 2. can find Hamiltonian Path in a DAG visiting all the nodes in a graph
- 1. Simple method pseudo code
"时间复杂度： O(n^2)
empty queue q
while( q.size() < |V| )
find vertex u whose in-degree is '0'
push u into q
delete all vertices adjacent to u // O(n) to go through all the adjacency list
end while
print out q"
- 2. Better method I ( improved version of 1st method )
"version 1: 课本P103下方： O(m+n)
version 2:
- Make an empty queue L and an empty queue S;
- Put all the vertices with no predecessors in L;
- While L has items in it;
Pop an item from L to n, and push it to S;
For each vertex m adjacent to n;
Remove edge(n, m);
If m has no predecessors – push it to L;
end for
end while
print out S
"
- version 1 basic idea: we need two extra variable
- 1. 需要一个array，存储每个节点的“出度”，并一步一步更新
- 2. 需要一个set，存储该图当前“出度”为0 的点的集合供选择
- 3. Better method II ( DFS )pseudo code(相当于用DFS进行DAG的遍历: 遇到死胡同，回头继续找)
"时间复杂度： O(m+n)"
- maintain a stack, recording the reversed order the courses
- Maintain a visited array, recording reversed order nodes
- DFS find the node without any child or node with children all visited
"if ( n.left != null && n.left.visited = false )
stack.push( n.left )
else if ( n.left != null && n.left.visited = false )
stack.push( n.left )
else
res.push ( n )
"
- 4. Detect connectivity
- undirected:
- from some vertex, just apply DFS/ BFS only once is enough
- directed:
- apply DFS/BFS one time is not enough.
"- Because even though from one vertex can reach all other vertices, doesn't mean the other vertices can surely reach it.
- The definition is: any vertex can reach the others && when reverse direction, any vertex can also reach the others"
- solution:
- from some vertex, apply DFS/ BFS once
- if can't reach all nodes, return FALSE
- if can reach all nodes
- reverse the direction. Apply DFS/ BFS again
- if can't reach all node, return FALSE
- if can reach all nodes, return TRUE
- 5. Detect cycle ( degree is an easy approach )
"http://www.cnblogs.com/TenosDoIt/p/3644225.html"
- 无向图：
- 1.节点的度：从degree <= 1开始删除；
- 求出图中所有顶点的度，
- 删除图中所有度<=1的顶点以及与该顶点相关的边，把与这些边相关的顶点的度减一
- 如果还有度<=1的顶点重复步骤2
- 最后如果还存在未被删除的顶点，则表示有环；否则没有环
- 时间复杂度为O（E+V），其中E、V分别为图中边和顶点的数目，这个算法我们稍后分析算法3的时候再分析。
- 2. DFS + visited数组( 0/1/2 ) + parent数组：
"《算法导论》P331
http://www.cnblogs.com/TenosDoIt/p/3644225.html"
- 白色white： 表示尚未访问的点
- 灰色grey：表示正在访问，但未访问完其所有孩子(仍然有edge联系)
- 黑色black：完全访问完的点（edge也访问完了）
- pseudo code
"0 : white
1: grey
2: black
DFS( G )
for each vertex u belongs to V
color[u] = 0
p[u] = null
endfor
time = 0; // global var
d[ ] = new array[ ] // indicate the time first visit this node
f[ ] = new array[ ] // indicate the time finish its childrend
for each vertex u
if color[u] == 0
DFS-VISIT(u);
endif
endfor
DFS-VISIT( u )
color[u] = grey;
time = time + 1;
d[u] = time;
for each v adjacent to u
if color[v] ==1 && parent[u] != v
report "circle"!!!
else if color[v] == 0
DFS-VISIT(v);
endif
endfor
color[u] = 2;
time = time + 1;
f(u) = time;"
-
- 3. BFS + visited数组( 0/1/2 ) + parent数组：
"《算法导论》P331
http://www.cnblogs.com/TenosDoIt/p/3644225.html"
- 白色white： 表示尚未访问的点
- 灰色grey：表示正在访问，但未访问完其所有孩子(仍然有edge联系)
- 黑色black：完全访问完的点（edge也访问完了）
- pseudo code
"BFS( G )
for each vertex u belongs to V
color[u] = 0
p[u] = null
endfor
d[s] = 0; // 深度
p[ s] = null // 记录父节点
queue = new Queue();
queue.add(s);
qLen = 1;
color[s] = 1;
while( !queue.isEmpty() )
Node u = queue.removeFirst();
for each child v of u
if color[v] == 0
color[v] = 1
queue.add(v)
p[v] = u
d[v] = d[u] +1
elseif color[v] == 1 && p[u] != v
report "circle"!!!
endif
endfor
color[u] = 2;
endwhile
for each v adjacent to u
if color[v] ==1 && parent[u] != v
report "circle"!!!
else if color[v] == 0
DFS-VISIT(v);
endif
endfor
color[u] = 2;
time = time + 1;
f(u) = time;"
-
- 有向图：
- 1.节点的度：从 inbound degree=0开始删除；
- 拓扑排序，大家都知道的kahn算法：
- 计算图中所有点的入度，把入度为0的点加入栈
- 如果栈非空：
- 取出栈顶顶点a，输出该顶点值，删除该顶点
- 从图中删除所有以a为起始点的边，如果删除的边的另一个顶点入度为0，则把它入栈
- 如果图中还存在顶点，则表示图中存在环；否则输出的顶点就是一个拓扑排序序列
- 2. DFS + visited数组( 0/1/2 ) + parent数组（与无向图一致）：
"《算法导论》P331
http://www.cnblogs.com/TenosDoIt/p/3644225.html"
- 白色white： 表示尚未访问的点
- 灰色grey：表示正在访问，但未访问完其所有孩子(仍然有edge联系)
- 黑色black：完全访问完的点（edge也访问完了）
- pseudo code
"0 : white
1: grey
2: black
DFS( G )
for each vertex u belongs to V
color[u] = 0
p[u] = null
endfor
time = 0; // global var
d[ ] = new array[ ] // indicate the time first visit this node
f[ ] = new array[ ] // indicate the time finish its childrend
for each vertex u
if color[u] == 0
DFS-VISIT(u);
endif
endfor
DFS-VISIT( u )
color[u] = grey;
time = time + 1;
d[u] = time;
for each v adjacent to u
if color[v] ==1 && parent[u] != v
report "circle"!!!
else if color[v] == 0
DFS-VISIT(v);
endif
endfor
color[u] = 2;
time = time + 1;
f(u) = time;"
-
- 5. MST / MBST( Minimum Bottleneck Spanning Tree: for all the spanning trees, there exists a maximum edge in each tree, we choose the tree whose maximum is the smallest)
- MBST => MST : wrong
- 最大边有多条的情况
"ab = 6
ac = 6
ad = 1
cd = 1
bd = 8
exist two MBST: { ab ad cd } and { ab ac ad } whose maximum is both 6
but the MST is only { ab ad cd } "
- MST => MSBT : right
- prove:
- 1. contradiction by assume maximum edge in a MST is not the smallest
- 2. delete that edge E from MST, thus resulting in two separate parts,........( like proof of " cut property " )
- 6. k-clustering
- divide a set objects into k groups, in order to make each group
- use Kruskal's Algorithm, run n-k steps
- 7. a graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge (i.e., a unique edge of smallest cost) crossing the cut.
- Heap
- min-Heap / max-Heap
- 时间复杂度
"___________|__Binary Heap / amortized__||___Binomial Heap / amortized__||_Fibonacci amortized_
findMin | O(1) O(1) O(lgn) O(1)
insert | O(lgn) O(lgn) O(lgn) O(1) O(1)
extractMin | O(lgn) O(1) O(lgn) O(lgn)
delete | O(lgn) O(1) O(lgn) O(lgn)
decreaseKey| O(lgn) O(lgn) O(lgn) O(1)
merge | O(n) O(n) O(lgn) O(1) O(1)
construct | O(n) O(n) O(n) O(n)"
- binary heap
- createHeap O(n) :A binary max-heap can be built using an unsorted list of elements in O(n) time [ Bottom up ]
"视频35分：https://www.youtube.com/watch?v=B7hVxCmfPtM"
- binomial heap
- eagerly consolidate trees after each INSERT;
- implement DECREASE-KEY by repeatedly exchanging node with its parent.
-
- fibonacci heap
- Similar to binomial heaps, but less rigid structure.
- lazily defer consolidation until next EXTRACT-MIN/ Delete;
- implement DECREASE-KEY by cutting off node and splicing into root list.
- Common problem:
- 1. k largest(or smallest) elements in an array
- solution0: Bubble sort/ Insertion sort ( improved )
"1) Modify Bubble Sort to run the outer loop at most k times.
2) Print the last k elements of the array obtained in step 1.
Time Complexity: O(nk)
space complexity： O(n)"
- solution1: Max Heap
"1) Build a Max Heap tree in O(n)
2) Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)
Time complexity: O(n + klogn)
space complexity： O(n)
"
- solution2: Min Heap
"1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)
2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
……a) If the element is greater than the root then make it root and call heapify for MH
……b) Else ignore it.
Time complexity: O((n-k)*logk)
space complexity： O(k)"
- Union-Find
- 用途：
- 1. check两个元素是否属于同一个Union
- 2. get元素集合中共存在多少个Union
- 3. build 最小连通图( Kruskal Algorithm --- find minimun spanning tree for a graph )
"( 建立Union-find，依次尝试建立节点间连接，if already connected，discard such pair, continue）"
- API & time complexity
- create( int N ) ---> O(n)
- 实现：
"private int [ ] parent;
private int [ ] weight;
private int count;
public void UF( N )
{
count = N;
weight = new int [ N ];
parent = new int [ N ];
for( int i = 0; i < N; i++)
parent[ i ] = i;
}"
- find( int i ) ---> amortized O(1)
- 实现：每次find时候，update target的parent为grandparent节点( halve the height of tree)
"public int find( int i ){
while( i != parent( i ) ){
parent( i ) = parent( parent ( i ) );
i = parent ( i ) ;
}
return i;
}"
- isConnected( int i, int j ) ---> amortized O(1)
- 实现：
"public boolean isConnected( int i, int j ) {
return find( i ) == find ( j );
}"
- union( int i, int j ) ---> amortized O(1)
- 解释：
- parent[i] 记录其父亲，最好的情况是其父亲就是该union的root，不需要while循环
- 为使union操作后该union树结构平衡，用一个数组记录weight，light tree挂在heavy tree上
- 实现
"public void union( int i, int j )
{
int iRoot = find ( i );
int jRoot = find ( j );
if ( iRoot == jRoot ) return;
int iWeight = weight [ i ] ;
int jWeight = weight [ j ] ;
if( iWeight < jWeight )
parent( iRoot ) = jRoot;
else
{
parent ( jRoot ) = iRoot;
if ( iWeight == jWeight )
weight [ i ] ++ ;
}
count -- ;
}"
- count() ---> O(1)
- 实现
"public int count( )
{
return count;
}"
- Backtrack
- 分类：
"https://segmentfault.com/a/1190000006121957#articleHeader1"
- 1. 是否有解？ --- 返回True/False，或者其中一个解
- 2. 解有哪些？ --- 返回所有解Set
- 3. 最优解？ --- 返回符合条件的最优解
- 适用条件：“解”可以写成向量，解是在向量一步一步向外扩张形成的。
- 搜索空间：树结构。可以是由解构成的“n叉树”、“子集树”、“排列树”，树的节点对应于当前构成的向量，可行解都出现在叶子结点 ( Leaf Node )
- 回溯终止条件：遇到 Leaf Node
- recursion形式如下(subset举例)：
"List<> res
int[] set = [1，2，3 ]
ArrayList<T> prefix
int level = 0
void backtrack( prefix, set, level, res){
// leaf node -> need to return. also is base case for recursion
if( level == set.length){
res.add( new ArrayList<>(prefix) )
}
// recursive case
for( i =0; i < level; i++){
prefix.add( num[i] );
backtrack( prefix, set, i+1, res);
prefix.remove( prefix.size() - 1 );
}
}
"
- Greedy
- Three Proving methods 证明方法：
"general idea: solution found by Greedy is no worse than the others"
- 1. stay ahead
- IDEA: in each step, greedy stays ahead to other methods
- 2. exchange argument ( inversion )
- IDEA: suppose there exists an optimal solution other than ours, if we could modify that method with a few exchange or inversion, and our solution still no worse than the optimal method, we are good
- problems related to "order" or "sequence" , can absolutely apply "inversion"
- 3. Structural bound
- IDEA: if we can bound our method in a range, ie, no larger than a certain number, we
- How to solve?
- 1. transform into a mathematic formula with variables ( a concrete eg. is better )
"P3"
- 2. extract intuition from the formula, --> the come up greedy solution
- Common Problems:
- 1. Interval Scheduling: one recourse accommodating as many tasks as possible
"earliest-finish-time-first algorithm"
- Pseudo code:
"SORT jobs by finish time so that f1 ≤ f2 ≤ … ≤ fn
A ← φ
FOR j = 1 TO n
IF job j is compatible with A
A ← A ∪ { j }
ENDIF
ENDFOR
RETURN A"
- Time complexity
- O(n log n) : Sorting by finishing time
- 2. Interval Partitioning: min num of recourses to accommodating all tasks
"earliest-start-time-first algorithm"
- Min num of Processors for all different tasks
"Description: You are given n jobs each with a known start and end time. There are n identical processors. Two jobs with overlapping running times cannot be assigned to the same processor. Describe an algorithm to assign jobs to processors such that the number of processors utilized is
minimized.
"
- Pseudo code:
"SORT lectures by start time so that s1 ≤ s2 ≤ … ≤ sn.
d ← 0 // num of classrooms needed
pq = new priorityQueue(n) // used for store the room with the earliest finishing time
FOR j = 1 TO n
room = ExtractMin(pq);
IF lecture j is compatible with the finishing time of that room
Schedule lecture j in that room.
ELSE
Allocate a new classroom d + 1.
Schedule lecture j in classroom d + 1.
put this classroom into queue with it finishing time as the key
ENDIF
d ← d + 1
ENDFOR
RETURN d.
"
- Time complexity
- O(n log n) : Sorting by starting time & n tasks:O(n log n), and ExtractMin :O(logn)
- 3. tasks with deadline & weight ( two parameters needs to consider）
- Statement:
"Description: You are given n events where each takes one unit of time. Event i will provide a
profit of gi dollars (gi > 0) if started at or before time ti, where ti is an arbitrary real
number. (Note: If an event is not started by ti then there is no benefit in scheduling it
at all. (All events can start as early as time 0.) Given the most efficient algorithm you
can to find a schedule that maximizes the profit."
- 1~k task with different deadline Ti and its benefit Gi ( for which to be applicable, the task have to be scheduled at or before Ti)
- Note: the task could be like due at 3:25, 3:49, ...
- Solution:
- 1. we sort the jobs according to ⎿ Ti ⏌(sorted from largest to smallest) and go from back to front. And we maintain a priority Queue with Gi to be the key.
- 2. Consider the last time slot t (where initially t = ⎿ T1 ⏌). All the jobs i where ⎿ Ti ⏌ = t are inserted into the priority queue with the profit Gi used as the key.
- 3. An extractMax is performed to select this job to be the chosen one at time t.
- 4. Then t is decremented by one and the process of 2 and 3 is repeated.
- Time Complexity:
- O(nlog n)
- The sort takes O(n log n)
- there are at most n insert and exitractMax operations performed on the priority queue, each which takes O(log n) time.
- 4. distribute cake to kids
- description: cake is enough, been divided into n slices, to n kids with different appetite. How to satisfy max number of children
- solution
- 1. sort cake slices in ascending order, si
- 2. sort kid appetites in ascending order, ai
- 3. from i=0 to n, for every si, if si < ai, then exists a solution
- Prove in both ways( why ? because if this method cannot find a solution, we have to make sure that no other methods other than this one would find a solution. Otherwise, our method is not a qualified one. )
- 1. if for all 1 <= i <= n , we have ai <= si, then there exists a solution
- 2. if there exists an i such that ai > si, then no solution exists. ( have to been proved as well ! )
- Divide and Conquer
- Big-O / Ω / Θ
- f(x) = O(g(x)) : means that the growth rate of f(x) is asymptotically less than or equal to to the growth rate of g(x).
"-----------------upper bound-----------------"
- f(x) = Ω(g(x)) : means that the growth rate of f(x) is asymptotically greater than or equal to the growth rate of g(x)
"-----------------lower bound-----------------"
- f(x) = Θ(g(x)) : means that the growth rate of f(x) is asymptotically equal to the growth rate of g(x)
"-----------------in the middle-----------------"
- Main theory: T(n) = aT(n/b) + f(n) [ a≥1 && b>1 && f(n)>0 ]
- case 1: if f(n) = O( n^ [ logb(a) - ε ] ) && ε > 0
- T(n) = Θ( n^ [ logb(a) ] )
- case 2: if f(n) = Θ( n^ [ logb(a)] * [log(n)]^p ) && p ≥ 0
- T(n) = Θ( n^ [ logb(a) ] * [log(n)] ^ (p+1) )
- case 3: if f(n) = Ω( n^ [ logb(a) + ε] ) && ε > 0 && there is 0<c<1 let regularity condition holds: a*f(n/b)<c*f(n)
- T(n) = Θ( f(n) )
- Gaps in master theorem don't apply:
- 1. Number of subproblems must be a constant.
"T(n) = nT(n/2) + n2 ---- a should be constant"
- 2. Number of subproblems must be a ≥ 1.
"T(n) = 0.5 T(n/2) + n2 ---- a ≥ 1"
- 3. Non-polynomial separation between f(n) and n*logb(a).
"T(n)= 2 T(n/2) + n /log n --- here p < 0"
- 4. f(n) is not positive.
"T(n)= 2 T(n/2) - n^2 ---- f(n) should > 0"
- 5. Regularity condition does not hold.
"T(n) = T(n/2) + n*(2 - cos n) ---- a*f(n/b)<c*f(n) for an 0<c<1"
- Common Problem is:
- 1. count intervals
"merge and count"
- 2. finding the closest pair of points
"https://www.youtube.com/watch?v=xi-WF07rAQw"
- 3. Integer multiplication
- 4. finding the missing number from range [ 0, ... 2^(k-1) ]
- 1. loop once to count leftmost bit of each number, compare '0' and '1'
- if number of '0' > number of '1': the missing number with leftmost bit '1'
- else , the missing number with leftmost bit '0'
- 2. loop again to eliminate the number with leftmost bit with less number
- 3. do the same thing as 1,2 on the left half
- Divide and Decrease
- description: Given a n*n matrix where each of the rows and columns are sorted in ascending order and a value v, find v in the matrix.
- solution:
- 1. from topright (bottomleft) item in this matrix, let say it is s
- 2. if s > v, we can surely delete the row where s resides
- 3. else s < v, we can surely delete the column where s resides
- 4. repeat step 2 and 3, after we delete a row or column. Until find target v.
- Time Complexity:
- O(n) : if n is the number of col and rows, each time delete a row and column. So at most after n times, we can find the target value.
- Dynamical Programming
- 0. 写在前面： DP问题关键在于：子问题描述 + 递推式
- 1. 子问题描述： 一般尽可能多的用到变量（决定最优解的那些变量）
"子问题也可以从“table”的角度考虑，table中有多少个cell，就有多少个子问题；根据依赖关系，由最初子问题一步步推至最后子问题(即答案)"
- 2. 递推式(关键)： 没有思路时候，换一个变量盯着看（notice：利用给出的条件），其他变量跟着走
- 3. 例子：N工人分配到M工厂，每工厂i有一个对应工人数的收益p(i,j)，求最优分配
- 子问题： Max( n, m ) --> 求解Max(N,M) , 明显两个变量
- 递推式：
- 1. 盯“工人”看，第n号工人，并未给出关于第n个工人的信息，无果
- 2. 盯“工厂”看，第m号工厂，给出了关于第m个工厂的信息，因此
- B[m, n] = max { B[m-1, n-i] + p(m,i) }
- 三要素：
- 1 - 最优子结构 optimal substructure
" （父问题最优 =>子问题最优：可以作为突破口）"
- 2 - 重叠最优解 overlapping subproblems
"（求解当前问题，需要依赖之前子问题，有依赖关系）"
- 3 - 无后效性
"（某阶段状态受之前阶段决策的影响；不受这个状态以后决策的影响）"
- 求解思路：
- DP <==> Recursion + Memoized ( OR tabular ) + Guess ( carefully )
"0. in order to solve a larger problem, we solve smaller subproblems( they must overlap) and store their values in a table.
* Because of overlap, it not D&C
* Because of it tries every choice before the problem, it is not Greedy.
1。 主要思想：将第n步计算出来的结果保存起，在第n+1、n+2步需要使用第n步的结果时，不必再对第n步计算：memoize it
2。 多阶段决策过程 (实质) : opt(1) --> opt(2) --> opt(3) --> ... ... --> opt(n)
3。 符合最优子结构( optimal substructure) ：“一个问题的最优决策序列的任何子序列，其本身一定是相对于子问题的最优决策序列” a greedy algorithm is used to solve a problem with optimal substructure if it can be proved by induction that this is optimal at each step"
- 1. 问题建模， 目标函数、约束条件
- 2. 如何划分子问题
- 3. 递推方程（ 问题与子问题的关系），看是否满足优化原则（最优子结构optimal substructure）
- 4. 子问题的初值
- Two ways to do DP ( fibonacci example )
- 1. up-bottom(Memoization) : recursion + memoized table
"hashMap<Integer, Integer> memo = new hashMap<>( );
public int fab( int k )
{
if ( memo.containsKey( k ) )
return memo.get( k );
int res = 0;
if ( k <= 2 ) res = 1;
else res = fab( k -1 ) + fab( k - 2 );
memo.put ( k, res );
return res;
}"
- 2. bottom-up(Tabulation): iteration ( no extra memory due to its intrinsic in-order character)
"int[ ] memo = new int[ k ] ;
public int fab( int k )
{
for ( int i = 0; i < k; i ++ )
{
if ( k <= 2 ) memo [ i ] = 1;
memo[ i ] = memo[ i - 1 ] + memo [ i - 2 ];
}
return memo[ k ];
}"
- When bottom-up，一定要符合Topological sort of subproblem dependency DAG
"f1 ---> f2 ---> f3 ---> f4 ---> f5
|_______|_____/ | / /
|______ |____/ /
|________/
由上图： topological sort: f1 f2 f3 f4 f5
f5 依赖 f3/f4; f4 依赖 f2/f3; f3依赖 f2/f1
“依赖” <=> “入度不为0”
"
- 结论： 如果依赖关系不清楚的话，可以借助topological sort搞清楚，按此顺序依次求解
- 注意： 问题的必须为DAG( acyclic )，不能存在“环”，即
- 1. 第n步问题，不能依赖于第n+1步问题
- 2. 第n步问题必须只能由之前的问题解决，不能存在第n+1步也能解决的情况
- DP分类
- 0. 写在前面： DP问题关键在于：子问题描述 + 递推式
- 1. 子问题描述： 一般尽可能多的用到变量（决定最优解的那些变量）
- 2. 递推式(关键)： 没有思路时候，换一个变量盯着看，其他变量跟着走
- 1. By table dimension（table维度）
- 一维 ：子问题一端固定，另一端伸缩
- 切棒子(棒子首端不动，末端伸缩）
- cutRod[k] = max( price[i] + cutRod[k-i-1] ) for all i in {0, 1 .. k-1}
- 二维：
- 1. 子问题两端都不固定，两个方向伸缩
- Matrix chain multiplication（矩阵链左端不可以固定）
- opt[ i, j ] = min{ opt(i, k) + opt(k+1, j) + pi*pk*pj }, k = i, ... , j
- 2. 子问题有两个变量决定
- 0-1背包问题（物品数目、背包承重量）
- opt[k, w] = max(vk+ OPT [k-1, w–wk], OPT[k-1,w])
- 三维：
- 子问题由三个变量决定( “0-1背包问题” 升级版 ）
- 1. S个运动员，B辆小车，做N个项目，或得最大效益P
- 背包问题相似：限制条件有两个--- s<S、b<B限制
- opt[ i, s, b ] = max{ pi + opt[ i-1, s-si, b-bi], opt[i-1, s, b] }
- 2. n客人，出价bi，住di天，问：D天，2个房间，如何安排收益最大
- 背包问题：限制条件虽只一种：d<D; 但有两个 d<D1, d<D2
- 2. Combination【0-1背包】 VS. Permutation【决策树】
- Combination: ( 不计顺序，只看有无：0-1背包 )
- 4.Coin Changing Ways
- Permutation: ( 顺序matter，紧盯第一位or最后一位 )
"Given n , you need to find the number of different ways to write n as the sum of numbers 1, 3, and 4.
Example: for n = 5 the answer is 6. The six ways are 1+1+1+1+1, 1+1+3, 1+3+1, 3+1+1, 1+4, 4+1. "
- C(n) = C(n-1) + C(n-3) + C(n-4), where C(1)=1, C(2)=1, C(3)=2, C(4)=4
- n的相加方式一定可以由3种情况决定并组成(决策树)：
"第一位是“1”，第一位是“3”，第一位是“4”"
- 最后一位是“1”的情况的数目 加上
- 最后一位是“3”的情况的数目 加上
- 最后一位是“4”的情况的数目
- 3. By relationship between problem and subproblem（递推公式）
- 只与之前某几项有关： OPT(k) = c* OPT(k-1) + c(1, k) / c(k,n)
- 与之前所有项有关： OPT(k) = min/max{ c(i,k) + OPT(i) }
- Common Problems
- 0. Bellman-Ford vs Floyd-Warshall ( 参考graph内容)
- 1. Longest Common Subsequence
- 问题表述：
"A B A Z D C
\ \ \ |
B A B A D"
- Given a string S of length n, and string T of length m. Our goal is to produce their longest common subsequence.
- A subsequence is a subset of elements in the sequence taken in order (with strictly increasing indexes.) Or you may think as removing some characters from one string to get another.
- 子问题:
- Let LCS[i, j] be the length of the LCS of S[1 · · ·i] with T[1 · · · j]
- 递推式
- Case 1. S[i] = T[j], LCS[i, j] = 1 + LCS[i-1, j-1]
- Case 2. S[i] ≠ T[j], LCS[i, j] = max{ LCS[i-1, j], LCS[i, j-1] }
- 伪代码
"int LCS(char[] S, int n, char[] T, int m)
{
int table[n+1, m+1];
table[0…n, 0] = table[0, 0…m] = 0; //init
for(i = 1; i <= n; i++)
for(j = 1; j <= m; j++)
if (S[i] == T[j])
table[i, j] = 1 + table[i-1, j-1]
else
table[i, j] = max(table[i, j-1], table[i-1, j]);
return table[n, m];
}"
- 时间复杂度: O(mn)
- 2. Fibonacci
- D&C approach: T(n) = T(n-1) + T(n-2) + Θ(n) = 2^n !!!!!!
- why Θ(n) ?
- Claim 1. We need log(n) bits to represent any decimal integer n.
- Claim 2. We need n bits to represent Fibonacci number Fn
- Fn的bit input size 为log(Fn)， 所以需要 log(Fn)次时间的bit加法
"log(Fn) = log(θ(φ^n)) = θ(log(φ^n)) = θ(n log(φ)) = θ(n)"
- why so slowly? repeatedly and unnecessarily computing same f(n)
- solution: 记录下已经计算好的值，之后的步骤直接使用 --> memo --> DP
- DP: T(n) = T(n-1) + Θ(n) = Θ(n^2)
- Complexity
- 时间复杂度： O( n )
- 空间复杂度： O( n )
- 如果明确知道f(n) 只依赖两个之前的结果f(n-1) 与 f(n-2)，那么对于bottom-up的方式，只需要用两个var即可，空间复杂度优化为 O( 1 )
- 3. Min Coin Changing Problem
- k demominations, a cash values n coin, give minimum number of change
- c[ k, x ] = MIN( 1+ c[ k, x - dk ], c[ k-1, x ] )
- O(mn)
- 4. Coin Changing Ways
- k demominations, a cash values x coin, give how many number of changes
- num[ k,x ] = num[ k, x - dk ] + num[ k -1, x ]
- O(mn)
- 5. Cut rod
- 每种长度对应一个价格， 求给定长度的费用最大值
- cutRod[k] = max( price[i] + cutRod[k-i-1] ) for all i in {0, 1 .. k-1}
- 6. Decode ways( A-1, B-2, C-3, ... )
- A message containing only letters is encoded in the following ways: a-1, b-2, c-3,d-4,... Design an algorithm to calculate the number of ways to decode a given message M. For example, for the message M=‘12’, we can decode it as ‘AB’ or ‘L’, so there are 2 ways to decode it.
- SubProblem: OPT(i) means till ith letter, the number of decoding ways
- Solution: (先判断条件1、2， 然后判断 3)
- 0. OPT[0] = OPT[1] = 1;
- 1. if( M[i] = '0' ) OPT(i) = OPT(i-2);
- 2. if( M[i-1] = '0' ) OPT(i) = OPT(i);
- 3. if( M[i-1] < '2' && M[i] < '6' ) OPT(i) = OPT(i-1) + OPT(i-2)
- 7. Knapsack Problem(0-1问题) --- 【 7、8、9、10、11同类型：决策树】
- unique items with weight and value, but the knapsack capacity is fixed. try to put highest items in it within the capacity.
- brute force: O(2^n) -- pick it or not pick it
- OPT[k,w] = MAX( vk + OPT[k-1,w-wk], OPT[k-1,w] )
- O(n*w)
- 8. Decision Tree/ Permutation --- 【 7、8、9、10、11同类型：决策树】
- Given n , you need to find the number of different ways to write n as the sum of numbers 1, 3, and 4. Example: for n = 5 the answer is 6. The six ways are 1+1+1+1+1, 1+1+3, 1+3+1, 3+1+1, 1+4, 4+1.
- C(n) = C(n-1) + C(n-3) + C(n-4), where C(1)=1, C(2)=1, C(3)=2, C(4)=4
- n的相加方式一定可以由3种情况决定并组成(决策树)：
"第一位是“1”，第一位是“3”，第一位是“4”"
- 最后一位是“1”的情况的数目 加上
- 最后一位是“3”的情况的数目 加上
- 最后一位是“4”的情况的数目
- 9. Matrix chain multiplication --- 【 7、8、9、10、11同类型：决策树】
- Description: given A1 * A2 * A3 * Ak * ... * An-1 , parenthesize this multiplication chain, in order to minimize the number of multiplication among these matrix as possible.
- ❶Statement:
- what is the # of multiply ? A(i,k) × B(k,j)
"matrix A (5 row, 3 col), and B (3 row, 8 col) , the result C (5 row, 8 col)C34= A3[1,2,3 ] × B[1,2,3] 4 = A31*B14 + A32*B24 + A33*B34So, for each Cij, the total # of multiply : i*j*k"
- maintain dimension array to record the dimension of A1 ... An-1. P= [ p0, p2,..., pn ]
"A1(2,3), A2(3,5), A3(5,8), A4(8,4) ==> P = [ 2, 3, 5, 8, 4 ] => P[0] P[1]: A1 / P[1] P[2]: A2 "
- == How to parenthesize P, to minimize multiplication number?
- ❷solution
- How to subproblem it ? optimal substructure
- Guess: divide it by last time multiplication
- 每一个子问题都存在最后一步由两个矩阵相乘才得到最终矩阵。
- A1(A2..An-1) 、(A1A2)(A3..An-1) ... =>最后一步2个矩阵相乘的情况会有n-1种
- 对于每一个子问题又存在这种模式：最后两矩阵相乘。m(i,j) :矩阵i到j最优相乘次数
- 只要在这n-1中情况中，选择出min( m(i,k) + m(k+1,j) + p[i]*p[k]*p[j] ),我们就得到了最优解
- bottom-up
- 由Guess得到：大问题依赖子问题，子问题依赖更小子问题
- 可以采用iterative方法，从最小问题开始求解。即
"P(i,i+1) --> P(i,i+2) --> P(i,i+3) -->P(i,i+k) -->P(1,n)最终问题"
- pseudo code
"MatrixChain( p, n )
令所有 m(i, i) = 0; // m(i, j) 矩阵i到j最优相乘次数
令所有 s(i, j) = 0; // s (i, j) 矩阵i到j分隔位置,找最终结果用
for r = 2 to n // r 为链长
for i = 1 to n-r+1 // 左边界 i , 计算长为r的链乘的所有情况，并得到min(i,j)
j = i+r-1 // 右边界 j
m(i, j) = m(i, i)+ m(i+1, j) + p[i-1] p[ i] p[ j] // 第一种情况, k=i
s[i, j] = i
for k = i+2 to j // 遍历k，计算其他组合情况
t = m(i, k) + m(k+1,j) + p[i-1] p[k] p[j]
if t < m(i, j)
m(i, j) = t
s(i, j) = k
endif
endfor
endfor
endfor
"
- How to extract parentheses location ? --- need additional matrix
- s(i ,j) : when pick smallest value from using k intermediate value, meanwhile, record the intermediate value we picked
- ❹Complexity
- time：O(n^3)
- space: m(i,j) and s(i,j) : O(n^2)
- 10. Static Optimal BST --- 【 7、8、9、10、11同类型：决策树】
- 背景：
- 1. "static" means the database remains unchanged, no new data inserted or updated.
- 2. Build a BST which gives a minimum average-case retrieval cost
- 写在前面：
- 这里的k1, ..., kn 如果之前没有排序，在做题之前一定要排好序，这样才能应用二叉搜索树的性质：左子树 < 根 < 右子树
- 问题表述：
- Given sequence k1, k2, ··· , kn of n keys, with a search probability pi for each key ki
- For key ki, search cost = depth(ki), where we assume that the root depth is 1.
- Want to build a binary search tree from the keys with minimum expected search cost: Cost = sum { pi * depth(ki) }
- 子问题:
- OPT[i, j] is the optimal cost for ki, …, kj , where 1 ≤ i ≤ j ≤ n
- 递推式:
- OPT[i, j] = min{ OPT[i, r-1] + OPT[r +1, j] } + pi+ ... +pj
- OPT[i, i] = pi, for 1 ≤ i ≤ n
- OPT[i, i-1] = 0, for 1 ≤ i ≤ n (防越界)
- 伪代码:
"OPT[i, i-1] = 0, for 1 ≤ i ≤ n
OPT[i, i] = pi, for 1 ≤ i ≤ n
for(k = 1; k < n; k++)
for(i = 1; i <= n-k, i++)
j = i + k;
OPT[i, j] =pi+…+pj+ min{ OPT[i, r-1]+OPT[r+1, j] }; (i ≤ r ≤ j)
endfor
endfor
output OPT[1, n];"
- 时间复杂度: O(n^3)
- 11. Polygon Triangulation --- 【 7、8、9、10、11同类型：决策树】
- 问题表述：
- Given is a convex polygon, we would like to triangulate this polygon, i.e. decompose it into disjoint triangles by adding line segments (diagonals) between its corners (vertices).
- triangulating a convex polygon with n vertices while minimizing the total perimeter of all the triangles.
- 子问题: 关键在于设定base edge为1st Node to last Node
- Let OPT[i, j] denote the minimum triangulation for the subpolygon (i, i+1, …, j-1, j) where 1 ≤ i < j ≤ n.
- We may split this subpolygon into three parts: a single triangle, the subpolygon to the left, and the subpolygon to the right.
- 递推式
- OPT[i, j] = min (OPT[i, k] + OPT[k, j] + perimeter ) i<k<j
- OPT[i, i] = OPT[i, i+1] = 0
- 伪代码
- 类似 --- Matrix chain multiplication
- 时间复杂度 O(n^3)
- Network Flow ( 有向图／无向图--->有向图 )
- 0. 写在前面：注意Graph中5个量的赋值
- 1. bipartite 两个set之间的方向含义
- 2. bipartite 两个set之间的赋值含义
- 2. Node ‘s' 到左侧set点之间的赋值含义
- 3. Node ‘t' 到右侧set点之间的赋值含义
- 5. Node ‘t' 与 ‘s' 之间是否需要赋值、指向
- 6. fe ≤ Ce , fe ≥ Le是闭区间，在设定Ce时，区别 Ce=M or Ce= M-1
- 1. Max Flow <---> Min Cut
- Max Flow
- what is 'one' augmentation?
- 1. corresponding to a Gf
- 2. corresponding to a P path
- 3. corresponding to a Edge in a path
- solution:
- algorithm 1: Ford–Fulkerson ---- O( C*(E+V) ) ---- pseudo polynomial
- algorithm 2: Δ - Scaling -------- O( logC*E^2 ) ---- weakly polynomial
" Pseudo Code:
Set Δ to be 2^Δ< max{ c(e) out of s }
Consider the residual graph Gf(Δ) consisting only of edges with c(e) > Δ
while (Δ≥1)
construct Gf(Δ) or update Gf(Δ)
while ( still exist augmenting path)
augment flow
update Gf(Δ)
end while
Δ= Δ/2
end while
return f"
- 时间复杂度：
- O( logC*E^2 )
- 外层循环Δ： O( logC ) --- 不断减小 Δ
- 内层循环：O(2m*m) --- 找augmenting path O(2m)，然后进行augment O(m)
- algorithm 3: Edmonds-Karp ---- O( V*E^2 ) ---- strongly polynomial
" Pseudo Code:
1: f ← 0; Gf ← G
2: while Gf contains an s−t path P do
3: Let P be an s−t path in Gf with the minimum number of edges.
4: Augment f using P.
5: Update Gf
6: end while
7: return f"
- 思路：
- 1. Start with |f|=0, so f(e)=0
- 2. BFS Find an augmenting path with min number of edges in Gf
- 3. Augment flow along this path
- 4. Repeat until there is no an s-t path in G
- 时间复杂度
- O(V * E^2)
- 外层循环：O(E*V) --- 用BFS找最短边数的augmenting path的次数
- 内层augment： O(E+V)
- Strongly Polynomial vs. Weakly Polynomial vs. Pseudo Polynomial
"“时间复杂度函数中的每一项 <---> 输入量的每一项” 决定到底属于哪一种"
- 1. Strongly Polynomial: 即正常的多项式时间复杂度 -- Edmonds-Karp
- input size: O(n * m^2 * 32^3)
- time function: O(n*m^2)
- 2. Weakly Polynomial: 弱多项式时间复杂度 -- Δ - Scaling
- input size: O(log C * m^2 * 32^2)
- time function: O( log C * m^2 )
- 3. Pseudo Polynomial: 伪多项式时间 [ explanation: week 7video - 1:14:47 ] - FF
"1. https://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time
2. https://www.zhihu.com/question/20013122
3. http://www.matrix67.com/blog/archives/105"
- input size: O( n (lgW + lgV) )
- time function: O( n*W)
- de facto time complexity: O( n * 2^(lgW) )
- eg. & explanation:
"当我们处理一些图论、链表、数组、树等问题时，这个标准定义下的多项式时间和我们传统的多项式时间相差无几。比如，用选择排序对元素个数为的数组进行排序时，传统时间复杂度为。输入规模，因此，得到的标准时间复杂度是，仍然是多项式时间。
现在我们来讨论判断一个整数是否为素数的算法，下面是一个简单的算法：function isPrime(n):
for i from 2 to n - 1:
if (n mod i) = 0, return false
return true
显然，这个算法在传统时间复杂度计算方法中是多项式时间的。我们不妨认为它的传统时间复杂度是。然后我们再来分析这个问题的输入规模，可能有的同学会说，对于32-bit整数，这个输入规模不就是32吗？这话虽然没错，但是因为在这个问题中，输入规模完全依赖于n的大小，所以n的范围不再限制在32-bit整数的范围内，而是要探讨当n更大时对数据规模的影响。我们知道，保存一个整数所需要的bit位数x=lgn，因此，在标准的时间复杂度中，此算法的复杂度变为了O(2^4x)! 这已经不再是多项式时间，而是一个指数时间。
"
- Common problem
- 1. Given max flow f, decrease Ce of one edge by 1, what is new max flow
"Problem: you have successfully computed a maximum s-t flow f for a network G = (V; E) with integer edge capacities. Your boss now gives you another network G’ that is identical to G except that the capacity of exactly one edge is decreased by one. You are also explicitly given the edge whose capacity was changed. Describe how you can compute a maximum flow for G’ in O(|V| + |E|) time."
- 1. if the flow on it f(e) < Ce, max flow stay the same
- 2. if the flow on it f(e) = Ce, decreasing Ce by 1 doesn't necessarily means that the max flow would drop
- - starting from this edge, find a path P1 carrying flow to t
- - starting from t, find a path P2 to this edge carrying flow
- - decrease the flow on edges along P1 and P2
- - create new Gf, see if there exist an augmenting path
- if Yes, f stay the same
- if NOt, f now is (fmax -1)
- Min Cut
- Max Flow <---> Min Cut
- min cut截面上的flow：out of A*---全盈满； in to A*---空flow！
- cut capacity: C(A,B) = capacity of cut A/B = SUM( Ce out of A ), 只计算从A出去的
- 已知max flow，如何找出minCut ？
- 找到Max flow之后，根据每个edge的flow，形成residual graph: Gf
- BFS遍历所有s可达的点，构成点集A；剩下的为B
- 已知min cut，如何求max v(f) ？
- 找到处于min cut上的Edge
- 对所有流出s的edge的Ce求和，得到minCut capacity，即为v(f)
- minCut 唯一么？
- No s ->a -> t two edges are 1
- minCut 是否唯一,如何确定？
- 1. reverse all edge in G, to form G'; Find minCut in G'
- 3. if the minCut is the same as that of G ---> unique
- 2. Bipartite Matching
- Bipartite Graph definition: (多夫多妻)
- A bipartite graph G=(V,E) in an undirected graph whose node set can be partitioned as V= X U Y, with property that every edge e has one end in X and the other in Y.
- Matching definition:（一夫一妻）
- A matching M in G is a subset of the edges M belongs to E, such that each node appears in at most one edge in M
- Solution：
- 1. Design a flow network G' on this bipartite graph(无向变有向)
- 2. set all edges with Ce = 1
- 3. find maxFlow, see if maxFLow=|X|
- Correctness Prove:
- 正向：
"if we have a s-t flow of value k in G', we can find a matching of size k in G"
- 反向：
"if we have a matching of size k in G, we can find a s-t flow of value k in G'"
- Common problems
- Example: (田忌赛马)USC - UCLA tennis player match
- Time Complexity: Polynomial time ( NOT pseudo-polynomial )
- why? because O(C*m) 中的C不是一个“wild number”，而是顶点链接的点个数，顶多n个
- Example: Rook Attack
- This problem asks us to place a maximum number of rooks on a chessboard with some squares cut out. The rook moves horizontally or vertically, through any number of squares
- Rows and columns are two sets. For each row add edges to every column if the square is not cut out.
- 3. Edge-disjoint Path
- Definition:
- a set of paths is edge-disjoint if the edge sets are disjoint
- Directed Graph
- Problem statement
- Given a directed graph G with s & t belong to V, find max number of edge-disjoint s-t paths in G
- Solution
- make a flow network G' on the original G, by limiting the Ce = 1 to all edges.
- find out the max flow of G', then v(f) is target value
- Correctness Prove
- 正向：
"if we have k edge-disjoint s-t paths, we can find a flow of value k in G'"
- 反向：
"if we have a flow of value k in G', we can find k edge-disjoint s-t path in G"
- Common problem
- 1. Example: graph has 1-unit-edge, how to delete k edges to reduce max flow largely?
- general idea: treat it as edge-disjoint path problem, delete k edge-disjoint path
- strategy:
- run max-flow to get the min cut
- delete k edges from f*
- if |f*| >= k, f* = |f*| - k
- else f* = 0;
- 2. Consider the following problem: Given a flow network G with source s and sink t, and a unique s − t min cut, find k edges that, when deleted, reduce the maximum s − t flow in the graph by as much as possible.
- Wrong: Find the s − t min cut in G. Sort edges on the min cut in decreasing order of weightDelete the first k (highest capacity) edges from the ordered list
- Undirected Graph
- solution:
- 1. 无向变有向：将所有边变为双向边，Ce=1
- 2. run Ford-Fulkerson，找出maxflow
- 3. check exists cycle, if exist, delete them
"如果存在环的话，那么就会形成edge-share，不符合题意，所以要删掉"
- Example: human-eating plants maze
- 4. Node-disjoint Path
- Node-disjoint Def：
- a set of paths is node-disjoint if the nodes sets( except s & t) are disjoint
- Problem statement
- Given a directed graph G with s&t belongs to V, find the max number of node-disjoint s-t paths in G
- Solution:
- 1. convert Node into Edge, with Ce=1, and one node receiving flow, the other sending flow
- 2. create flow network on new G, and run FF
- 3. the maxFlow is the node-disjoint path
- 5. Circulation with demand: feasible circulation in G <=> MaxFlow = D in G'
- solution:
- first sum up all d to see if == 0
- if != 0, no feasible circulation
- else, add super s & t to supply nodes and demand nodes respectively.
- run FF, see v(f)
- if v(f) = D, feasible
- if v(f) < D, not feasible
- if v(f) > D, NO WAY!
- Correctness proof:
- 正向
"if there is a feasible circulation f with demand value {dv} in G, we can find a max flow in G' with value D"
- 反向
"if..."
- Example: human-eating plants maze
- 6. Circulation with demand & lower bound
- Lv: flow imbalance at Node v
"跟 “demand constrain” 一致： dv = fin(v) - fout(v)
Lv = fin(v) - fout(v) = sum Le(in) - sum Le(out)"
- Solution:
- 1. reduction of lower bound:
- f0(e) = Le - find f0 to satisfy all Le
- 2. create flow network G':
"use remaining capacity of the network to find a feasible circulation f1( if it exists)"
- C'e = Ce - Le
- d'v = dv - Lv
- 3. find feasible circulation f1 in G'
- if no feasible in G', then no feasible in G
- else, feasible circulation is f0+f1
- Common Problems
- Example 1: Survey design
- Example 2: TA's office hour assignment
- 7. Min Flow
- Statement:
- given a G, edge with only Le, no Ce, what is the Min Flow on this G?
- Solution:
- 1. Create a G' with Ce having big enough value;
- Find a valid max flow in G', thus we have fmax(e) on each edge
- 2. Create another G'', with Ce = fmax(e) - Le;
- Find max flow in G'', we get f'max(e) on each edge
- 3. Min Flow on each edge, is now fmin(e) = fmax(e) - f'max(e)
- Example: Airline Scheduling
- 8. Discussion --- week 9
- problem 1:
- 易错解法： 找这条边的两个点是否处在minCut上
- yes， maxflow-1
- no， maxflow+1
- 正确解法：
"即便(v,u)在minCut上，不一定maxflow减少，因为有可能还有值相同的另一个minCut"
- 找任一条携带flow的s->v, 与 u->t的路径，其上的f(e) 全部减1
- 根据当前flow，做Gf，继续augmentation，看是否有s->t的路径
- yes，maxflow 不变
- no， maxflow-1
- problem 3:
- 注意gate node与t点之间的Ce的赋值，不可以赋值为‘1’
- 因为如果赋值为‘1’，t与gateNode之间的edge可能成为minCut；然而这些edge是后来加上的虚构的线，所以一定不能更让这些edge被选为minCut
- 所以 edge[ t, gateNode ] 设置为Ce = ∞