Cormen Algo-lec15
-
Upload
geniusamit -
Category
Documents
-
view
224 -
download
0
Transcript of Cormen Algo-lec15
-
8/14/2019 Cormen Algo-lec15
1/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.1
Introduction to Algorithms6.046J/18.401J
L ECTURE 15Dynamic Programming Longest common
subsequence Optimal substructure Overlapping subproblems
Prof. Charles E. Leiserson
-
8/14/2019 Cormen Algo-lec15
2/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.2
Dynamic programming
Design technique, like divide-and-conquer.
Example: Longest Common Subsequence (LCS) Given two sequences x[1 . . m] and y[1 . . n], finda longest subsequence common to them both.
-
8/14/2019 Cormen Algo-lec15
3/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.3
Dynamic programming
Design technique, like divide-and-conquer.
Example: Longest Common Subsequence (LCS) Given two sequences x[1 . . m] and y[1 . . n], finda longest subsequence common to them both.
a not the
-
8/14/2019 Cormen Algo-lec15
4/31
-
8/14/2019 Cormen Algo-lec15
5/31 November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.5
Dynamic programming
Design technique, like divide-and-conquer.
Example: Longest Common Subsequence (LCS) Given two sequences x[1 . . m] and y[1 . . n], finda longest subsequence common to them both.
x: A B C B D A B
y: B D C A B A
a not the
BCBA =LCS( x, y)
functional notation, but not a function
-
8/14/2019 Cormen Algo-lec15
6/31 November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.6
Brute-force LCS algorithm
Check every subsequence of x[1 . . m] to seeif it is also a subsequence of y[1 . . n].
-
8/14/2019 Cormen Algo-lec15
7/31 November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.7
Brute-force LCS algorithm
Check every subsequence of x[1 . . m] to seeif it is also a subsequence of y[1 . . n].
Analysis
Checking = O(n) time per subsequence. 2m subsequences of x (each bit-vector of length m determines a distinct subsequenceof x).
Worst-case running time = O(n2m)
= exponential time.
-
8/14/2019 Cormen Algo-lec15
8/31 November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.8
Towards a better algorithm
Simplification:1. Look at the length of a longest-common
subsequence.2. Extend the algorithm to find the LCS itself.
-
8/14/2019 Cormen Algo-lec15
9/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.9
Towards a better algorithm
Simplification:
1. Look at the length of a longest-commonsubsequence.2. Extend the algorithm to find the LCS itself.
Notation: Denote the length of a sequence s by | s |.
-
8/14/2019 Cormen Algo-lec15
10/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.10
Towards a better algorithm
Simplification:1. Look at the length of a longest-common
subsequence.2. Extend the algorithm to find the LCS itself.
Notation: Denote the length of a sequence s by | s |.
Strategy: Consider prefixes of x and y. Define c[i, j] = | LCS( x[1 . . i], y[1 . . j]) |.
Then, c[m, n] = | LCS( x, y) |.
-
8/14/2019 Cormen Algo-lec15
11/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.11
Recursive formulation
Theorem.
c[i, j] =c[i 1, j 1] + 1 if x[i] = y[ j],max {c[i 1, j], c[i, j 1] } otherwise.
-
8/14/2019 Cormen Algo-lec15
12/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.12
Recursive formulation
Theorem.
c[i, j] =c[i 1, j 1] + 1 if x[i] = y[ j],max {c[i 1, j], c[i, j 1] } otherwise.
Proof. Case x[i] = y[ j]:
L1 2 i m
L1 2 j n
x:
y:
=
-
8/14/2019 Cormen Algo-lec15
13/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.13
Recursive formulation
Theorem.
c[i, j] =c[i 1, j 1] + 1 if x[i] = y[ j],
max {c[i 1, j], c[i, j 1] } otherwise. Proof. Case x[i] = y[ j]:
L1 2 i m
L1 2 j n
x:
y:
=
Let z [1 . . k ] = LCS( x[1 . . i], y[1 . . j]), where c[i, j]= k . Then, z [k ] = x[i], or else z could be extended.Thus, z [1 . . k 1] is CS of x[1 . . i 1] and y[1 . . j 1] .
-
8/14/2019 Cormen Algo-lec15
14/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.14
Proof (continued)
Claim: z [1 . . k 1] = LCS( x[1 . . i 1], y[1 . . j 1]) .Suppose w is a longer CS of x[1 . . i 1] and
y[1 . . j 1] , that is, | w | > k 1 . Then, cut and paste : w || z [k ] (w concatenated with z [k ]) is a
common subsequence of x[1 . . i] and y[1 . . j]with | w || z [k ] | > k . Contradiction, proving theclaim.
-
8/14/2019 Cormen Algo-lec15
15/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.15
Proof (continued)
Claim: z [1 . . k 1] = LCS( x[1 . . i 1], y[1 . . j 1]) .Suppose w is a longer CS of x[1 . . i 1] and
y[1 . . j 1] , that is, | w | > k 1 . Then, cut and paste : w || z [k ] (w concatenated with z [k ]) is acommon subsequence of x[1 . . i] and y[1 . . j]with | w || z [k ] | > k . Contradiction, proving theclaim.
Thus, c[i 1, j 1] = k 1 , which implies that c[i, j]= c[i 1, j 1] + 1 .Other cases are similar.
-
8/14/2019 Cormen Algo-lec15
16/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.16
Dynamic-programming
hallmark #1
Optimal substructure An optimal solution to a problem(instance) contains optimal
solutions to subproblems.
-
8/14/2019 Cormen Algo-lec15
17/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.17
Dynamic-programming
hallmark #1
Optimal substructure An optimal solution to a problem(instance) contains optimal
solutions to subproblems.
If z = LCS( x, y), then any prefix of z isan LCS of a prefix of x and a prefix of y.
-
8/14/2019 Cormen Algo-lec15
18/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.18
Recursive algorithm for LCS
LCS ( x, y, i, j)
if x[i] = y[ j]then c[i, j] LCS ( x, y, i 1, j 1) + 1else c[i, j] max { LCS ( x, y, i 1, j),
LCS ( x, y, i, j 1) }
-
8/14/2019 Cormen Algo-lec15
19/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.19
Recursive algorithm for LCS
LCS ( x, y, i, j)
if x[i] = y[ j]then c[i, j] LCS ( x, y, i 1, j 1) + 1else c[i, j] max { LCS ( x, y, i 1, j),
LCS ( x, y, i, j 1) }Worst-case: x[i] y[ j], in which case thealgorithm evaluates two subproblems, eachwith only one parameter decremented.
-
8/14/2019 Cormen Algo-lec15
20/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.20
Recursion tree
m = 3, n = 4: 3,43,4
2,42,4
1,41,4
3,33,3
3,23,2
2,32,3
1,31,3 2,22,2
2,32,3
1,31,3 2,22,2
-
8/14/2019 Cormen Algo-lec15
21/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.21
Recursion tree
m = 3, n = 4: 3,43,4
2,42,4
1,41,4
3,33,3
3,23,2
2,32,3
1,31,3 2,22,2
m+n2,3
2,3
1,31,3 2,22,2
Height = m + n work potentially exponential.
-
8/14/2019 Cormen Algo-lec15
22/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.22
Recursion tree
same subproblem
, but were solving subproblems already solved!
m = 3, n = 4: 3,43,4
2,42,4
1,41,4
3,33,3
3,23,2
2,32,3
1,31,3 2,22,2
Height = m + n work potentially exponential.
2,32,3
1,31,3 2,22,2
m+n
D i i
-
8/14/2019 Cormen Algo-lec15
23/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.23
Dynamic-programminghallmark #2
Overlapping subproblems A recursive solution contains a
small number of distinct
subproblems repeated many times.
D i i
-
8/14/2019 Cormen Algo-lec15
24/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.24
Dynamic-programminghallmark #2
Overlapping subproblems A recursive solution contains a
small number of distinct
subproblems repeated many times.
The number of distinct LCS subproblems for two strings of lengths m and n is only mn.
-
8/14/2019 Cormen Algo-lec15
25/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.25
Memoization algorithm
Memoization: After computing a solution to asubproblem, store it in a table. Subsequent calls
check the table to avoid redoing work.
-
8/14/2019 Cormen Algo-lec15
26/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.26
Memoization algorithm
Memoization: After computing a solution to asubproblem, store it in a table. Subsequent calls
check the table to avoid redoing work.LCS ( x, y, i, j)
if c[i, j] = NILthen if x[i] = y[ j]
then c[i, j] LCS ( x, y, i 1, j 1) + 1
else c[i, j]
max {LCS ( x, y, i 1, j),LCS ( x, y, i, j 1) }
sameasbefore
-
8/14/2019 Cormen Algo-lec15
27/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.27
Memoization algorithm Memoization: After computing a solution to asubproblem, store it in a table. Subsequent calls
check the table to avoid redoing work.
Time = (mn) = constant work per table entry.
Space = (mn).
LCS ( x, y, i, j)if c[i, j] = NIL
then if x[i] = y[ j]then c[i, j] LCS ( x, y, i 1, j 1) + 1else c[i, j] max {LCS ( x, y, i 1, j),
LCS ( x, y, i, j 1) }
sameas
before
Dynamic programming
-
8/14/2019 Cormen Algo-lec15
28/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.28
Dynamic-programmingalgorithm
IDEA :Compute thetable bottom-up. 0
000
00
00
00
00 00 11 11 1100
00
00
11 11 11
00
00
11
11
11
22
22
2D 2
00 00 11 22 22 22 22 2C 2
00
11
11
22
22
22
33A
33
00 11 22 22 33 33 33 44
00 11 22 22 33 33
AA B C B D B
4
B
B
4 44A
Dynamic programming
-
8/14/2019 Cormen Algo-lec15
29/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.29
Dynamic-programmingalgorithm
IDEA :Compute thetable bottom-up. 0
000
00
00
00
00 00 11 11 1100
00
00
11 11 11
00
00
11
11
11
22
22
2D 2
00 00 11 22 22 22 22 2C 2
00
11
11
22
22
22
33A
33
00 11 22 22 33 33 33 44
00 11 22 22 33 33
AA B C B D B
4
BTime = (mn).
B
4 44A
Dynamic programming
-
8/14/2019 Cormen Algo-lec15
30/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.30
00
00
00
00
00
00
00
00
00 00 11 11 11 11 11 11
00
00
11
11
11
22
22D
22
00 00 11 22 22 22 22C 22
00
11
11
22
22
22
33A
33
00 11 22 22 33 33 33B 44
00 11 22 22 33 33
A
Dynamic-programmingalgorithm
IDEA :Compute thetable bottom-up.
A B C B D B
B
A 44 44
Time = (mn).ReconstructLCS by tracing
backwards.
0A
4
0B
B
1
C
C
2
B
B
3
A
A
D
1
A
2
D
3
B
4
Dynamic programming
-
8/14/2019 Cormen Algo-lec15
31/31
November 7, 2005 Copyright 2001-5 by Erik D. Demaine and Charles E. Leiserson L15.31
00
00
00
00
00
00
00
00
00 00 11 11 11 11 11 11
00
00
11
11
11
22
22D
22
00 00 11 22 22 22 22C 22
00
11
11
22
22
22
33A
33
00 11 22 22 33 33 33B 44
00 11 22 22 33 33
A
Dynamic-programmingalgorithm
IDEA :Compute thetable bottom-up.
A B C B D B
B
A 44 44
Time = (mn).ReconstructLCS by tracing
backwards.
0A
4
0B
B
1
C
C
2
B
B
3
A
A
D
1
A
2
D
3
B
4
Space = (mn).Exercise:O(min{ m, n}).