## 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以下的数据删掉，但是这种方法不可回溯

## 算法设计与分析笔记0x07 —— 动态规划(1)

Divide and Conquer 小问题中独立解决

• Dynamic Programming 小问题是有重叠的
• 分隔时，父问题共享子问题

## Integer Multiplication

Brute force solution: $\Theta(n^2)$ bit operations.
To multiply two n-digit integers: (warm up)

• Multiply four n/2-digit integers.
• Add two n/2-digit integers, and shift to obtain result.

$x = 1000 1101$, $x_1 = 1000$, $x_0 = 1101$

## 算法设计与分析笔记0x05 —— 分治法(1)

Divide and Conquer

• Break up problem into several parts
• Solve each part recursively
• Combine solution to sub-problems into over solution

$$T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + n$$
We solve it and get T(n)=O(nlogn), which could be proved by several methods mentioned in Basic Algorithm Note.

## 算法基础笔记0x06 —— 二叉搜索

Dictionary also called dynamic set, which support the following operations.

• find(k) returns 1 if k is in D, 0 otherwise.
• insert(k) puts k in D.
• delete(k) removes k from D.
• pred(k) / succ(k) return the predecessor / successor to k in D, resp.
• min / max return the minimum / maximum value in D, resp.

## Search Algorithm

• 给定一个排好序的数组，搜索输入x
• Idea Maintain an interval between [l, r] where x may be. Shrink the interval as quickly as possible.
• Initially the interval is all of A, i.e. l = 1, r = |A|.
• Use a probe point m = (l + r) / 2.
• If x < A[m], x can’t lie in [m, r], so keep searching in [l, m-1].
• If x > A[m], keep searching in [m+1, r].
• If l = r but x ≠ A[m], then x is not in A.