# Algorithm Note
---
[toc]

---
## Complexity
### some technique
$n^n>n!>c^n>n^c>n^2>n\log n>n>\sqrt{n}>\log n$
binary have $\log n$ usually
### big O
$f(n)=O(g(n))$
$f(n)\leq C\times g(n), \exists\ C>0\ \forall\ n\geq n_0$
### big Theta
$f(n)=\Theta(g(n))$
$C_1\times g(n)\leq f(n)\leq C_2*g(n), \exists\ C_1>0, C_2>0\ \forall\ n\geq n_0$
### big Omega
$f(n)=\Omega(g(n))$
$C\times g(n)\leq f(n), \exists\ C>0\ \forall\ n\geq n_0$
## Master Theorem
if the time like this
$T(n) = aT(\frac{n}{b}) + f(n)$
than
$T(n) = \Theta(n^{\log_ba})+\sum\limits_{i=1}^{\log_bn-1}a^if(\frac{n}{b^i})$
let $\sum\limits_{i=1}^{\log_bn-1}a^if(\frac{n}{b^i}) = pf(n)$
and you can observe that $pf(n)$ is near $O(f(n))$
### case 1
if $f(n) = O(n^{\log_ba-\epsilon})\ \exists\epsilon>0$
that mean $\frac{f(n)}{n^{\log_ba}}<1$
than $T(n) = \Theta(n^{\log_ba})$
### case 2
if $f(n) = \Theta(n^{\log_ba})$
that mean $\frac{f(n)}{n^{\log_ba}}$ is a constant
than $T(n) = \Theta(n^{\log_ba}\log n)$

### case 3
if $f(n) = \Omega(n^{\log_ba+\epsilon})\ \exists\ \epsilon>0$
**and** $af(\frac{n}{b})\leq cf(n),\exists\ c<1$
than $T(n) = \Theta(f(n))$
some prove
$\sum\limits_{i=1}^{\log_bn-1}a^if(\frac{n}{b^i}) \leq\sum\limits_{i=1}^{\log_bn-1}c^if(n)+O(1)\leq f(n)\sum\limits_{i=1}^{\infty}c^i+O(1)=O(f(n))$

## sorting

### Comparison sort
#### bubble sort

FUNCTION BUBBLE-SORT(array[n])
    for i from 1 to n
        for j from 1 to n-i-1
            if(array[j] > array[j+1])
                swap(array[j], array[j+1])
            

- stable
##### Complexity
- time
- best case $O(n^2)$
- worst case $O(n^2)$
- average case $O(n^2)$
- extra space
- O(1)

#### selection sort

FUNCTION SELETION-SORT(array[n])
    for i from 1 to n
        min = array[i]
        for j from i to n
            min = min(min, array[j])
        swap(min, array[i])
            
    

- stable
##### complexity
- time
- best case $O(n)$
- worst case $O(n^2)$
- average case $O(n^2)$
- extra space
- O(1)
#### insertion sort

FUNCTION INSERTION-SORT(array[n])
    for i from 1 to n
        now = i
        while now-1>=1 and array[now]<array[now-1]
            swap(array[now], array[now-1])
            now-=1
            
    

- stable
##### complexity
- time
- best case $O(n)$
- worst case $O(n^2)$
- average case $O(n^2)$
- extra space
- O(1)
#### quick sort

FUNCTION partition(array[n], L, R)
    pivot=array[R]
    i=L-1
    for j from L to R-1
        if array[j]<=pivot
            swap(A[++i], A[j])
    ++i
    swap(A[i], A[R])
    return i
FUNCTION QUICK-SORT(array[n], L, R)
    if L>=R or L<0
        return
    p=partition(array, L,R)
    QUICK-SORT(array, L, p-1)
    QUICK-SORT(array, p+1, R)

- unstable
##### complexity
- time
- best case $O(nlogn)$
- worst case $O(n^2)$
- average case $O(nlogn)$
- extra space
- O(1)
#### merge sort

