Formula Sheets: Dynamic Programming | Algorithms - Computer Science Engineering (CSE) PDF Download

 Page 1


Dynamic Programming
General Concepts
Optimal Substructure
• Optimal solution to problem con tains optimal solutions to subproblems.
Ov erlapping Subproblems
• Subproblems are solv ed m ultiple times in recursiv e approac h, stored in table for e?iciency .
Key Algorithms
Longest Common Subsequence (LCS)
• Recurrence: LCS(i,j) =
?
?
?
?
?
0 if i = 0 or j = 0
LCS(i-1,j -1)+1 if x
i
=y
j
max(LCS(i-1,j),LCS(i,j -1)) otherwise
.
• Time C omplexit y: O(mn) , where m,n are lengths of sequences.
• Space Com plexit y: O(mn) , optimizable to O(min(m,n)) .
Matrix Chain Mul tiplication
• Recurrence : MCM(i,j) = min
j-1
k=i
{MCM(i,k)+MCM(k+1,j)+p
i-1
p
k
p
j
} , where p
i
is dimension
of matrix i .
• Time Complexit y: O(n
3
) , where n is n um b er of matrices.
• Space Complexit y: O(n
2
) for DP table.
0-1 Knapsac k Problem
• Recurrence: K(n,W) = max{K(n-1,W),v
n
+K(n-1,W -w
n
)} , where v
n
is v alue, w
n
is w eigh t,
W is capacit y .
• Time Complexit y: O(nW) .
• Space Complexit y: O(nW) , optimizable t o O(W) .
Subset Sum Problem
• Recurrence: SS(n,s) =SS(n-1,s) or SS(n-1,s-a
n
) , where a
n
is elemen t, s is target sum.
• Time Complexit y: O(n·s) .
• Space Complexit y: O(n·s) , optimizable to O(s) .
Min Cost P ath
• Recurrence: MCP(i,j) = min{MCP(i-1,j),MCP(i,j -1),MCP(i-1,j -1)}+cost(i,j) .
• Time Complexit y: O(mn) , where m,n are grid dimensions.
• Space Complexit y: O(mn) .
T ra v eling Salesman Problem (TSP)
• Recurrence: TSP(S,v) = min
u?S
{c(v,u) +TSP(S \ {u},u)} , where S is set of v ertices, c(v,u) is
cost.
• Time Complexit y: O(n
2
·2
n
) .
• Space Complexit y: O(n·2
n
) .
Flo yd-W arshall Algorithm (All P airs Shortest P ath)
• Recurrence: d
(k)
ij
= min{d
(k-1)
ij
,d
(k-1)
ik
+d
(k-1)
kj
} , where k is in termediate v ertex.
• Time Complexit y: O(V
3
) , where V is n um b er of v ertices.
1
Page 2


Dynamic Programming
General Concepts
Optimal Substructure
• Optimal solution to problem con tains optimal solutions to subproblems.
Ov erlapping Subproblems
• Subproblems are solv ed m ultiple times in recursiv e approac h, stored in table for e?iciency .
Key Algorithms
Longest Common Subsequence (LCS)
• Recurrence: LCS(i,j) =
?
?
?
?
?
0 if i = 0 or j = 0
LCS(i-1,j -1)+1 if x
i
=y
j
max(LCS(i-1,j),LCS(i,j -1)) otherwise
.
• Time C omplexit y: O(mn) , where m,n are lengths of sequences.
• Space Com plexit y: O(mn) , optimizable to O(min(m,n)) .
Matrix Chain Mul tiplication
• Recurrence : MCM(i,j) = min
j-1
k=i
{MCM(i,k)+MCM(k+1,j)+p
i-1
p
k
p
j
} , where p
i
is dimension
of matrix i .
• Time Complexit y: O(n
3
) , where n is n um b er of matrices.
• Space Complexit y: O(n
2
) for DP table.
0-1 Knapsac k Problem
• Recurrence: K(n,W) = max{K(n-1,W),v
n
+K(n-1,W -w
n
)} , where v
n
is v alue, w
n
is w eigh t,
W is capacit y .
• Time Complexit y: O(nW) .
• Space Complexit y: O(nW) , optimizable t o O(W) .
Subset Sum Problem
• Recurrence: SS(n,s) =SS(n-1,s) or SS(n-1,s-a
n
) , where a
n
is elemen t, s is target sum.
• Time Complexit y: O(n·s) .
• Space Complexit y: O(n·s) , optimizable to O(s) .
Min Cost P ath
• Recurrence: MCP(i,j) = min{MCP(i-1,j),MCP(i,j -1),MCP(i-1,j -1)}+cost(i,j) .
• Time Complexit y: O(mn) , where m,n are grid dimensions.
• Space Complexit y: O(mn) .
T ra v eling Salesman Problem (TSP)
• Recurrence: TSP(S,v) = min
u?S
{c(v,u) +TSP(S \ {u},u)} , where S is set of v ertices, c(v,u) is
cost.
• Time Complexit y: O(n
2
·2
n
) .
• Space Complexit y: O(n·2
n
) .
Flo yd-W arshall Algorithm (All P airs Shortest P ath)
• Recurrence: d
(k)
ij
= min{d
(k-1)
ij
,d
(k-1)
ik
+d
(k-1)
kj
} , where k is in termediate v ertex.
• Time Complexit y: O(V
3
) , where V is n um b er of v ertices.
1
• Space Complexit y: O(V
2
) .
Bellman-F ord Algorithm
• R ecurrence: d
i
(v) = min{d
i-1
(v),min
u
{d
i-1
(u)+w(u,v)}} , for i = 1 to V -1 .
• T ime Complexit y: O(V ·E) .
• Space Complexit y: O(V) .
Optimal Binary Searc h T ree
• Rec urrence: C(i,j) = min
j
r=i
{C(i,r-1)+C(r+1,j)+
?
j
k=i
p
k
} , where p
k
is probabilit y of k ey k .
• Time C omplexit y: O(n
3
) .
• Space Comple xit y: O(n
2
) .
Multistage Graph
• Recurrence: C(v,s) = min{c(v,u)+C(u,s)} , where v is v ertex, s is stage.
• Time Complexit y: O(V +E) , where V is v ertices, E is edges.
• Space Complexit y: O(V) .
2