Vincec's Dimension

# Algorithm Review Notes - Dynamic Programming

Word count: 836 / Reading time: 5 min
2018/11/25 Share # Divide and Conquer

T(n) = T(n/2) + O(1)

### MergeSort

T(n) = 2T(n/2) + O(n)

### Master Theorem

T(n) = a*T(n/b) + f(n), a >=1 , b >=1
c = ㏒b(a) [h]

#### Case 1:(Only leaves)

• f(n) = O(nc-ͼ), then T(n) = θ(n2) for ͼ>0

#### Case 2:(All nodes)

• f(n) = θ(nckn), k>=0, then T(n) θ(nck+1n)

#### Case 1:(Only internal nodes)

• f(n) = Ω(nc+ͼ), then T(n) = θ(f(n)) for ͼ>0

Note: k must >= 0 and f(n) must be positive.

# Dynamic Programming / Tabulation

### The Money Changing Problem

#### input:

• amount to change
• denominations: 1, 4 & 6

k is the first k denomiation.
x is the amount need to change.
dx is the lagest denomination in k.

#### Base:

• c[k, 0] = 0 #1row
• c[d1, x] = x #1col

#### Recurrence:

• c[k, x] = c[k-1, x] if x < dx
• c[k, x] = min(1 + c[k, x-dx], c[k-1, x])

Time: O(n, m)

### 0-1 Knapsack Problem / unbreakable

#### input:

w is the item weight, k is the first k denomiation, v is the item biggest value in k,

#### Base:

• opt[k, w] = 0, if k = 0 or w = 0

#### Recurrence:

• opt[k, w] = opt[k-1, w], can not take, if w < dw
• opt[k, w] = max(v + opt[k-1, w-dw], opt[k-1, w])

Time: O(n*W)

### Longest Common Subsequence / unbreakable

#### input:

i, j is number of order letter in two sequence

#### Base:

• LCS[i, 0] = LCS[0, j] = 0

#### Recurrence:

• LCS[i, j] = 1 + LCS[i-1, j-1], if S[i] = T[j]
• LCS[i, j] = max(LCS[i-1, j], LCS[i, j-1]), if S[i] != T[j]

Time: O(n*m)

Only half table is needed but that way we can not reconstruct the solution.

# Minimum Spanning Tree

### Kruskal’s Algorithm

1. Sort edge with weights - O(E×㏒E)
2. Choose all minimum weight edges
3. Grow the forest / repeat cycle detection for each edge - O(V)

Time: O(V×E + E×㏒E)

### Prim’s Algorithm

Build a tree one vertex at a time.

2. Expand vertex checking the minimum weight dege
3. Update distances from adjacent vertices
4. Grow the tree

#### Maintaining a array of vertices - Better for dense graph

findMin/deleteMin - O(V) V times
update - O(1)
E times
Total = O(V2 + E)

#### Maintaining a binary heap of vertices - Better for spare graph（Facebook）

deleteMin - O(㏒V) V times
update(decreaseKey) - O(㏒V)
E times
Total = O(V㏒V + E㏒V)

#### Maintaining a Fibonacci heap of vertices

deleteMin - O(㏒V) V times
update(decreaseKey) - O(1)
E times
Total = O(V㏒V + E)

# Shortest Path Problem - SSSP (Single Source Shortest Path)

### Dijkstra Greedy Algorithm

Not work when having negative cycle.

#### Time of Dijkstra same as Prim, but algorithm is different:

• Dijkstra for get minimum path cost from source to all other
• Prim for get the MST
• Dijkstra you can go from the selected node to any other with the minimum cost, you don’t get this with Prim’s source
• UCS is only stop at when reach the goal status, similar with the Dijkstra.

Maintaining a array of vertices: Total = O(V2 + E) -> O(V2)
Maintaining a binary heap(PQ - Priority Queues) of vertices: Total = O(V㏒V + E㏒V) -> O(E㏒V)
LAZIEST| Maintaining a Fibonacci heap: Total = O(V㏒V + E)

### SSSP in DAG - Directed Acyclic Graph

1. Topological -> linear
2. Check edge -> linear

# All-pairs Shortest Path Problem

### Bellman-Ford - Dynamic Way

• Case 1: Path uses at most k-1 edges: D[v, k] = D[v, k-1]
• Case 2: Path uses at most k edges: D[v, k] = min(D[w, k-1] + c(wv))

#### Detect Negative Cycle:

• Do not stop after V-1 iteration. If anything changes, there is negative.

Time: O(VE * V) / Time: O(VE) in SSSP

### Floyd-Warshall Algorithm - Dynamic Way

#### Detect Negative Cycle:

• Check diagonal in table, if have negative then have find the negative cycyle.

Time: O(V3)
Space: O(V2)

## Comparision in ALL-PAIRS SSP

Floyd-Warshall: O(V3)
Bellman-Ford: O(VE * V)
Dijikstra(Fibonacci): O(V(V㏒V + E))

• FW is same BF for running, but implement is easy
• Dijikstra is fater but not work in negative.

• slides

Author: VINCEC