### 1. NP problem

undecidable problems

decidable problems: P, NP

turing machine: 图灵机：改变状态，在当前位置擦除并写入符号，左、右、或不移动

• Deterministic Turing Machine

executes one instruction at each point in time. Then depending on the instruction, it goes to he next unique instruction.

• Nondeterministic Turing Machine

free to choose its next step from a finite set. And if one of these steps leads to a solution, it will always choose the correct one.

NP: Nondeterministic polynomial-time

NP problem: we can prove any solution is true in polynomial time.

NP-complete problem: any problem in NP can be polynomially reduced to it. Not all decidable problems are in NP.

For example: the problem of determining whether a graph does not have a Hamiltonian cycle.

NPC problems examples:

• Hamiltonian cycle problem: Given a graph G=(V, E), is there a simple cycle that visits all vertices?
• Traveling salesman problem: Given a complete graph G=(V, E), with edge costs, and an integer K, is there a simple cycle that visits all vertices and has total cost <= K?
• Satisfiability problem (Circuit-SAT): Input a boolean expression and ask if it has an assignment to the variables that gives the expression a value of 1
• Vertex cover problem

### 2. Approximation

approximation ratio: $R(x,y)=\max \left( { \frac{OPT}{f(y)}}, { \frac{f(y)}{OPT} } \right )$

r(n) approximation.

(1+ e)-approximation algorithm:

• polynomial-time approximation scheme (PTAS):

if for any fixed e > 0, the scheme runs in time polynomial in the size n of its input instance

$O(n^{\frac{2}{e}})$

• fully polynomial-time approximation scheme (FPTAS):

fully的意思是关于(1/epsilon)和n都是多项式级的

$O((\frac{1}{e})^{2} n^{2})$

Bin packing

• next fit 2M-1
• first fit 1.7M
• best fit 1.7M
• worst fit 1.7M

offline:

first fitting decreasing : 11/9*M + 6/9

The Knapsack Problem (01 version)

K-center problem

• vertex cover problem:

Given an undirected graph G = (V, E). Find a minimum subset S of V such that for each edge (u, v) in E, either u or v is in S.

delete from G(V, E)

• Hopfield Neural Networks

Graph G = (V, E) with integer edge weights w (positive or negative).

If we < 0, where e = (u, v), then u and v want to have the same state;

if we > 0 then u and v want different states.

for a good node v (e has one endpoint v):

$\sum_{e \in E}w_{e} \times S_{u} \times S_{v} \le 0$

〖Definition〗A configuration is stable if all nodes are satisfied.

a Hopfield network always have a stable configuration.

### 4. Randomized Algorithms

• The hiring problem

### 5. Parallel Algorithm

• Parallel Random Access Machine (PRAM)

• Arbitrary rule
• Priority rule (P with the smallest number)
• Common rule (if all the processors are trying to write the same value)
• Work-Depth (WD)

### 6. External Sorting

$passes = 1 + \lceil log_{k}{N/M}\rceil$

$tapes = 2k$

polyphase merge:

k+1 tapes

### 7. Greedy

​ Make the best decision at each stage, under some greedy criterion. A decision made in one stage is not changed in a later stage, so each decision should assure feasibility.

1. Activity Selection Problem

1. Huffman Codes

$T = O(N )$

### 8. Dynamic Programming

1. fibonacci numbers

1D DP
$T = O(N)$

1. 矩阵乘法排序

2. 最优二叉搜索树

$C_{Left,Right} = \min_{Left{\leq}i{\leq}Right}({C_{Left,i-1}}+C_{i+1,Right}+\sum_{j=Left}^{Right}{p_j})$

1. 所有点对最短路径

### 9. Divide and Conquer

​ $T(N)= aT(N/b) + f(N)$

1. If $af(N/b) = k f(N)$ for some constant k< 1, then $T(N) = (f(N))$

2. If $af(N/b) = K f(N)$ for some constant K > 1, then $T(N) = (N^{_{b}{a}})$

3. If $af(N/b) = f(N)$, then $T(N) = (f(N)_bN)$ ### 10. Backtracking

1. eight queens

2. The Turnpike Reconstruction Problem

Given N points on the x-axis with coordinates x1 < x2 < …< xN Assume that x1 = 0. There are N ( N – 1 ) / 2 distances between every pair of points.

Given N ( N – 1 ) / 2 distances. Reconstruct a point set from the distances.

1. $N(N–1)/2$ 得到点数量
2. $x_1$ = 0, $x_N$ = max_distance
3. 找下一个最大距离置于 $x_2$ 或 $x_{N-1}$ 并检查