FUNCTION MERGE-SORT(array[n], L, R) // 0~n-1
    if R-L<=1 // [L,R) have only 1 element
        return
    MERGE-SORT(array, L, MID(L,R))
    MERGE-SORT(array, MID(L,R), R)
    nowL = L
    nowR = MID(L, R)
    nowt = 0
    temp[R-L]
    while nowL<MID(L,R) and nowR < R
        if array[nowL]<=array[nowR]
            temp[nowt] = array[nowL]
            nowL += 1
        else
            temp[nowt] = array[nowR]
            nowR += 1 
        nowt += 1
    while nowL<MID(L, R)
        temp[nowt] = array[nowL]
        nowL += 1
        nowt += 1
    while nowR<R
        temp[nowt] = array[nowR]
        nowR += 1
        nowt += 1

- stable
##### complexity
- time
- best case $O(n\log n)$
- worst case $O(n\log n)$
- average case $O(n\log n)$
- extra space
- O(n)
##### inverse pair
add inverse pair count when `array[nowL]>array[nowR]`
#### heap sort
- just heap and pop all element

FUNCTION HEAPIFY(array[n])
    for i from 1 to n
        now = i
        while now>1
            if(array[now/2]<array[now])
                swap(array[now/2],array[now])
FUNCTION HEAP-SORT(array[n])
    HEAPIFY(array)
    for i from n to 1
        swap(array[1], array[i])
        now = i
        while now*2<i
            left = array[now*2]
            if now*2+1<i
                right = array[now*2+1]
            if(left>right) next = now*2
            else(left>right) next = now*2+1
            if(array[next]>array[now])
                swap(array[next], array[now])
                now = next
            else
                break

- unstable
##### complexity
- time
- best case $O(n\log n)$
- worst case $O(n\log n)$
- average case $O(n\log n)$
- extra space
- O(1)
### linear time sort
#### counting sort

FUNCTION COUNTING-SORT(array[n])
    C = unordered_map<int, int>
    for i from 1 to n
        C[array[i]]+=1
    prev = 0
    for i in C
        i.second += prev
        prev = i.second
    temp[n] = {0}
    for i from n to 1
        temp[C[array[i]]] = array[i]
        C[array[i]]-=1
    for i from 1 to n
        array[i] = temp[i]

- stable
##### complexity
- time
- best case $O(n+K)$
- worst case $O(n+K)$
- average case $O(n+K)$
- extra space
- O(K) (K is meaning max element of array)
#### radix sort

FUNCTION RADIX-SORT(array[n])
    d = digit of max number
    i = 10^d
    while i>=1
        bucket[10] = {vector}
        for j from 1 to n
            digit = (array[j]/i) % 10
            bucket[digit].append(array[j])
        c = 1
        for j from 0 to 9
            for k from 1 to bucket[j].size
                array[c] = bucket[j][k]
                c+=1
        i/=10;

- time
- best case $O(dn)$
- worst case $O(dn)$
- average case $O(dn)$
d is meaning digit of max number
- extra space
- O(d) (K is meaning max element of array)
## Devide and Conquer
### binary search
it can find 0 and 1 meeting point of a bool array like $[0,0,0,0,...,0,1,1,1,...,1]$

FUNCTION BINARY-SEARCH(bool-array[n])
    l = 1, r = n
    while(l<=r)
        m = MID(l, r)
        if(bool-array[m])
            r = mid-1
        else
            l = mid+1
    return l

complexity $O(logN)$
### Binary Exponentiation
find a^b in fast way

FUNCTION POWER(a, b)
    if b == 0
        return 1
    if b == 1
        return a
    p = POWER(a, b/2)
    p = p*p
    if(b is odd) p *=a
    return p

