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)

最大效率优先 ratio = 2


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)
  • Exclusive-Read Exclusive-Write (EREW)

  • Concurrent-Read Exclusive-Write (CREW)

  • Concurrent-ReadConcurrent-Write(CRCW)
    • 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

选取ends first 即可

  1. Huffman Codes

$ T = O(N ) $

建堆,在堆里取出频率最小的两个,合并成一个节点,然后放回堆里。

保证前缀码:只有叶子节点代表letter


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} $ 并检查