## KMP

m is the length of text
n is the length of pattern

• [Prefix Array Logic]
• 初始j指向0索引，i指向1索引
• 数组0索引初始化为0
• 检查匹配
• 不匹配时，跳到j索引的前一个数组值所对应的索引位置继续检查匹配
• 不匹配时，j=Array[j-1]
• 若j是0，数组值为0，Array[i]=0
• 匹配时，数组中的值为j的值加1，i和j同时加1继续检查匹配
• Array[i]=j+1, i++, j++

## 算法设计与分析笔记0x10 —— Extending the Limits of Tractability

Must sacrifice one of three desired features.

• Solve problem to optimality.
• Solve problem in polynomial time.
• Solve arbitrary instances of the problem.

## 算法设计与分析笔记0x0F —— PSPACE

P Decision problems solvable in polynomial time.
PSPACE Decision problems solvable in polynomial space.

• P PSPACE
• 3-SAT is in PSPACE
• NP PSPACE

## Partitioning Problems

### 3-Dimensional Matching

3D-MATCHING. Given n instructors, n courses, and n times, and a list of the possible courses and times each instructor is willing to teach, is it possible to make an assignment so that all courses are taught at different times?
3D-MATCHING. Given disjoint sets X, Y, and Z, each of size n and a set T X × Y × Z of triples, does there exist a set of n triples in T such that each element of X Y Z is in exactly one of these triples?

## 算法设计与分析笔记0x0C —— Part 1 NP完全

Algorithm design patterns.

• Greedy.
• Divide-and-conquer.
• Dynamic programming.
• Max-flow min-cut.
• Reductions.

Algorithm design anti-patterns.

• NP-completeness.
• PSPACE-completeness.
• Undecidability.

## Image Segmentation 图像分割

• $a_i$, likelihood pixel i in foreground.
• $b_i$, likelihood pixel i in background.
• $p_{ij}$, separating penalty for labeling one of i and j as foreground

## 算法设计与分析笔记0x0A —— 网络流应用(1)

Soviet Rail Network

## Bipartite Matching

• Goal: Maximize matching
• Input: undirected, bipartite graph $G(L\cup R, E)$.
• Matching: 每个节点只在一条边出现

## Max-flow and Ford-Fulkerson Algorithm

• 网络流是一个有向图，源点s，汇点t
• 每条边流量f(e)不能超过容量c(e)
• 守恒: 指向结点的流量之和($\sum_{e\,in\,to\, v}f(e)=\sum_{e\,out\,of\,v}f(e)$)等于流出结点的流量之和 (except source and sink points)
• 流的值: 流出源点的流量综合 $v(f)=\sum_{e\,out\,of\,s}f(e)$.
• Max flow problem 找到 s-t flow 使其流的值最大
• Greedy algorithm: 局部最优, 非全局最优.
• Start with f(e) = 0 for all edge e ∈ E.
• Find an s-t path P where each edge has f(e) < c(e).
• Augment flow along path P.
• Repeat until you get stuck.

## Sequence Alignment: Linear Space

How can we use $\Theta(m+n)$ space and $O(mn)$ time.

• Compute OPT(i,*) from OPT(i-1,*)
• 可以把i-1以下的数据删掉，但是这种方法不可回溯