complexity $O(logN)$
### matrix multiplication
$\begin{bmatrix}
r s \\
t u\end{bmatrix}=\begin{bmatrix}
a b \\
c d\end{bmatrix}\times\begin{bmatrix}
e f \\
g h\end{bmatrix}$
$P_1=a\times(f-h), P_2=(a+b)\times h,P_3=(c+d)\times e, P_4=d\times(g-e)$
$P_5=(a+d)\times(e+h), P_6=(b-d)\times (g+h),P_7=(a-c)\times (e+f)$
$r=P_5+P_4-P_2+P_6$
$s=P_1+P_2$
$s=P_3+P_4$
$u=P_5+P_1-P_3-P_7$
there have 7 multiplication, 18 add/sub

$T(n) = 7T(\frac{n}{2})+18\times n^2$
=> by master theorem
- $n^{log_ba}=n^{log_27}$
- $18n^2=O(n^{log_27-log_2\frac{7}{4}})=O(n^2)$
- $T(n) = \Theta(n^{log_27})$
### Closest-Pair Problem
sort points by x,y
each time cut at middle
find two side Closest-Pair by recursive
find middle 7 points(distance in min(left,right)) and use brute-force

FUNCTION CLOSEST-PAIR(points[n], l, r)
    if(r-l+1 == 1){
        return 0
    }
    if(r-l+1 == 2){
        return dis(points[l], points[r])
    }
    m = mid(l, r) 
    left = CLOSEST-PAIR(points, l, mid)
    right = CLOSEST-PAIR(points, mid+1,r)
    d = min(left, right)
    strip = []
    for i from 1 to n
        if dis(points[i], points[m])<d
            strip.append(points[i])
    b = find closest pair by brute-force
    return min(b, d)

### convex hull
scan line

FUNCTION CONVEX-HULL(points[n])
    sort points by x,y
    h = [] //convex hull
    for i from 1 to n //lower hull
        if(h.size >= 2 and cross(h[-2], h[-1], points[i])<0)
            h.pop_back()
        h.push_back(points[i])
    h.pop_back()
    reverse points
    t = h.size
    for i from 1 to n //upper hull
        if(h.size -y >= 2 and cross(h[-2], h[-1], points[i])<0)
            h.pop_back()
        h.push_back(points[i])
    h.pop_back()
    return h

## Dynamic Programming
### rod cutting
$price(n) = max(price(n-l[i])+p[i])$
complexity:$O(np)$
### LCS
### memory $O(n^2)$
$lcs[i][j] = max(lcs[i-1][j], lcs[i][j-1])\ if\ s1_i\neq s2_j$
$lcs[i][j] = lcs[i-1][j-1]+1 \ if\ s1_i==s2_j$
complexity:$O(n^2)$
### Edit distance
$ed[i][j] = \min(ed[i-1][j-1]+(x_i\neq y_i), ed[i-1][j]+1, ed[i][j-1]+1)$
complexity:$O(N^2)$
### Knapsack

for j fomr 1 to n
    for w from W to 1
        dp[i] = max(dp[i-w[j]]+c[j])

complexity:$O(NK)$
### best binary search tree
$cost =\sum\limits_{i=1}^{n}p_i\times d(k_i)+\sum\limits_{i=0}^{n}q_i\times d(d_i)+\sum\limits_{i=1}^{n}p_i+\sum\limits_{i=1}^{n}q_i$
$dp[i][j]$ is optimal expected cost for $k[i,j]$
$w[i][j] = \sum\limits_{l=i}^{j}p_l+\sum\limits_{l=i-1}^{j}q_l=w[i][j-1]+p_j+q_j$
$root[i][j]$ is which is the root of $subtree[i,j]$
$dp[i][j] = min(dp[i][r-1]+dp[r+1][j]+w[i][j])$
Complexity: $O(n^3)$

## Greedy
when we at each previous statment, choose optimal solution
the general solution will be the optimal too
### Activity-Selection Problem
Given the time table of activities, select a **maximum-size**subset of mutually compatible activities
#### with dp method
$dp[i,j]=max(dp[i,k]+dp[k,j]+1)$
complexity: $O(n^3)$
#### greedy
each time choose the earliest finish time
consider nonempty sub-problem S, $a_m$ be an activity in S with earliest finish time
$a_m$ is included in some maximum-size subset of mutually compatible activities of S
##### prove
let A be an solution by S
$a_j$ be the activity in A with the earliest finish time
case 1: $a_j = a_m$: correct
case 2: $a_j \neq a_m$
- let $A' = A- a_j\cup a_m$
- A' is an optimal solution
- because activities in A' are disjoint
- |A| = |A'|
- A' is a maximum-size subset of S, it include $a_m$

