Dynamic Programming From CS 6515(Fibonacci, LIS, LCS))
leoyang0406
4 views
67 slides
Mar 11, 2025
Slide 1 of 67
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
About This Presentation
Course slides from Graduate class
Slide Content
CS6515: Lecture 1
Dynamic Programming
(Fibonacci, LIS, LCS)
Dr. GerandyBrito
Dr. Mengmeng (Helen) Liu
Email: [email protected]
Phone: (+86)-15117982925
Office: Room 418
Dynamic Programming
(Fibonacci, LIS, LCS)
Dr. GerandyBrito
Dr. Mengmeng (Helen) Liu
Email: [email protected]
Phone: (+86)-15117982925
Office: Room 418
•Data analysis
•Clustering
•Social Network Analysis
•Centrality Measures, Recommendation, Information Diffusion
•Databases
•Queries
•Circuit Design
•Every electronic device you use
•Scheduling & Resource Allocation
•Timetabling (your classes and exams)
•Transportation
•Routing, network design
•Computational biology
•Genome Sequencing, Protein Folding
•Computational Physics & Chemistry
Wide Range of Applications of Algorithm
•Clustering
•Social Network Analysis
•Centrality Measures, Recommendation, Information Diffusion
•Databases
•Queries
•Circuit Design
•Every electronic device you use
•Scheduling & Resource Allocation
•Timetabling (your classes and exams)
•Transportation
•Routing, network design
•Computational biology
•Genome Sequencing, Protein Folding
•Computational Physics & Chemistry
Wide Range of Applications of Algorithm
•Dynamic Programming
•Divide and Conquer
•Randomized Algorithms
•Graph Algorithms
•Max-Flow
•Linear Programming
•NP-Completeness
Algorithms Covered in CS6500
•Divide and Conquer
•Randomized Algorithms
•Graph Algorithms
•Max-Flow
•Linear Programming
•NP-Completeness
Algorithms Covered in CS6500
Algorithms
Proof of Correctness: (Review)
On every valid input, the algorithm produces the output
that satisfies the required input/output relationshi
Definition:
a sequence of computationalstepsthat transformthe
input into a desired output.
Analysis of Time and Space: (Review)
Given the ‘size’ of the input, how many computational
steps does the algorithm take?
Proof of Correctness: (Review)
On every valid input, the algorithm produces the output
that satisfies the required input/output relationshi
Definition:
a sequence of computationalstepsthat transformthe
input into a desired output.
Analysis of Time and Space: (Review)
Given the ‘size’ of the input, how many computational
steps does the algorithm take?
•Model of computation: Random-access Machine (RAM)
•Instructions are executed one after the other (non concurrency)
•Each “simple” operation takes 1 step: (+, -, =, if, call, memory
access)
•Loops and subroutine calls are not simple operations. They depend
upon the size of the data and the contents of a subroutine.
•“Sort” is not a single step operation
•Input size: depends on the problem being studied
•E.g. Number of items in the input
•E.g. number of nodes and number of edges in a graph
•Running time
•Number of steps taken by the algorithm, given input size
Running Time
•Instructions are executed one after the other (non concurrency)
•Each “simple” operation takes 1 step: (+, -, =, if, call, memory
access)
•Loops and subroutine calls are not simple operations. They depend
upon the size of the data and the contents of a subroutine.
•“Sort” is not a single step operation
•Input size: depends on the problem being studied
•E.g. Number of items in the input
•E.g. number of nodes and number of edges in a graph
•Running time
•Number of steps taken by the algorithm, given input size
Running Time
•Worst-Case: the maximumnumber of steps taken on
any instance of size n
•Best-Case: the minimumnumber of steps taken on any
instance of size n.
•Average-Case: the averagenumber of steps taken on
any instance of size n.
Running Time
•Need an
understanding of the
distributionof
possible inputs
any instance of size n
•Best-Case: the minimumnumber of steps taken on any
instance of size n.
•Average-Case: the averagenumber of steps taken on
any instance of size n.
Running Time
•Need an
understanding of the
distributionof
possible inputs
•Best, worst, and average are difficult to deal with
precisely because the details are very complicated
Exact Analysis is Hard
•It easier to talk about upperand lowerboundsof the
function
•Asymptotic notation (??????,??????,??????) are the way we practically
deal with analysis of time complexity.
precisely because the details are very complicated
Exact Analysis is Hard
•It easier to talk about upperand lowerboundsof the
function
•Asymptotic notation (??????,??????,??????) are the way we practically
deal with analysis of time complexity.
•Proofs by Counterexample
Review of Proofs
•Proofs by Contradiction
•E.g., ‘All primes are odd’ is False
→Exhibit the even prime 2
•Q: Can you give other examples ?
•Assume the opposite of hypothesis, show thesis cannot follow
•e.g., There are infinite number of primes
→Assume there are a finite number of primes: �
1,�
2,...,�
�
→Consider the number p=�
1∗�
2∗…∗�
�+1
→p is composite: p is not divisible by any of our primes, hence it
must be prime .
→p is larger than any of the primes in our finite set →contradiction
Review of Proofs
•Proofs by Contradiction
•E.g., ‘All primes are odd’ is False
→Exhibit the even prime 2
•Q: Can you give other examples ?
•Assume the opposite of hypothesis, show thesis cannot follow
•e.g., There are infinite number of primes
→Assume there are a finite number of primes: �
1,�
2,...,�
�
→Consider the number p=�
1∗�
2∗…∗�
�+1
→p is composite: p is not divisible by any of our primes, hence it
must be prime .
→p is larger than any of the primes in our finite set →contradiction
Review of Proofs
•InductiveProofs
•e.g., Proof: for any positive n, show that: 1+2+3+…+�=
��+1
2
•Step 1:�=1→1=1∗2/2
1)A Statementinvolving a natural number n, andwe will show that
it holds for all values of n
2)Basis: show it holds for small inputs, usually for n=0 or n=1
3)Induction Hypothesis: assume it holds for n (or all values <= n)
4)Inductive Step: show it holds for n+1
•Step 2: Assume it holds for n
•Step 3: show it holds for n+1:
1+2+3+…+�+�+1=
��+1
2
+�+1=
�+1�+2
2
•InductiveProofs
•e.g., Proof: for any positive n, show that: 1+2+3+…+�=
��+1
2
•Step 1:�=1→1=1∗2/2
1)A Statementinvolving a natural number n, andwe will show that
it holds for all values of n
2)Basis: show it holds for small inputs, usually for n=0 or n=1
3)Induction Hypothesis: assume it holds for n (or all values <= n)
4)Inductive Step: show it holds for n+1
•Step 2: Assume it holds for n
•Step 3: show it holds for n+1:
1+2+3+…+�+�+1=
��+1
2
+�+1=
�+1�+2
2
Review of Proofs
•StructuralInduction: proofstatements about recursively
defined structures, e.g. lists and trees.
•e.g.Binary tree is defined as a node with no children (a leaf), or as a node with two
children, both of which are binary trees.
•The root of the tree has two binary tree children T1 and T2.
Proof: Any binary tree with �leaves, has �−1non-leaf nodes.
•Step 1: �=1, a tree consisting of a leaf has �−1=0non-leaf nodes.
•Step 2: Assume it holds for all trees with ≤�leaves.
•Step 3: Consider a tree T with (�+1) leaves.
•Both T1 and T2 consist of at least one node, hence both have leaves<�−1
•leaf(T) = leaf(T1) + leaf(T2)
•Inter(T) = inter(T1) + inter(T2) + 1
= (leaf(T1) –1) + (leaf(T2) –1) + 1 = leaf(T1) + leaf(T2) –1 = leaf(T) -1
•StructuralInduction: proofstatements about recursively
defined structures, e.g. lists and trees.
•e.g.Binary tree is defined as a node with no children (a leaf), or as a node with two
children, both of which are binary trees.
•The root of the tree has two binary tree children T1 and T2.
Proof: Any binary tree with �leaves, has �−1non-leaf nodes.
•Step 1: �=1, a tree consisting of a leaf has �−1=0non-leaf nodes.
•Step 2: Assume it holds for all trees with ≤�leaves.
•Step 3: Consider a tree T with (�+1) leaves.
•Both T1 and T2 consist of at least one node, hence both have leaves<�−1
•leaf(T) = leaf(T1) + leaf(T2)
•Inter(T) = inter(T1) + inter(T2) + 1
= (leaf(T1) –1) + (leaf(T2) –1) + 1 = leaf(T1) + leaf(T2) –1 = leaf(T) -1
Review of Proofs
•e.g.All horses are the same color.
•Label horses: 1,2,3,…,�,�+1
•Step 1: in any set of �horses, all horses have the same color
•Step 2: �=1, clearly holds.
•Step 3: assume it holds for any set with ≤�horses
•Step 4: Consider a set of (�+1) horses.
•Apply hypothesis since size is ≤�, each set must be of one color
•Consider sets ,1,2,3,…,nand2,3,…,n+1
•The two sets intersect: have at least one horse in common
•Hence, all (�+1) horses are the same color.
Q: Is my proof right ?
→“The two sets intersect” are not true for n = 2
•e.g.All horses are the same color.
•Label horses: 1,2,3,…,�,�+1
•Step 1: in any set of �horses, all horses have the same color
•Step 2: �=1, clearly holds.
•Step 3: assume it holds for any set with ≤�horses
•Step 4: Consider a set of (�+1) horses.
•Apply hypothesis since size is ≤�, each set must be of one color
•Consider sets ,1,2,3,…,nand2,3,…,n+1
•The two sets intersect: have at least one horse in common
•Hence, all (�+1) horses are the same color.
Q: Is my proof right ?
→“The two sets intersect” are not true for n = 2
Time Complexity
•The time complexity of an algorithm associates a
number T(n),
•the worst-case time the algorithm takes, with each
problem size n
•Mathematically, T: N → R
•T is a function mapping non-negativeintegers
(problem sizes) to realnumbers (number of steps)
•A key question is “Scaling up” of the algorithm
•What happens to my runtime if I have twice as many items,
or twice as large graph?
•(E.g. today: ��
2
, next year: �(2�)
2
=4��
2
: 4x longer)
•Big-Oh notation answers this kind of questions.
•The time complexity of an algorithm associates a
number T(n),
•the worst-case time the algorithm takes, with each
problem size n
•Mathematically, T: N → R
•T is a function mapping non-negativeintegers
(problem sizes) to realnumbers (number of steps)
•A key question is “Scaling up” of the algorithm
•What happens to my runtime if I have twice as many items,
or twice as large graph?
•(E.g. today: ��
2
, next year: �(2�)
2
=4��
2
: 4x longer)
•Big-Oh notation answers this kind of questions.
Big O (DPV Chapter 0)
Upper bounds: T(n) is O(f(n)) if there exist constants c > 0 and
�
00 such that for all n �
0we have T(n) c · f(n)
Lower bounds: T(n) is (f(n)) if there exist constants c > 0 and
�
00 such that for all n �
0we have T(n) c · f(n).
Tight bounds: T(n) is (f(n)) if T(n) is both O(f(n)) and (f(n)).
Upper bounds: T(n) is O(f(n)) if there exist constants c > 0 and
�
00 such that for all n �
0we have T(n) c · f(n)
Lower bounds: T(n) is (f(n)) if there exist constants c > 0 and
�
00 such that for all n �
0we have T(n) c · f(n).
Tight bounds: T(n) is (f(n)) if T(n) is both O(f(n)) and (f(n)).
Big O (DPV Chapter 0)
e.g., ��=32�
2
+17�+32
→T(n) is O(�
2
), O(�
3
), (�
2
), (n), and (�
2
)
→T(n) is not O(n), (�
3
), (n), or (�
3
).
e.g., ��=32�
2
+17�+32
→T(n) is O(�
2
), O(�
3
), (�
2
), (n), and (�
2
)
→T(n) is not O(n), (�
3
), (n), or (�
3
).
Big O (DPV Chapter 0)
•Not Transitive:
�
1�=5�
3
,�
2�=3�
2
�
1�=��
3
,�
2�=��
3
,but�
1�≠�
2�
Better notation: ��∈�(�(�))
•T(n) is in the setof functions bounded from above by f(n)
•Transitivity:
•If f O(g) and g O(h) then f O(h).
•If f = (g) and g = (h) then f (h).
•If f (g) and g (h) then f (h)
•Additivity:
If f O(h) and g O(h) then f + g O(h).
If f (h) and g (h) then f + g (h).
If f (h) and g O(h) then f + g (h)
•Not Transitive:
�
1�=5�
3
,�
2�=3�
2
�
1�=��
3
,�
2�=��
3
,but�
1�≠�
2�
Better notation: ��∈�(�(�))
•T(n) is in the setof functions bounded from above by f(n)
•Transitivity:
•If f O(g) and g O(h) then f O(h).
•If f = (g) and g = (h) then f (h).
•If f (g) and g (h) then f (h)
•Additivity:
If f O(h) and g O(h) then f + g O(h).
If f (h) and g (h) then f + g (h).
If f (h) and g O(h) then f + g (h)
•Some Common Functions
•Polynomials:�
0+�
1�+…+�
??????�
??????
��(�
??????
)if �
??????> 0
•Logarithms: the base does not matter
•�log
��=�(log
��)for any constant �,�>0
•log
��=log
��/log
��
•Polynomial time. Running time is O(�
??????
) for some constant d
independent of the input size n.
•Exponential time. Running time is O(�
�
) for some constant r
•Logarithms grow slower than every polynomial: ����∈�(�
??????
)
•Exponentials grow faster than every
polynomial(r > 1, d > 0)
•Polynomials:�
0+�
1�+…+�
??????�
??????
��(�
??????
)if �
??????> 0
•Logarithms: the base does not matter
•�log
��=�(log
��)for any constant �,�>0
•log
��=log
��/log
��
•Polynomial time. Running time is O(�
??????
) for some constant d
independent of the input size n.
•Exponential time. Running time is O(�
�
) for some constant r
•Logarithms grow slower than every polynomial: ����∈�(�
??????
)
•Exponentials grow faster than every
polynomial(r > 1, d > 0)
Small O Notation
•Let �and �be two functions from N to R+ (the set of positive real
numbers).
•If ���
n→
(f(n)/g(n))=0,then��∈�(�(�))
Upper bounds: �(�)is ??????(??????(�))if there existconstants �>0and
�
0≥0such that for all�≥�
0we have ��≤??????·??????(�).
•If ��∈�(�(�))then ��∈??????(�(�)), but the reverse is not always true
•Inequality of big-Oneeds to hold for somepositive constant c,
•Inequality of small-omust hold for everypositive constant c
Small-o: For anypositive real number �, a number �
0exists such that
for every �≥�
0,�(�)<��(�).
•Let �and �be two functions from N to R+ (the set of positive real
numbers).
•If ���
n→
(f(n)/g(n))=0,then��∈�(�(�))
Upper bounds: �(�)is ??????(??????(�))if there existconstants �>0and
�
0≥0such that for all�≥�
0we have ��≤??????·??????(�).
•If ��∈�(�(�))then ��∈??????(�(�)), but the reverse is not always true
•Inequality of big-Oneeds to hold for somepositive constant c,
•Inequality of small-omust hold for everypositive constant c
Small-o: For anypositive real number �, a number �
0exists such that
for every �≥�
0,�(�)<��(�).
Some Examples of Running Times
•??????(log�): Binary search on sorted list
•??????(�): Find max element in a list
•??????(�log�): Sorta set of elements
•??????(�
�
): Find the pair of points that is closest to each other
•??????(�
�
): Given �sets �
1,…,�
�, each of which is a subsetof
1,2,…,�, is there some pair of these which are disjoint?
•??????(�
�
): Given a graph of �nodes, are there �nodes such that no
two are joined by an edge?
•??????(�
�
): Enumerate all subsets of a set of �elements
•??????(�!): Given a set of cities and distances, find a route that visits
each city exactly once and returns to the start city?
(naïve approach)
•??????(log�): Binary search on sorted list
•??????(�): Find max element in a list
•??????(�log�): Sorta set of elements
•??????(�
�
): Find the pair of points that is closest to each other
•??????(�
�
): Given �sets �
1,…,�
�, each of which is a subsetof
1,2,…,�, is there some pair of these which are disjoint?
•??????(�
�
): Given a graph of �nodes, are there �nodes such that no
two are joined by an edge?
•??????(�
�
): Enumerate all subsets of a set of �elements
•??????(�!): Given a set of cities and distances, find a route that visits
each city exactly once and returns to the start city?
(naïve approach)
Why Algorithm Design Matters?
Big O : Practical Problem
Big O : Practical Problem
Big O : Practical Problem
Big O : Practical Problem
Exponentials grow faster than every polynomial(�>1,�>0)
Exponentials grow faster than every polynomial(�>1,�>0)
Big O : Practical Problem
Inductive Proofs
1)A Statementinvolving a natural number �, andwe will show that
it holds for all values of �
2)Basis: show it holds for small inputs, usually for �=0or �=1
3)Induction Hypothesis: assume it holds for �(or all values ≤�)
4)Inductive Step: show it holds for (�+1)
Inductive Proofs
1)A Statementinvolving a natural number �, andwe will show that
it holds for all values of �
2)Basis: show it holds for small inputs, usually for �=0or �=1
3)Induction Hypothesis: assume it holds for �(or all values ≤�)
4)Inductive Step: show it holds for (�+1)
Dynamic Programming
•Dynamic programming
•Break up a probleminto a series of overlapping sub-problems
•build upsolutions to larger and larger sub-problems,
(reusingsolutions of encountered subproblems as much as
possible)
•Dynamic programming algorithms
•systematically search allpossibilities (thus guaranteeing
correctness)
•storing results to avoid recomputing (thus providing efficiency)
•Some famous dynamic programming algorithms.
•Comparing two files -Unix diff
•Hidden Markov models –Viterbi
•Genetic sequence alignment -Smith-Waterman
•Shortest paths -Bellman-Ford
•Parsing context free grammars -Cocke-Kasami-Younger
Dynamic Programming
•Break up a probleminto a series of overlapping sub-problems
•build upsolutions to larger and larger sub-problems,
(reusingsolutions of encountered subproblems as much as
possible)
•Dynamic programming algorithms
•systematically search allpossibilities (thus guaranteeing
correctness)
•storing results to avoid recomputing (thus providing efficiency)
•Some famous dynamic programming algorithms.
•Comparing two files -Unix diff
•Hidden Markov models –Viterbi
•Genetic sequence alignment -Smith-Waterman
•Shortest paths -Bellman-Ford
•Parsing context free grammars -Cocke-Kasami-Younger
Dynamic Programming
•Top-down DP =Memoization
•Design a recursivealgorithm
•Store result for each subproblem when you first compute it
•Check for existing result for a subproblem, before doing any
extra work
Dynamic Programming
•Bottom-upDP =IterativeDP
•Determine dependency between a problem and its subproblems
•Determine an order in which to compute subproblems so that you
always have what you need already available
•Fill in the table of results in the determined order (using FORloops)
•Design a recursivealgorithm
•Store result for each subproblem when you first compute it
•Check for existing result for a subproblem, before doing any
extra work
Dynamic Programming
•Bottom-upDP =IterativeDP
•Determine dependency between a problem and its subproblems
•Determine an order in which to compute subproblems so that you
always have what you need already available
•Fill in the table of results in the determined order (using FORloops)
Dynamic Programming: Outline
•Fibonacci Numbers
•Longest Increasing Subsequence (LIS)
•Longest Common Subsequence (LCS)
•Knapsack
•Chain Matrix Multiply
•Shortest Path Algorithms
•Fibonacci Numbers
•Longest Increasing Subsequence (LIS)
•Longest Common Subsequence (LCS)
•Knapsack
•Chain Matrix Multiply
•Shortest Path Algorithms
Fibonacci Numbers
•How to solveit ?
•RecursiveAlgorithm
•DynamicProgramming
•Goal: Given number �generate the �-thFibonacci numbers
What is Fibonaccinumbers?
0,1,1,2,3,5,8,13,21,34,….
??????
0=0,??????
1=1, ??????
�=??????
�−1+??????
�−2for�>1
•Define Problem
•Input: integer n≥0
•Output: �-thFibonacci number
•How to solveit ?
•RecursiveAlgorithm
•DynamicProgramming
•Goal: Given number �generate the �-thFibonacci numbers
What is Fibonaccinumbers?
0,1,1,2,3,5,8,13,21,34,….
??????
0=0,??????
1=1, ??????
�=??????
�−1+??????
�−2for�>1
•Define Problem
•Input: integer n≥0
•Output: �-thFibonacci number
Fibonacci Numbers: RecursiveAlgorithm
Fib1(n):
Input: integer �≥0
Output: ??????
�
If n = 0, return 0
If n = 1, return 1
return Fib1(n-1) + Fib1(n-2)
Shortages:
repeat computing
(recursive from up to down)
Fib1(n):
Input: integer �≥0
Output: ??????
�
If n = 0, return 0
If n = 1, return 1
return Fib1(n-1) + Fib1(n-2)
Shortages:
repeat computing
(recursive from up to down)
Fibonacci Numbers: DP Pseudocode
Fib2(n):
F[0] = 0
F[1] = 1
For i= 2 to n do
F[i] = F[i-1] + F[i-2]
End for
Return F[n]
•No repeat computing, time complexity: �(�)
•Fasterthan recursive
•Simpler to analyze time complexity
Dynamic Programming (bottom-up)
Efficient
Computing
Fib2(n):
F[0] = 0
F[1] = 1
For i= 2 to n do
F[i] = F[i-1] + F[i-2]
End for
Return F[n]
•No repeat computing, time complexity: �(�)
•Fasterthan recursive
•Simpler to analyze time complexity
Dynamic Programming (bottom-up)
Efficient
Computing
DP Solution
•1
st
: Define Subproblem In Words
•??????[�]=�-thFibonacci Number
•2
nd
: State Recursive Relations
•??????�=??????�−1+??????�−2for∀2≤�≤�
•Define Initial State
•??????[0]=0,??????[1]=1
•1
st
: Define Subproblem In Words
•??????[�]=�-thFibonacci Number
•2
nd
: State Recursive Relations
•??????�=??????�−1+??????�−2for∀2≤�≤�
•Define Initial State
•??????[0]=0,??????[1]=1
Longest Increasing Subsequences (LIS)
•LIS problem:
•Find the lengthof the longest subsequence of a given
sequence s.t.all elements of the subsequenceare
sorted in increasing order.
•Subsequences: set of elements in order (can skip,
NO need to be consecutive)
E.g, Given sequence {5,7,4,−3,9,1,10,4,5,8,9,3}
•Subsequences :
−3,9,10 5,7,9,10 {4,4,5,8,9}
•LIS={−3,1,4,5,8,9}→len=�
•LIS problem:
•Find the lengthof the longest subsequence of a given
sequence s.t.all elements of the subsequenceare
sorted in increasing order.
•Subsequences: set of elements in order (can skip,
NO need to be consecutive)
E.g, Given sequence {5,7,4,−3,9,1,10,4,5,8,9,3}
•Subsequences :
−3,9,10 5,7,9,10 {4,4,5,8,9}
•LIS={−3,1,4,5,8,9}→len=�
LIS: DP Definition
•1
st
: Define Subproblem In Words
•Let ??????�=length of LIS on �
1,�
2,�
3,…..,�
�andincludes ??????
�
•2
nd
: State Recursive Relations
•Express ??????�in terms of ??????1,??????2,…,??????�−1
•??????�=1+max
1≤�≤�−1,&�
�<�
�
{??????[�]}for∀2≤�≤�
•Initial State
•??????1=1
•Input: �numbers �
1,�
2,�
3,…..,�
�
•Goal: find length of LIS in a list of numbers
•1
st
: Define Subproblem In Words
•Let ??????�=length of LIS on �
1,�
2,�
3,…..,�
�andincludes ??????
�
•2
nd
: State Recursive Relations
•Express ??????�in terms of ??????1,??????2,…,??????�−1
•??????�=1+max
1≤�≤�−1,&�
�<�
�
{??????[�]}for∀2≤�≤�
•Initial State
•??????1=1
•Input: �numbers �
1,�
2,�
3,…..,�
�
•Goal: find length of LIS in a list of numbers
LIS: DP Algorithm
LIS(�
1,�
2,�
3,…..,�
�):
L[1] = 1
for i= 2 to n do
for j = 1 to i-1do
if �
�< �
�then L[i] = 1 + L[j]
end if
end for
end for
#### find the maximum length of subsequences
max = 1
for i= 2 to n do
if L[i] > L[max] then max = i
end if
end for
return L[max]
LIS(�
1,�
2,�
3,…..,�
�):
L[1] = 1
for i= 2 to n do
for j = 1 to i-1do
if �
�< �
�then L[i] = 1 + L[j]
end if
end for
end for
#### find the maximum length of subsequences
max = 1
for i= 2 to n do
if L[i] > L[max] then max = i
end if
end for
return L[max]
Q: Find the length of LIS for {5, 7, 4, -3, 9, 1, 10, 4, 5, 8, 9, 3}
→len=6and LIS is {10, 22, 33, 50, 60, 80}.
index12345 6 7 8 9 10 11 12
value574-39 1 104 5 8 9 3
LIS_Len12113 2 4 3 4 5 6 3
LIS 55,
7
4-35, 7,
9
-3, 15, 7,
9, 10
-3, 1, 4-3, 1, 4,
5
-3, 1,
4, 5, 8
-3, 1, 4,
5, 8, 9
-3, 1,3
??????�=1+max
1≤�<�,&�
�<�
�
??????�for∀2≤�≤�
→len=6and LIS is {10, 22, 33, 50, 60, 80}.
index12345 6 7 8 9 10 11 12
value574-39 1 104 5 8 9 3
LIS_Len12113 2 4 3 4 5 6 3
LIS 55,
7
4-35, 7,
9
-3, 15, 7,
9, 10
-3, 1, 4-3, 1, 4,
5
-3, 1,
4, 5, 8
-3, 1, 4,
5, 8, 9
-3, 1,3
??????�=1+max
1≤�<�,&�
�<�
�
??????�for∀2≤�≤�
Q: Find the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80}
→len= 6 and LIS is {10, 22, 33, 50, 60, 80}.
index12 34 5 6 7 8 9
value1022 933 21 50 41 60 80
LIS_Len12 13 2 4 4 5 6
LIS 1010, 22910, 22,
33
10, 21
or
9, 21
10, 22,
33, 50
10, 22,
33, 41
10, 22, 33, 41, 60
or
10, 22, 33, 50, 60
10, 22, 33,
41, 60, 80
or
10, 22, 33,
50, 60, 80
Ref: https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/
Other examples: https://afteracademy.com/blog/longest-increasing-subsequence
??????�=1+max
1≤�<�,&�
�<�
�
??????�for∀2≤�≤�
→len= 6 and LIS is {10, 22, 33, 50, 60, 80}.
index12 34 5 6 7 8 9
value1022 933 21 50 41 60 80
LIS_Len12 13 2 4 4 5 6
LIS 1010, 22910, 22,
33
10, 21
or
9, 21
10, 22,
33, 50
10, 22,
33, 41
10, 22, 33, 41, 60
or
10, 22, 33, 50, 60
10, 22, 33,
41, 60, 80
or
10, 22, 33,
50, 60, 80
Ref: https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/
Other examples: https://afteracademy.com/blog/longest-increasing-subsequence
??????�=1+max
1≤�<�,&�
�<�
�
??????�for∀2≤�≤�
Longest Common Subsequence (LCS)
•Input: 2 strings X=x
1,�
2,…,�
�,
??????=�
1,�
2,…,�
�
•Goal: find the lengthof longest strings which
is a subsequenceof both XandY.
e.g, GivenX=BCDBCDA,Y=ABECBAB,
what is their longest common subsequence?
→LCS =BCBA, len =4
•Input: 2 strings X=x
1,�
2,…,�
�,
??????=�
1,�
2,…,�
�
•Goal: find the lengthof longest strings which
is a subsequenceof both XandY.
e.g, GivenX=BCDBCDA,Y=ABECBAB,
what is their longest common subsequence?
→LCS =BCBA, len =4
•Can be used to:
•compare files, e.g., Unix diff command (diff helps you to find differences
between files and directories.)
•Different ways of comparing files in Unix:
https://www.softwaretestinghelp.com/compare-two-files-unix/
•Biological applications:
•compare DNA of 2 or more different organisms to check similarity.
•minimize insert/delete mutations that can transform one DNA string
into the other
�
1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA(len= 29)
�
2=GTCGTTCGGAATGCCGTTGCTCTGTAAA(len = 28)
Longest Common Subsequence (LCS)
•compare files, e.g., Unix diff command (diff helps you to find differences
between files and directories.)
•Different ways of comparing files in Unix:
https://www.softwaretestinghelp.com/compare-two-files-unix/
•Biological applications:
•compare DNA of 2 or more different organisms to check similarity.
•minimize insert/delete mutations that can transform one DNA string
into the other
�
1=ACCGGTCGAGTGCGCGGAAGCCGGCCGAA(len= 29)
�
2=GTCGTTCGGAATGCCGTTGCTCTGTAAA(len = 28)
Longest Common Subsequence (LCS)
LCS: DP Definition 1
•1
st
: Design Subproblems in Words
•For �in[0,�], let ??????�=length of LCS in x
1,�
2,…,�
�and
y
1,�
2,…,�
�
•2
nd
: State Recursive Relations
•Express ??????�intermsof??????1, ??????2, …., ??????�−1for∀1≤�≤�
•Initial State
•??????0=0
e.g., X=BCDBCDAC,
Y=ABECBABC,
if x
i=y
i,thenLi=1+L[i−1]
if x
i≠y
i, LCS does not include x
ior/andy
i.
e.g, if exclude y
i, then subproblem is: LCS(�
1,�
�;;�
1,…,�
�−�)
→not recursive definition
•1
st
: Design Subproblems in Words
•For �in[0,�], let ??????�=length of LCS in x
1,�
2,…,�
�and
y
1,�
2,…,�
�
•2
nd
: State Recursive Relations
•Express ??????�intermsof??????1, ??????2, …., ??????�−1for∀1≤�≤�
•Initial State
•??????0=0
e.g., X=BCDBCDAC,
Y=ABECBABC,
if x
i=y
i,thenLi=1+L[i−1]
if x
i≠y
i, LCS does not include x
ior/andy
i.
e.g, if exclude y
i, then subproblem is: LCS(�
1,�
�;;�
1,…,�
�−�)
→not recursive definition
LCS: DP Definition 2
•1
st
: Design Subproblems in Words
•For i,jin[0,�], let ??????�,�= length of LCS in x
1,�
2,…,�
�and
y
1,�
2,…,�
�
•2
nd
: State Recursive Relations
•Express ??????�,�intermsof??????0,0,…,??????1,1, ??????1,2, ….,
??????�−1,�−1,Li−1,j,….,Li,j−1
•2 cases: �
�≠�
�or�
�=�
�
•Initial State
•??????�,0=0
•??????0,�=0
•1
st
: Design Subproblems in Words
•For i,jin[0,�], let ??????�,�= length of LCS in x
1,�
2,…,�
�and
y
1,�
2,…,�
�
•2
nd
: State Recursive Relations
•Express ??????�,�intermsof??????0,0,…,??????1,1, ??????1,2, ….,
??????�−1,�−1,Li−1,j,….,Li,j−1
•2 cases: �
�≠�
�or�
�=�
�
•Initial State
•??????�,0=0
•??????0,�=0
LCS: DP Definition 2
e.g., X=BCDBCDAC,
Y=ABECBABC, D
(1) if x
i≠y
j, LCS does not include x
ior/andy
i.
•if exclude �
�, then subproblem is: ????????????�(�
1,�
�;;�
1,…,�
�−1)
→??????[�,�]=??????[�,�−1]
•if exclude �
�, then subproblem is: ????????????�(x
1,x
i−1;;�
1,…,�
�)
→??????[�,�]=??????[�−1,�]
•if exclude both, then subproblem is: ????????????�(x
1,x
i−1;;�
1,…,�
�−1)
→??????[�,�]=??????[�−1,�−1]
→??????[�,�]=max{??????[�,�−�],??????[�−�,�],??????[�−�,�−�]}
=max{??????[�,�−�],??????[�−�,�]}
e.g., X=BCDBCDAC,
Y=ABECBABC, D
(1) if x
i≠y
j, LCS does not include x
ior/andy
i.
•if exclude �
�, then subproblem is: ????????????�(�
1,�
�;;�
1,…,�
�−1)
→??????[�,�]=??????[�,�−1]
•if exclude �
�, then subproblem is: ????????????�(x
1,x
i−1;;�
1,…,�
�)
→??????[�,�]=??????[�−1,�]
•if exclude both, then subproblem is: ????????????�(x
1,x
i−1;;�
1,…,�
�−1)
→??????[�,�]=??????[�−1,�−1]
→??????[�,�]=max{??????[�,�−�],??????[�−�,�],??????[�−�,�−�]}
=max{??????[�,�−�],??????[�−�,�]}
e.g., X=BCDBCDC,
Y=ABECBABC
(2) if x
i=y
�, LCS does not include x
ior/andy
i.
•if exclude y
�, then subproblem is: ????????????�(�
1,�
�;;�
1,…,�
�−1)
→??????[�,�]=??????[�,�−1]
•if exclude x
i, then subproblem is: ????????????�(�
1,�
�−1;;�
1,…,�
�)
→??????[�,�]=??????[�−1,�]
•if exclude both, then subproblem is: ????????????�(�
1,�
�−1;;�
1,…,�
�−1)
→??????[�,�]=??????[�−1,�−1]+1
→??????�,�=max{Li,j−1, Li−1,j, Li−1,j−1+1}
=??????�−�,�−�+�
LCS: DP Definition 2
Y=ABECBABC
(2) if x
i=y
�, LCS does not include x
ior/andy
i.
•if exclude y
�, then subproblem is: ????????????�(�
1,�
�;;�
1,…,�
�−1)
→??????[�,�]=??????[�,�−1]
•if exclude x
i, then subproblem is: ????????????�(�
1,�
�−1;;�
1,…,�
�)
→??????[�,�]=??????[�−1,�]
•if exclude both, then subproblem is: ????????????�(�
1,�
�−1;;�
1,…,�
�−1)
→??????[�,�]=??????[�−1,�−1]+1
→??????�,�=max{Li,j−1, Li−1,j, Li−1,j−1+1}
=??????�−�,�−�+�
LCS: DP Definition 2
LCS: DP Definition 2
•1
st
: Design Subproblems in Words
•For i,jin[0,�], let ??????�,�= length of LCS in x
1,�
2,…,�
�
and y
1,�
2,…,�
�
•2
nd
: State Recursive Relations
•Express ??????�,�intermsof??????0,0,…,??????1,1, ??????1,2, ….,
??????�−1,�−1,Li−1,j,….,Li,j−1
•for1≤�≤�,1≤�≤�:
•??????�,�=൝
�??????�??????�,�−�,??????�−�,��??????�
�≠�
�
??????�−�,�−�+��??????�
�=�
�
•????????????????????????????????????????????????????????????????????????
•??????�,0=0 ??????0,�=0
•1
st
: Design Subproblems in Words
•For i,jin[0,�], let ??????�,�= length of LCS in x
1,�
2,…,�
�
and y
1,�
2,…,�
�
•2
nd
: State Recursive Relations
•Express ??????�,�intermsof??????0,0,…,??????1,1, ??????1,2, ….,
??????�−1,�−1,Li−1,j,….,Li,j−1
•for1≤�≤�,1≤�≤�:
•??????�,�=൝
�??????�??????�,�−�,??????�−�,��??????�
�≠�
�
??????�−�,�−�+��??????�
�=�
�
•????????????????????????????????????????????????????????????????????????
•??????�,0=0 ??????0,�=0
LCS: DP Algorithm Pseudocode
LCS(X, Y):
#### initial states
for �=0�����
??????�,0=0
end for
for�=0�����:
??????0,�=0
end for
####recursiverelations
for�=1�����
for�=1�����
if �
�=�
�then ??????�,�=??????�−1,�−1+1
else: ??????�,�=���??????�,�−1,??????�−1,�
end if
end for
end for
return ??????�,�
Time
complexity:
�(�
2
)
LCS(X, Y):
#### initial states
for �=0�����
??????�,0=0
end for
for�=0�����:
??????0,�=0
end for
####recursiverelations
for�=1�����
for�=1�����
if �
�=�
�then ??????�,�=??????�−1,�−1+1
else: ??????�,�=���??????�,�−1,??????�−1,�
end if
end for
end for
return ??????�,�
Time
complexity:
�(�
2
)
LCS: DP Algorithm Pseudocode
LCS(X, Y):
#### initial states
for �=0�����
??????�,0=0
end for
for�=0�����:
??????0,�=0
end for
####recursiverelations
for�=1�����
for�=1�����
if �
�=�
�then ??????�,�=??????�−1,�−1+1
else: ??????�,�=���??????�,�−1,??????�−1,�
end if
end for
end for
return ??????�,�
Time
complexity:
�(��)
LCS(X, Y):
#### initial states
for �=0�����
??????�,0=0
end for
for�=0�����:
??????0,�=0
end for
####recursiverelations
for�=1�����
for�=1�����
if �
�=�
�then ??????�,�=??????�−1,�−1+1
else: ??????�,�=���??????�,�−1,??????�−1,�
end if
end for
end for
return ??????�,�
Time
complexity:
�(��)
LCS(X, Y):
#### initial states
for �=0�����
??????�,0=0
end for
for�=0�����:
??????0,�=0
end for
####recursiverelations
for�=1�����
for�=1�����
if �
�=�
�then ??????�,�=??????�−1,�−1+1
else: ??????�,�=���??????�,�−1,??????�−1,�
end if
end for
end for
return ??????�,�
�:FindLCSofX=ABCBDAB,Y=BDCABA
�0 1 2 3 4 5 6
� �
�B D C A B A
0 �
�
1 A
2 B
3 C
4 B
5 D
6 A
7 B
0 0 0 0 0 00
0
0
0
0
0
0
0
0 0 0 1 1 1
1 1 1 1 2
2
1 1 2 2 2 2
1 1 2 2 3
3
1 2 2 2 3 3
1 2 2 3 3 4
1 2 2 3 4 4
Q: How do we find the actual
optimal subsequence?
Q: Do we need the whole matrix
L (for finding longest length)?
#### initial states
for �=0�����
??????�,0=0
end for
for�=0�����:
??????0,�=0
end for
####recursiverelations
for�=1�����
for�=1�����
if �
�=�
�then ??????�,�=??????�−1,�−1+1
else: ??????�,�=���??????�,�−1,??????�−1,�
end if
end for
end for
return ??????�,�
�:FindLCSofX=ABCBDAB,Y=BDCABA
�0 1 2 3 4 5 6
� �
�B D C A B A
0 �
�
1 A
2 B
3 C
4 B
5 D
6 A
7 B
0 0 0 0 0 00
0
0
0
0
0
0
0
0 0 0 1 1 1
1 1 1 1 2
2
1 1 2 2 2 2
1 1 2 2 3
3
1 2 2 2 3 3
1 2 2 3 3 4
1 2 2 3 4 4
Q: How do we find the actual
optimal subsequence?
Q: Do we need the whole matrix
L (for finding longest length)?
DP Algorithm Definition Summary
•1
st
: Define Subproblemsin Words
a)Start with Prefixof current problem
b)Add constraintsif needed, e.g, include last
elements in LIS
•2
nd
: Express RecursiveRelations
•�[�]in terms of �1,…,��−1for∀valid�
•Define the InitialState
•T[1] or T[0]
•1
st
: Define Subproblemsin Words
a)Start with Prefixof current problem
b)Add constraintsif needed, e.g, include last
elements in LIS
•2
nd
: Express RecursiveRelations
•�[�]in terms of �1,…,��−1for∀valid�
•Define the InitialState
•T[1] or T[0]
Practical Problems
DPV 6.1: Maximum Subarray Problem
•Input: A list of numbers a
1,a
2,…,a
n
•Goal: Find Subarray (contiguous subsequence) of maximum sum
→Cannot determine if can append
a
i(do not know what it ends), so
need to revise subproblems
And the substring includes ??????
�
→��=??????
�+�??????�{�,�[�−�]}
��=�,��=??????
�
•1
st
: Define Subproblemsin Words
Siin terms of S[0], S[1], …, S[i-1]
•2
nd
: Express RecursiveRelations
•Define the InitialState
For iin0,n,letSi=maxsumofsubarryofa
1,a
2,….,a
i
Q: What is the output?
Q: Anyone can write the
pseudocode?
Q: [5, 15, -30, 10, -5, 40, 10] output?
DPV 6.1: Maximum Subarray Problem
•Input: A list of numbers a
1,a
2,…,a
n
•Goal: Find Subarray (contiguous subsequence) of maximum sum
→Cannot determine if can append
a
i(do not know what it ends), so
need to revise subproblems
And the substring includes ??????
�
→��=??????
�+�??????�{�,�[�−�]}
��=�,��=??????
�
•1
st
: Define Subproblemsin Words
Siin terms of S[0], S[1], …, S[i-1]
•2
nd
: Express RecursiveRelations
•Define the InitialState
For iin0,n,letSi=maxsumofsubarryofa
1,a
2,….,a
i
Q: What is the output?
Q: Anyone can write the
pseudocode?
Q: [5, 15, -30, 10, -5, 40, 10] output?
DPV 6.1: Maximum Subarray Pseudocode
X= a
1,a
2,…,a
n
MaximumSubarray(X):
S[1] = �
1
For���2,�:
��=??????
�+�??????�{�,�[�−�]}
Return ���(��)
LeetCode: https://leetcode.com/problems/maximum-subarray/
Q: [5, 15, -30, 10, -5, 40, 10] output?
→Subarray: [10, -5, 40, 10]
→minimum sum =10+−5+40+10=55
X= a
1,a
2,…,a
n
MaximumSubarray(X):
S[1] = �
1
For���2,�:
��=??????
�+�??????�{�,�[�−�]}
Return ���(��)
LeetCode: https://leetcode.com/problems/maximum-subarray/
Q: [5, 15, -30, 10, -5, 40, 10] output?
→Subarray: [10, -5, 40, 10]
→minimum sum =10+−5+40+10=55
Practical Problems
DPV 6.2: Hotel Stops
•You are going on a long trip. You start on the road at mile post 0.
Along the way there are n hotels, at mile posts �
1<�
2<…<�
�,
where each �
�is measured from the starting point.
•The only places you are allowed to stop are at these hotels, but
you can choose which of the hotels you stop at.
•You must stop at the final hotel (at distance �
�), which is your
destination.
•You’d ideally like to travel 200 miles a day, but this may not be
possible (depending on the spacing of the hotels). If you travel �
miles during a day, the penalty for that day is ���−�
�
.
•You want to plan your trip so as to minimize the total penalty—that
is, the sum, over all travel days, of the daily penalties.
•Give an efficient algorithm that determines the optimal sequence
of hotels at which to stop.
DPV 6.2: Hotel Stops
•You are going on a long trip. You start on the road at mile post 0.
Along the way there are n hotels, at mile posts �
1<�
2<…<�
�,
where each �
�is measured from the starting point.
•The only places you are allowed to stop are at these hotels, but
you can choose which of the hotels you stop at.
•You must stop at the final hotel (at distance �
�), which is your
destination.
•You’d ideally like to travel 200 miles a day, but this may not be
possible (depending on the spacing of the hotels). If you travel �
miles during a day, the penalty for that day is ���−�
�
.
•You want to plan your trip so as to minimize the total penalty—that
is, the sum, over all travel days, of the daily penalties.
•Give an efficient algorithm that determines the optimal sequence
of hotels at which to stop.
Practical Problems
DPV 6.2: Hotel Stops
•Input: sequence of increasing positive numbers: �
1<�
2<…<�
�
•Output: subsequence of numbers with minimum sum of penalties&
must include �
�
•If you travel �miles during a day, the penalty for that day is
200−�
2
•1
st
: Define Subproblemsin Words
•2
nd
: Express RecursiveRelations
•3
rd
: Define the InitialState
�[�]=minimumsumofpenalitieswhenstopat�
�
�[�]=Min
0≤�≤�−1
{��+(200−(�
�−�
�))
2
}
�[0]=0
Q: What is the output?
Q: Anyone can write the
pseudocode?
Q: [60, 150, 210, 300, 520, 700]
output?
DPV 6.2: Hotel Stops
•Input: sequence of increasing positive numbers: �
1<�
2<…<�
�
•Output: subsequence of numbers with minimum sum of penalties&
must include �
�
•If you travel �miles during a day, the penalty for that day is
200−�
2
•1
st
: Define Subproblemsin Words
•2
nd
: Express RecursiveRelations
•3
rd
: Define the InitialState
�[�]=minimumsumofpenalitieswhenstopat�
�
�[�]=Min
0≤�≤�−1
{��+(200−(�
�−�
�))
2
}
�[0]=0
Q: What is the output?
Q: Anyone can write the
pseudocode?
Q: [60, 150, 210, 300, 520, 700]
output?
DPV 6.2: Hotel Stops Pseudocode
X= a
1,a
2,…,a
n
HotelStops(X):
�[0]=0
For���1,�:
�[�]=Min
0≤�≤�−1
{��+(200−(�
�−�
�))
2
}
Return �[�]
Q: [60, 150, 210, 300, 520, 700] output?
→Stop at: 150, 300, 520, 700
→minimum penalty =50
2
+50
2
+20
2
+20
2
X= a
1,a
2,…,a
n
HotelStops(X):
�[0]=0
For���1,�:
�[�]=Min
0≤�≤�−1
{��+(200−(�
�−�
�))
2
}
Return �[�]
Q: [60, 150, 210, 300, 520, 700] output?
→Stop at: 150, 300, 520, 700
→minimum penalty =50
2
+50
2
+20
2
+20
2
Practical Problems
DPV 6.3: Yuck Donald’s Restaurant
•Yuckdonald’s is considering opening a series of restaurants
along Quaint Valley Highway (QVH).
The �possible locations are along a straight line, and the
distances of these locations from the
start of QVH are, in miles and in increasing order, �
1,�
2,…,�
�.
•The constraints are as follows:
•At each location, Yuckdonald’smay open at most one
restaurant.
•The expected profit from opening a restaurant at location �is
�
�, where �
�>0,����=1,2,3,…,�
•Any two restaurants should be at least �miles apart, where �
is a positive integer.
•Give an efficient algorithm to compute the maximum expected
total profit subject to the given constraints.
DPV 6.3: Yuck Donald’s Restaurant
•Yuckdonald’s is considering opening a series of restaurants
along Quaint Valley Highway (QVH).
The �possible locations are along a straight line, and the
distances of these locations from the
start of QVH are, in miles and in increasing order, �
1,�
2,…,�
�.
•The constraints are as follows:
•At each location, Yuckdonald’smay open at most one
restaurant.
•The expected profit from opening a restaurant at location �is
�
�, where �
�>0,����=1,2,3,…,�
•Any two restaurants should be at least �miles apart, where �
is a positive integer.
•Give an efficient algorithm to compute the maximum expected
total profit subject to the given constraints.
Practical Problems
•1
st
: Define Subproblemsin Words
•2
nd
: Express RecursiveRelations
•3
rd
: Define the InitialState
������1,�,��
=maximumsumofprofitwhenopeningthelastrestaurantat�
�
��= Max
1≤�≤�−1
and�
�−�
�≥�
��+�
�
(�1=�
1)
DPV 6.3: Yuck Donald’s Restaurant
•Input: nlocations’ milestone: �
1<�
2<⋯<m
n,with profit of each
location is : �
1,�
2,…,�
�.
•Goal: subsequence of numbers with maximum expected total profit
•Constraints :
•May open at most one restaurant at each location.
•The expected profit from opening a restaurant at location �is �
�, where
�
�>0,����=1,2,3,…,�
•Any 2 restaurants should be at least �miles apart (�is a positive integer).
Q: What is the output?
Q: Anyone can write the
pseudocode?
•1
st
: Define Subproblemsin Words
•2
nd
: Express RecursiveRelations
•3
rd
: Define the InitialState
������1,�,��
=maximumsumofprofitwhenopeningthelastrestaurantat�
�
��= Max
1≤�≤�−1
and�
�−�
�≥�
��+�
�
(�1=�
1)
DPV 6.3: Yuck Donald’s Restaurant
•Input: nlocations’ milestone: �
1<�
2<⋯<m
n,with profit of each
location is : �
1,�
2,…,�
�.
•Goal: subsequence of numbers with maximum expected total profit
•Constraints :
•May open at most one restaurant at each location.
•The expected profit from opening a restaurant at location �is �
�, where
�
�>0,����=1,2,3,…,�
•Any 2 restaurants should be at least �miles apart (�is a positive integer).
Q: What is the output?
Q: Anyone can write the
pseudocode?
DPV 6.3: Yuck Donald’s Restaurant Pseudocode
m=�
1,�
2,…,�
n, p=p
1,�
2,…,�
n
ChooseResaurant(m,p):
�[0]=0
For���1,�:
��= Max
1≤�≤�−1
and�
�−�
�≥�
��+�
�
Return max{��}
Q: m=[60,150,210,300,520,700], �=[50,30,60,80,100,80],
�=200, output?
→Open restaurant at: 60,300,520
→minimum penalty =50+80+100=230
m=�
1,�
2,…,�
n, p=p
1,�
2,…,�
n
ChooseResaurant(m,p):
�[0]=0
For���1,�:
��= Max
1≤�≤�−1
and�
�−�
�≥�
��+�
�
Return max{��}
Q: m=[60,150,210,300,520,700], �=[50,30,60,80,100,80],
�=200, output?
→Open restaurant at: 60,300,520
→minimum penalty =50+80+100=230
Practical Problems
DPV 6.4: String of Words
•You are given a string of �characters ��[1…�], which you believe to be a
corrupted text document, in which all punctuation has vanished (so that it
looks something like “itwasthebestoftimes...”).
You wish to reconstruct the document using a dictionary, which is available in
the form of a Boolean function dict∙for any string �,
dict�=ቊ
������������������
�������ℎ������
•(a) Give a dynamic programming algorithm that determines whether the
string s[·] can be reconstituted as a sequence of valid words. The running
time should be at most O(�
2
), assuming calls to dict∙take unit time.
•(b) In the event that the string is valid, make your algorithm output the
corresponding sequence of words.
DPV 6.4: String of Words
•You are given a string of �characters ��[1…�], which you believe to be a
corrupted text document, in which all punctuation has vanished (so that it
looks something like “itwasthebestoftimes...”).
You wish to reconstruct the document using a dictionary, which is available in
the form of a Boolean function dict∙for any string �,
dict�=ቊ
������������������
�������ℎ������
•(a) Give a dynamic programming algorithm that determines whether the
string s[·] can be reconstituted as a sequence of valid words. The running
time should be at most O(�
2
), assuming calls to dict∙take unit time.
•(b) In the event that the string is valid, make your algorithm output the
corresponding sequence of words.
Practical Problems
DPV 6.4: String of Words
•Input: A string of �characters ��1…�
•Goal: Determines whether the string s[·] can be reconstituted as a
sequence of valid words.
•1
st
: Define Subproblemsin Words
•2
nd
: Express RecursiveRelations
•3
rd
: Define the InitialState
for�in1,�,��=the first ??????characters can be reconstituted as a
sequence of valid words
��=??????�
0≤�<�(v
j⋀dict(substring(j,i)))
�0=����
•??????�
0≤�<��
�=�
0⋁�
1⋁�
2⋁…⋁�
�−1
•substringj,iis the substring of characters located in the place (�,�]
Q: What is the output?
Q: Anyone can write
the pseudocode?
DPV 6.4: String of Words
•Input: A string of �characters ��1…�
•Goal: Determines whether the string s[·] can be reconstituted as a
sequence of valid words.
•1
st
: Define Subproblemsin Words
•2
nd
: Express RecursiveRelations
•3
rd
: Define the InitialState
for�in1,�,��=the first ??????characters can be reconstituted as a
sequence of valid words
��=??????�
0≤�<�(v
j⋀dict(substring(j,i)))
�0=����
•??????�
0≤�<��
�=�
0⋁�
1⋁�
2⋁…⋁�
�−1
•substringj,iis the substring of characters located in the place (�,�]
Q: What is the output?
Q: Anyone can write
the pseudocode?
Practical Problems
DPV 6.4: String of Words Pseudocode
����������ℎ��������=�1…�
String_of_Words(�):
??????[0]=1
For���1,�:
��=OR
0≤�<�(v
j⋀dict(substring(j,i)))
Return ??????[�]
DPV 6.4: String of Words Pseudocode
����������ℎ��������=�1…�
String_of_Words(�):
??????[0]=1
For���1,�:
��=OR
0≤�<�(v
j⋀dict(substring(j,i)))
Return ??????[�]
Practical Problems
DPV 6.11: Longest Common SubString(LCSS)
•Input: Given two strings �=�
1�
2….�
�and �=�
1�
2….�
�,
•Goal: Find the lengthof their Longest Common SubString(LCSS)
•Show how to do this in time O(mn).
•1
st
: Define Subproblemsin Words
•2
nd
: Express RecursiveRelations •3
rd
: Define the
InitialState
For i,jin[0,�], let ??????�,�= length of LCSS in x
1,�
2,…,�
�
and y
1,�
2,…,�
�, and LCCS include �
�and �
�
Express ??????�,�intermsof??????0,0,…,??????1,1, ??????1,2, ….,
??????�−1,�−1,Li−1,j,….,Li,j−1
2 cases: �
�≠�
�or�
�=�
�
fori≥1,j≥1:
??????�,�=൝
� �??????�
�≠�
�
??????�−�,�−�+��??????�
�=�
�
??????�,0=0
??????0,�=0
Q: What is the output?
Q: Anyone can write
the pseudocode?
DPV 6.11: Longest Common SubString(LCSS)
•Input: Given two strings �=�
1�
2….�
�and �=�
1�
2….�
�,
•Goal: Find the lengthof their Longest Common SubString(LCSS)
•Show how to do this in time O(mn).
•1
st
: Define Subproblemsin Words
•2
nd
: Express RecursiveRelations •3
rd
: Define the
InitialState
For i,jin[0,�], let ??????�,�= length of LCSS in x
1,�
2,…,�
�
and y
1,�
2,…,�
�, and LCCS include �
�and �
�
Express ??????�,�intermsof??????0,0,…,??????1,1, ??????1,2, ….,
??????�−1,�−1,Li−1,j,….,Li,j−1
2 cases: �
�≠�
�or�
�=�
�
fori≥1,j≥1:
??????�,�=൝
� �??????�
�≠�
�
??????�−�,�−�+��??????�
�=�
�
??????�,0=0
??????0,�=0
Q: What is the output?
Q: Anyone can write
the pseudocode?
LCSS(X, Y):
For ���0,�:
??????�,0=0
For���0,�:
??????0,�=0
For���1,�:
For���1,�:
if �
�=�
�then ??????�,�=??????�−�,�−�+�
else:??????�,�=�
Return ���{??????�,�}
DPV 6.11: Longest Common SubString(LCSS)
For ���0,�:
??????�,0=0
For���0,�:
??????0,�=0
For���1,�:
For���1,�:
if �
�=�
�then ??????�,�=??????�−�,�−�+�
else:??????�,�=�
Return ���{??????�,�}
DPV 6.11: Longest Common SubString(LCSS)
Practical Problems
Rod Cutting
•Serling Enterprises buys long steel rods and cuts them
into shorter rods, which it then sells. Each cut is free.
•The management of Serling Enterprises wants to know
the best way to cut up the rods.
•We assume that we know, for �=1,2,3,…,�, the price �
�
in dollars that Serling Enterprises charges for a rod of
length �inches. Rod lengths are always an integral
numberof inches.
Ref: T.Cormen, C. Leiserson, R. Rivest, & C. Stein. Introduction to Algorithm 3
rd
Edition. ISBN 978-0-262-03384-8
Rod Cutting
•Serling Enterprises buys long steel rods and cuts them
into shorter rods, which it then sells. Each cut is free.
•The management of Serling Enterprises wants to know
the best way to cut up the rods.
•We assume that we know, for �=1,2,3,…,�, the price �
�
in dollars that Serling Enterprises charges for a rod of
length �inches. Rod lengths are always an integral
numberof inches.
Ref: T.Cormen, C. Leiserson, R. Rivest, & C. Stein. Introduction to Algorithm 3
rd
Edition. ISBN 978-0-262-03384-8
Rod-Cutting Problem:
•Input: Given a rod of length �inches and a table of prices �
�for�=
1,2,3,…,�,
•Goal: Determine the maximum revenue �
�obtainable by cutting up
the rod and selling the pieces.
•Note: if the price �
�for a rod of length �is large enough, an
optimal solution may require no cutting at all.
•1
st
: Define Subproblemsin Words
•2
nd
: Express RecursiveRelations
•3
rd
: Define the InitialState
For �in[1,�], let ��=maximum revenue obtainable by cutting up a rod
of length �and selling the pieces.
��=�??????��
�,��−�+��,��−�+��,…,��+��−�
=�??????�
�≤�<�{�
�,��−�+��}
�1=�
1
Rewrite ��in terms of ��,��,…,��−�
•Input: Given a rod of length �inches and a table of prices �
�for�=
1,2,3,…,�,
•Goal: Determine the maximum revenue �
�obtainable by cutting up
the rod and selling the pieces.
•Note: if the price �
�for a rod of length �is large enough, an
optimal solution may require no cutting at all.
•1
st
: Define Subproblemsin Words
•2
nd
: Express RecursiveRelations
•3
rd
: Define the InitialState
For �in[1,�], let ��=maximum revenue obtainable by cutting up a rod
of length �and selling the pieces.
��=�??????��
�,��−�+��,��−�+��,…,��+��−�
=�??????�
�≤�<�{�
�,��−�+��}
�1=�
1
Rewrite ��in terms of ��,��,…,��−�
Rod_Cut(p, n):
�1=�
1
for�in2,�:
�=�
�## price of i-inch rod
for j in �,�−�:
�=�??????�{�,R�−�+��}
��=�
Return ��
Rod-Cutting Problem: DP Pseudocode
Q: What is the best way to cut a 10-inch long rod, with profit from
each inch listed below?
Q: What is the time
complexity?
Q: Is there any way to
optimize this code?
Q: What is the time
complexity after
optimization?
�1=�
1
for�in2,�:
�=�
�## price of i-inch rod
for j in �,�−�:
�=�??????�{�,R�−�+��}
��=�
Return ��
Rod-Cutting Problem: DP Pseudocode
Q: What is the best way to cut a 10-inch long rod, with profit from
each inch listed below?
Q: What is the time
complexity?
Q: Is there any way to
optimize this code?
Q: What is the time
complexity after
optimization?
��=maximum revenue obtainable by cutting up a rod of length �.
Rod_Cut(p, n):
�1=�
1
for���2,�:
�=�
�## price of i-inch rod
for j in �,�/�:##floor(i/2)
�=�??????�{�,R�−�+��}
��=�
Return ��
•�2=max�
2,R1+R1=
max5,1+1=�→�
•R3=����
3,�1+�2=
max8,1+5=�→�
•R4=���{
}
�
4,�1+�3,�2+
�[2]=max9,1+8,5+5=
��→�,�
•�5=max{
}
�
5,R1+R4,R2+
R3=max10,1+10,5+8=
��→�,�
•R6=���{
}
�
6,�1+�5,�2+�4,
�3+�3=max{
}
17,1+13,5+10,
8+8=��→�
•R7=���{
}
�
7,�1+�6,�2+
�[5],�3+�4=max{
}
17,1+17,
5+13,8+10=��→
�,��??????�,�,��??????�,�,�
•R8=���{
}
�
8,�1+�7,�2+
�6,�3+�5,�4+�4=
max{
}
20,1+18,5+17,8+13,10+
10=��→�,�
•R9=���{
}
�
9,�1+�8,�2+
�7,�3+�6,�4+�5=
max{
}
24,1+22,5+18,8+17,10+
13=��→�,�
•R10=���{
}
�
10,�1+�9,�2+
�8,�3+�7,�4+�6,�5+
�5=max{
}
30,1+25,5+22,8+
18,10+17,13+13=��→��
Rod_Cut(p, n):
�1=�
1
for���2,�:
�=�
�## price of i-inch rod
for j in �,�/�:##floor(i/2)
�=�??????�{�,R�−�+��}
��=�
Return ��
•�2=max�
2,R1+R1=
max5,1+1=�→�
•R3=����
3,�1+�2=
max8,1+5=�→�
•R4=���{
}
�
4,�1+�3,�2+
�[2]=max9,1+8,5+5=
��→�,�
•�5=max{
}
�
5,R1+R4,R2+
R3=max10,1+10,5+8=
��→�,�
•R6=���{
}
�
6,�1+�5,�2+�4,
�3+�3=max{
}
17,1+13,5+10,
8+8=��→�
•R7=���{
}
�
7,�1+�6,�2+
�[5],�3+�4=max{
}
17,1+17,
5+13,8+10=��→
�,��??????�,�,��??????�,�,�
•R8=���{
}
�
8,�1+�7,�2+
�6,�3+�5,�4+�4=
max{
}
20,1+18,5+17,8+13,10+
10=��→�,�
•R9=���{
}
�
9,�1+�8,�2+
�7,�3+�6,�4+�5=
max{
}
24,1+22,5+18,8+17,10+
13=��→�,�
•R10=���{
}
�
10,�1+�9,�2+
�8,�3+�7,�4+�6,�5+
�5=max{
}
30,1+25,5+22,8+
18,10+17,13+13=��→��
THANK YOU!
67
67
Tags
Download
Download Slideshow Get the original presentation fileQuick Actions
Statistics
- Views 4
- Slides 67
- Age 265 days
Related Slideshows
11
TLE-9-Prepare-Salad-and-Dressing.pptxkkk
MaAngelicaCanceran
30 views
12
LESSON 1 ABOUT MEDIA AND INFORMATION.pptx
JojitGueta
24 views
60
GRADE-8-AQUACULTURE-WEEKQ1.pdfdfawgwyrsewru
MaAngelicaCanceran
39 views
26
Feelings PP Game FOR CHILDREN IN ELEMENTARY SCHOOL.pptx
KaistaGlow
39 views
![Jeopardy_Figures_of_Speech_Template.pptx [Autosaved].pptx](https://slidepub.com/thumb/5828/284015828.jpg)
54
Jeopardy_Figures_of_Speech_Template.pptx [Autosaved].pptx
acecamero20
23 views
7
Jeopardy_Figures_of_Speech.pptxvdsvdsvsdvsd
acecamero20
24 views