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.

  1. Start with a arbitrary vertex
  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))
1
2
3
4
for k = 1 ...V -1 do //detect negative change to 1 to V
for each v in V
for each edge(w, v) in E
D[v, k] = min(D[v, k-1], c(w,v) + D[w, k-1])

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

1
2
3
4
5
6
for k = 1 ...V do
for i = 1 ... V do
for j = 1 ... V do
D[i, j, j] = min(D[i, j, k-1], D[i, k, k-1], D[k, j, k-1])
//p[i, j] for extract the shortest path, p[i,j] = 0, its the edge(i, j), on diagonal
//check negative cycle.

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.

Reference

  • slides
CATALOG
  1. 1. Divide and Conquer
    1. 1.0.1. Binary Search
    2. 1.0.2. MergeSort
    3. 1.0.3. Master Theorem
      1. 1.0.3.1. Case 1:(Only leaves)
      2. 1.0.3.2. Case 2:(All nodes)
      3. 1.0.3.3. Case 1:(Only internal nodes)
  • 2. Dynamic Programming / Tabulation
    1. 2.0.1. The Money Changing Problem
      1. 2.0.1.1. input:
      2. 2.0.1.2. Base:
      3. 2.0.1.3. Recurrence:
    2. 2.0.2. 0-1 Knapsack Problem / unbreakable
      1. 2.0.2.1. input:
      2. 2.0.2.2. Base:
      3. 2.0.2.3. Recurrence:
    3. 2.0.3. Longest Common Subsequence / unbreakable
      1. 2.0.3.1. input:
      2. 2.0.3.2. Base:
      3. 2.0.3.3. Recurrence:
  • 3. Minimum Spanning Tree
    1. 3.0.1. Kruskal’s Algorithm
    2. 3.0.2. Prim’s Algorithm
      1. 3.0.2.1. Maintaining a array of vertices - Better for dense graph
      2. 3.0.2.2. Maintaining a binary heap of vertices - Better for spare graph(Facebook)
      3. 3.0.2.3. Maintaining a Fibonacci heap of vertices
  • 4. Shortest Path Problem - SSSP (Single Source Shortest Path)
    1. 4.0.1. Dijkstra Greedy Algorithm
      1. 4.0.1.1. Time of Dijkstra same as Prim, but algorithm is different:
    2. 4.0.2. SSSP in DAG - Directed Acyclic Graph
  • 5. All-pairs Shortest Path Problem
    1. 5.0.1. Bellman-Ford - Dynamic Way
      1. 5.0.1.1. Detect Negative Cycle:
    2. 5.0.2. Floyd-Warshall Algorithm - Dynamic Way
      1. 5.0.2.1. Detect Negative Cycle:
  • 5.1. Comparision in ALL-PAIRS SSP
  • 6. Reference