why 0-1 kanpsack problen can't use greedy?

### Huffman codes

coding:mapping alphabet, sign to some binary code
e.g. ascii code(mapping char to a number), Morse Code(use binary sequence express number), prefix code
#### prefix code
- can always be represented by binary tree
- characters can onlt at leaf
#### Huffman
on binary tree, node value is meaning appear time and left is meaning 0, right is meaning 1
A = {f: 5, e:9, c:12, b:13, d: 16, a:45}
cost:sum of weighted depth of leaves
with minimum cost:optimal tree
##### prove
clame: x, y be the lowest frequencies
exist an optimal prefix code for x,y **have same length only diff on last bit**
let $T^*$ be an optimal tree.a,b be 2 sibling leaves->deepest in $T^*$

Create T' that a, b is lowest frequencies as x,y
$cost(T^*)\geq cost(T')$

- $cost(T^*)-cost(T')$
$cost(T^*)=C+fxdx+fydy+fada+fbdb$
$cost(T')=C+fxda+fydb+fadx+fbdy$
$cost(T^*)-cost(T')=fxdx-fxda+fydy-fydb+fada-fadx+fbdb-fbdy$
$=fx(dx-da)+fy(dy-db)+fa(da-dx)+fb(db-dy)$
$=(fx-fa)(dx-da)+(fy-fb)(dy-db)$
$\because fx<fa, fy<fb, da>dx, db>dy$
$fx-fa<0, dx-da<0 \rightarrow (fx-fa)(dx-da)>0$ $fy-fb<0, dy-db<0 \rightarrow (fy-fb)(dy-db)>0$
$\therefore cost(T^*)-cost(T')>=0$
cost of T' is better then $T^*$
$\rightarrow$if the deepest nodes is the lowest frequencies

### didnt get optimal solution
#### 0-1 knapsack
if we use greedy
"chooce best cp value"->value per pound is highest
then
pack size:50
item 1:60/10(cp:6)
item 2:100/20 (cp:5)
item 3:120/30 (cp:4)
choose:1->5 =>total value is 160
but answer is take 2 3, value is 220
**not optimal solution**
"take the largest value"
pack size:50
item 1: 20/20
item 2: 30/30
item 3: 40/50
choose: 3=>total value is 40
but answer is take 1 2, value is 50
**not optimal solution**
"take the lightest weights"
pack size:50
item 1: 1/1
item 2: 60/50
item 3: 1/30
choose: 1,3=>total value is 2
but answer is take 2, value is 60
Fractional knapsack: can take part of item ->can greedy
## Graph
### defination:
- G(V,E):we have a graph name G,it with vertices set V, edges set E on this graph
- |V|:number of vertices, |E|:number of edges
- Sparse graph:$|E|<<|V|^2$,Dense graph:$|E|\apporx|V|^2$
- degree of a vertex
- number of it neighbot
- at directed graph:
- in-degree:the edge point to this vertex
- out-degree:the edge start from this vertex
- degree of graph : max(deg(V))
- directed:the edge have directed(E(u,v) not meaning v can go to u)
### representations
#### adjacency list

| node | directed | undirected |
|:----:|:-------- |:---------- |
| 1 | ->2->3 | ->2->3 |
| 2 | ->4->5 | ->1->4->5 |
| 3 | ->4->6 | ->1->4->6 |
| 4 | | ->2->3->6 |
| 5 | | ->2 |
| 6 | ->4 | ->3->4 |

1->2->3
2->1->4->5
3->1->4->6
4->2->3->6
5->2
6->3->4
each node have a list to record which node it can rich
E(u,v):
for directed graph
- adjList[u] push back v
for undirected graph
- adjList[u] push back v
- **adjList[v] push back u**
#### adjacency matrix

make a $n^2$ bool matrix
$adjmat[u][v]$ is meaning E(u,v) is exist or not
if it is undirected
$adjmat[u][v] = adjmat[v][u]$

### traversal
all example is this graph
#### Breadth-first search(BFS)
use queue to record what we want to go next
start from s
**FIRST IN FIRST OUT**
init:queue(s)
bold:**now poping**, ~~strikethrough~~:visited *italics*:now pushing

| round | check | queue |
| ----- | ----- |:----------------------- |
| 1 | s | **s** *w* *r* |
| 2 | w | **w** r *t* *x* |
| 3 | r | **r** t x *v* |
| 4 | t | **t** x v *u* *x* |
| 5 | x | **x** v u x *t* *y* |
| 6 | v | **v** u x t y |
| 7 | u | **u** x t y *t* *x* *y* |
| 8 | ~~x~~ | **x** t y t x y |
| 9 | ~~t~~ | **t** y t x y |
| 10 | ~~y~~ |**y** t x y |
| 11 | ~~t~~ | **t** x y |
| 12 | ~~x~~ | **x** y |
| 13 | ~~y~~ | **y** |

- always go the shortest path that start from starting point
(weight of edge is 1)
#### Depth-first search(DFS)
use stack to record what we want to go next
**FIRST IN LAST OUT**
init:stack(s)

##### add time stamps
start time and end time
for edge u,v
- tree edge: v is not start
- back edge: v is start but not end
- finished/cross edge : v is end

### Directed acyclic graph (DAG)
a directed graph without cycle
- check it's DAG
- DFS has no back edge
#### Topological sort
given a dag
find a order that if E(u,v), than u appear before v
calculate start, end time
**sort by decreasing order of end time**
$O(V+E)$
##### correctness

node n{
    s=>start time
    f=>end time
}

if E(u,v) is an edge of g
u.f>v.f
- if this edge is
- tree edge:u.f>v.f
- if u.f<v.f ->that mean we pop v before u, but stack like (...,v,u...)
- **must pop u first**
- back edge:impossible(it's DAG)
- finished/cross edge edge:u.f>v.f
- if u.f<v.f ->that mean we pop v before u, but stack like (...,v,...,(end v)u...)

### Stronly connected components(SCC)
for a directed graph
G(V,E) have the sub graph G' that for all node pair(u, v) of G'
have at least 1 path from u to v
### Kosaraju's Algorithm
calculate the end time of all vertices by dfs
compute the $G^T$(transpose of G)=> $E(u,v)->E(v,u)$
dfs the $G^T$ with the order of decreasing end time
and we can find the components by dfs
$O(V+E)$
#### correctness
##### obs 1
if G have 2 SCC C(u,v), C'(u',v'), E(u,u')
if path v'->v exist then it contain path u->u'->v', v'->v->u
u, v' are reachable each other->C, C' is same SCC =>P(v'->v) not exist if C,C' are distinct SCC
##### obs2
if G have 2 SCC C(...,u), C'(v...), E(u,v)
for all vertex on C's end time > vertex on C'
- case 1
- start time of C<C'
- it start from C, when go to C', it can't go back to C(otherwise C,C' are in same SCC)
- so when C have vertex end, all vertex of C' end
- case 2
- start time of C>C'
- it start from C', it can't go to C(otherwise C,C' are in same SCC)
- so when C have vertex start, all vertex of C' end
- end time of C >= start time of C all > end time of C
##### obs3
if $G^T$ have (u,v)from C->C'
for all vertex on C's end time < vertex on C'
**same as obs2**

therefore
C' have no edge to other component in $G^T$
### Minimum Spanning Tree(MST)
get a tree T from undirected graph G
which connect all vertex and don't have cycle with minimum cost W
**GREEDY METHOD**
$O(ElogV)$
#### Kruskal
init all vertex u in $SET_u$
each time find the edge(u,v) with smallest weight(sort edges by weight)
$if\ FIND-SET(u)\neq FIND-SET(v)$
$MST = MST \cup {(u,v)}$
$UNION(u,v)$
**with disjoint set**
#### Prim
start from a point
eachtime get a vertex that can be reach and have minimum weight and didn't be connected
##### correctness
cut(S, V-S):a partition of V
cut respect a set A of edge:no edge in A cross cut
light edge:a edge cross cut with minimal weight
G(V,E):connected undirected weighted graph with vertices V, edges E
A:a subset of E included some MST for G
C(S,V-S) cut of G respects A
L(u,v): a light edge cross (S, V-S)

**L(u,v) is SAFE for A**
prove about it
let T be MST included A, assume T not contain L(u,v)
u-v and u->...->v(simple path in T) is a cycle
this cycle must contain (x,y not in A)
- if(x,y) in A, then u, v is not cross(S,V-S)
removing (x, y), make T to 2 components
creatt $T' = T-\{(x,y)\}\cup\{(u,v)\}$
$w(T') = w(T)-w(x,y)+w(u,v)\leq w(T)$(w(u,v)<w(x,y) or u,v is not light edge)
T' must be a minimum spanning tree and contains (u,v)

#### Borůvka
not on this exam
I'll update it after exam

### single source shortest path
start from s
#### relax
if now have edge(u, v) with weight w
now u's distance is du, v's is dv
du+w< dv
set dv=du+w
#### bellman-Ford
basic on floyd warshall but best
$O(|V||E|)$ ->worst $O(V^3)$
init dis(s,u) to inf, dis(s,s) = 0
repeat |V|-1 times
for each edge(u,v) with weight w do
relax(u,v,w)
=>if s->...->u->v is better than other path from s to v:update the distance
proove why repeat V-1 times
- assert that G contain no negtive cycle
- each node v has a shortest path from s to v=>at most V-1 edges
how to know G have negtive cycle or not
- if the |V|-th iteration relax the edge
- because if we do V-1 times it will get shortest path if it don't have negtive cycles
- but when we do the V-th times, and get better answer
prove
if G contain a negtive cycle $c = \{v_0,v_1,\dots ,v_k\}, v_k=v_0$
$\sum_{i=1}^{k}w(v_{i-1},v{i})<0$
if no update: $dis(v_i)\leq dis(v_{i-1})+w(v_{i-1}, v_i) \forall i$
$\sum_{i=1}^{k}dis(v_i)\leq\sum_{i=1}^{k}(dis(v_{i-1})+w(v_{i-1},v_i))$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \leq\sum_{i=1}^{k}dis(v_{i-1})+\sum_{i=1}^{k}w(v_{i-1},v_i)$
$0\leq\sum_{i=1}^{k}w(v_{i-1},v_i)$ contradicts!
##### if graph is a DAG
Topologically sort + DP
after Topologically sort, new order is in T(T[i] is meaning i-th vertex)

for u in T: // see vertex in order by Topologically sort
    for v in G[u]: // see all edge start from u
        relax(u,v,w)

complexity:$O(|V|+|E|)$
correctness
because we sort vettices in Topologically sort
relax edge on path $v_0,v_1...v_n$ in order$(v_0,v_1), (v_1,v_2),...,(v_{k-1}, v_k)$
that meaning $dis(v_i)=\delta(s,v_i)$ at termination for i from 0 to k
where $\delta(s,v_i)$ is shortest path from s to $v_i$
##### if all weight is non-negative
#### Dijkstra
like prim, is a greddy method
complexity is O(|V|log|V|)
eachtime get a vertex u with minimum path from s and now can reach
reach all vertex u's neighbor(all E(u, v) )
and relax all of them
pseudo code

Q = G.v
S = EMPTY SET
while(Q is not EMPTY SET):
    u = EXTRACT-MIN(Q) // get a vertex with minimum path
    S = UNION(S, {u})
    for all v in G[u]:
        RELAX(u,v,w)

correctness
in each iteration $dis(u) = \delta(s, u)$ for the vertex added to set S =>(dis(u) will not be relaxed after)
suppose $dis(u)\neq \delta(s,u)$ when u is added to the set S
shortest path P from s to u(s->...->x->y->...->u)
x:the vertex in S before y (s->...->x->y)
y:first vertex on P(s,u) not in S
$dis(y) = \delta(s,y)\leq \delta(s,u)\leq dis(u)$
but when we choose u, and y is not in S => y is not chosen => dis(u)<dis(y)
contradicts!
therefore not shortest path from s to u have vertex not in S when we choose u
### All pair shortest path
#### Naive
run bellman-ford each vertex
$O(|V|O(|V||E|))=O(|V|^2|E|)$
wtf is this ==;
#### DP
all sub-paths of a shortest path are shortest path
->$\delta(i,j)=\delta(i,k)+w_{kj}$ if have edge(k,j) on shortest path P(i,j)
$l_{i,j}^{m}$:minimum weight of any path from i to j, contain at most m edges
init:
$l_{i,i}^{0} = 0$
$l_{i,j}^{1} = w_{i,j}$
otherwise :$\infty$
$l_{i,j}^{m} = min_{1\leq k\leq n}(l_{i,k}^{m-1}+w_{k,j})$
$\delta(i, j) = l_{i,j}^{n-1}$
=>$\delta(i, j)=\delta(i,k)+w_{k,j}$
##### be better
find shortest path with $L^{m-1}, W$
$L^1=W$
$L^2=L^1W=W*W$
$L^4=W^4=W^2*W^2$
...
=>need only log n times
$O(n^3logn)$
#### Floyd-Warshall
DP method with better way
$\delta(i,j)=\delta(i,k)+ \underline{\delta{(k,j)}}$
=> $l_{i,j}^{m} = \min(l_{i,j}^{m-1}, l_{i,k}^{m-1}+l_{k,j}^{m-1})$
and $l_{i,j}^{0} = w_{ij}$
and $\delta(i,j) = l_{i,j}^{n}$
Complexity:$O(n^3$)
#### Johnson
reweighting
each vertex v have a weight h(v)
and make edge weight to new weight
$w'(u,v) = w(u, v)+h(u)-h(v)$
$w(p) = \delta(v_0,v_k) \iff w'(p) = \delta'(v_0, v_k)$
**w' is non neggative**
##### method
add a vertex 0 and add E(0,u) for all u in G with weight 0
and vertex 0's w is also 0
$h(v) = \delta(0,v)$ => use bellman-ford
compute all $w(u,v)$ to $w'(u,v) = w(u, v)+h(u)-h(v)$
$O(n^3)$
###### a little prove
$h(v) = \delta(0,v)$
$h(v) \leq h(u)+w(u,v)$
$0 \leq h(u)+w(u,v)-h(v) = w'(u,v)$
### Flow problem
#### defination
a flow from s to t on a directed graph with weight on edge $w(u, v)\geq 0$
flow f(s,t) is a weight subgraph og G=>satisfies the
capacity constraint and flow conservation
value of flow is sum of outgoing edge of s in f
capacity constraint:$0\leq f(u,v)\leq w(u,v) \forall u,v\in V$
flow conservation:$\sum_{v\in V}f(v,u) = \sum_{v\in V}f(u,v) \forall v\in V-\{s,t\}$
#### max flow
##### Ford–Fulkerson
each time we find a simple path from s to t
and on this path minimum weight is x
all edge on this path
w(u,v)-x
**add a new backward edge (v,u) with weight x on residual G**
##### correctness
f is a flow
f' is a flow of residual graph $G_f$
=>f+f' is a flow of G
f is not maximum for G iff still have path on $G_f$ from s to t
###### prove
if f is maximum for G but still have path on $G_f$ from s to t
=>we can find a flow g on $G_f$, and f+g is a flow of G and f+g>f (g is positive)=>f is not maximum

#### min cut


#### Bipartite match
each node can only match 1 node
solution:
add pseudo start point and end point
connect it to two side with weight=1

### Max flow in ADA...
##### Ford–Fulkerson
f:flow of G
###### residual graph R
- If $f(uv) > 0$, then let $R( f )$ have an edge vu with capacity f (uv).
- If $c(uv) > f (uv)$, then let $R( f )$ have an edge uv with capacity $c(uv)− f (uv)$.

f:st-flow of G
g:flow of R(f) iff f+g=flow of g
- observation
- if g(vu)>0 & $E(v,u) \notin G$, $(f+g)(uv)=f(uv)+g(uv)-g(vu)$
###### algorithm
- Let $f(uv) = 0$ for each edge uv of G. Repeat steps until R(f) does not contain an st-path.
- Obtain an st-path P of $R( f )$. Let q be the minimum capacity of the edges of P.
- Obtain an st-flow g of $R( f )$ by letting $g(uv) = q$ for each edge uv of P and $g(uv) = 0$ for all other edges uv of G.
- Let $f = f + g$.
###### correctness
- P:st-path of $R( f )$,
- st-flow g of R( f ) with positive value.
- By observing residual graph, h = f + g is an st-flow of G whose value is strictly larger than that of f . Thus, f is not a maximum st-flow of G.
- If f is not a maximum a maximum st-flow of G, then there is an st-flow h of G whose value is strictly larger than that of f .
- Let g = h − f
- Verify that g is an st-flow of R( f )
- Thus, there is an st-path of R( f )
- when algorithm stop, f is max flow of s-t
**observation**
- Let P be an st-path whose number edges is minimized in the R( f ).
- Let g be the flow for R( f ) corresponding to P.
- For each vertex v of G, we have $d_R( f )(s, v) ≤ d_R( f +g)(s, v)$, where $d_H (s, v)$ for a residual graph H of G denotes the distance of s to v in the unweighted version of H.

- unweighted version of H:edge length=1 (not care capacity).
- P is unweighted version of R( f )'s shortest st-path.

#### complexity
if capacity is C:O(mC)
\* **is exponential-time**
if C is not limited
store space is O(mlogC)
\* $O(mC) \neq O(m\log C)^{O(1)} \rightarrow not polynomial$
##### make C to mn
- makes sure that the st-path P in $R( f )$ having a minimum number of edges
#### some about algorithm
- complexity is relative to problem size
if the problem size is $\Theta(f(n))$
- linear-time algorithm:$O(f(n))$
- quadratic-time algorithm:$O(f(n)^2)$
- polynomial-time algorithm:$O(f(n))^{O(1)} = f(n)^{O(1)}$
- exponential-time algorithm:$O(1)^{f(n)}$ or more

## NP Problem
### Reducibility

if $P_1$ can deduct to $P_2$
then exist a function that
$f({S_1}_i)={S_2}_i$ where S is meaning answer
like this, each 1 is mapping to 1

P:problem can slove in polynomial time
NP:problem will slove with non-polynomial time
can verify answer in polynomial time
NP-Complete is NP and NP-Hard problem
NP-Hard:**all** NP problem polynomial time reducible to this problem

### Hamiltonian Path->long path
Hamiltonian Path:each node should pass once
if longest-path(G, x, y, |V|-1) yes->have hamiltonian Path
otherwise no
### Hamiltonian Cycle->Hamiltonian Path
Hamiltonian-cycle:Hamiltonian Path and back to start point
if it have a hamiltonial path start at u, end at v, and there exist E(u,v)->have Hamiltonian-cycle
### TSP
Hamiltonian-cycle with minimum cost
### Hamiltonian Cycle->TSP
if each cost of $E[u,v]=0$, other edge on complete graph is 1
if exist TSP with cost 0 => have Hamiltonian-cycle
### SAT problem
first known NP-Complete problem
input a bool formula
if it have a answer let this formula been true -> yes
### Further reading
[2023 ADA midtern2](https://hackmd.io/@IBuVwIraTIWJeB88sQHXpw/H1VaNbcQ6)
[2023 ADA final](https://hackmd.io/@ntnuhiphop-panda/ry6weQkD6)