程序代写代做代考 algorithm Bioinformatics AVL data structure PowerPoint Presentation

PowerPoint Presentation

Faculty of Information Technology,
Monash University

FIT2004: Algorithms and Data Structures
Week 4:
Dynamic Programming

These slides are prepared by M. A. Cheema and are based on the material developed by Arun Konagurthu and Lloyd Allison.

Recommended Reading
Unit Notes (Chapter 5)
Weiss “Data Structures and Algorithm Analysis” (Pages 462-466.)

FIT2004: Lec-4: Dynamic Programming

Things to remember/note
FIT2004: Lec-4: Dynamic Programming
Next week is mid-sem break
If you don’t understand some lecture content, come to consultations! Times are available on Moodle
Assignment 1 is due at the end of week 4
Assignment 2 will be released at the end of week 4
Assignment 2 will be due at the end of week 6, so get started early!

Outline
Introduction to Dynamic Programming
Coins Change
Unbounded Knapsack
0/1 Knapsack
Edit Distance
Constructing Optimal Solution

FIT2004: Lec-4: Dynamic Programming

Dynamic Programming Paradigm
A powerful optimization technique in computer science
Applicable to a wide-variety of problems that exhibit certain properties.

Practice is the key to be good at dynamic programming
FIT2004: Lec-4: Dynamic Programming

Core Idea
Divide a complicated problem by breaking it down into simpler subproblems in a recursive manner and solve these.
Question: But how does this differ from `Divide and Conquer’ approach?
Overlapping subproblems: the same subproblem needs to be (potentially) be used multiple times
We also need Optimal substructure: optimal solutions to subproblems help us find optimal solutions to larger problems.
FIT2004: Lec-4: Dynamic Programming

N-th Fibonacci Number
FIT2004: Lec-4: Dynamic Programming
fib(N)
if N == 0 or N == 1
return N
else
return fib(N – 1) + fib(N – 2)

F(6)

F(5)

F(4)

F(3)

F(4)

F(1)

F(2)

F(2)

F(3)

F(3)

F(2)

F(1)

F(2)

F(0)

F(1)
Recursion tree for N = 6
Time Complexity
T(1) = b // b and c are constants
T(N) = T(N-1) + T(N-2) + c
= O(2N)

N-th Fibonacci Number
FIT2004: Lec-4: Dynamic Programming
fib(N)
if N == 0 or N == 1
return N
else
return fib(N – 1) + fib(N – 2)

F(6)

F(5)

F(4)

F(3)

F(4)

F(1)

F(2)

F(2)

F(3)

F(3)

F(2)

F(1)

F(2)

F(0)

F(1)
Recursion tree for N = 6
Time Complexity
T(1) = b // b and c are constants
T(N) = T(N-1) + T(N-2) + c
= O(2N)

N-th Fibonacci Number
FIT2004: Lec-4: Dynamic Programming
fib(N)
if N == 0 or N == 1
return N
else
return fib(N – 1) + fib(N – 2)

F(6)

F(5)

F(4)

F(3)

F(4)

F(1)

F(2)

F(2)

F(3)

F(3)

F(2)

F(1)

F(2)

F(0)

F(1)
Recursion tree for N = 6
Time Complexity
T(1) = b // b and c are constants
T(N) = T(N-1) + T(N-2) + c
= O(2N)

Can we memoize?

Fibonacci with Memoization: Version 1
memo[0] = 0 // 0th Fibonacci number
memo[1] = 1 // 1st Fibonacci number
for i=2 to i=N:
memo[i] = -1
fibDP(N)
if memo[N] != -1
return memo[N]
else
memo[N] = fibDP(N-1) + fibDP(N-2);
return memo[N]
Time Complexity
calls fibDP() roughly 2*N times
So the complexity is O(N)

FIT2004: Lec-4: Dynamic Programming

F(5)

F(4)

F(3)

F(4)

F(2)

F(3)
Recursion tree for N = 6

F(6)

F(2)

F(1)
Version 1 is called Top-down because it starts from the top – attempting the largest problem first, e.g., F(6)

Fibonacci with Memoization: Version 2
memo[0] = 0 // 0th Fibonacci number
memo[1] = 1 // 1st Fibonacci number
for i=2 to i=N:
memo[i] = memo[i-1] + memo[i-2]

FIT2004: Lec-4: Dynamic Programming
Version 2 is called Bottom-up because it starts from the bottom – solving the smallest problem first, e.g., F(0), F(1), and so on

Time Complexity
O(N)

0 1 1 2 4 5 8 13 21 34

Dynamic Programming Strategy
Assume you already know the solutions of all sub-problems and have memoized these solutions (overlapping subproblems)
E.g., Assume you know Fib(i) for every i < n Observe how you can solve the original problem using memoized solutions (optimal substructure) E.g., Fib(n) = Fib(n-1) + Fib(n-2) Solve the original problem by building upon solutions to the sub-problems E.g., Fib(0), Fib(1), Fib(2), …, Fib(n) FIT2004: Lec-4: Dynamic Programming Outline Introduction to Dynamic Programming Coins Change Unbounded Knapsack 0/1 Knapsack Edit Distance Constructing Optimal Solution FIT2004: Lec-4: Dynamic Programming Coins Change Problem Problem: A country uses N coins with denominations {a1, a2, …, aN}. Given a value V, find the minimum number of coins that add up to V. Example: Suppose the coins are {1, 5, 10, 50} and the value V is 110. The minimum number of coins required to make 110 is 3 (two 50 coins, and one 10 coin). Greedy solution does not always work. E.g., Coins = {1, 5, 6, 9} The minimum number of coins to make 12 is 2 (i.e., two 6 coins). What is the minimum number of coins to make 13? FIT2004: Lec-4: Dynamic Programming Coins Change Problem Problem: A country uses N coins with denominations {a1, a2, …, aN}. Given a value V, find the minimum number of coins that add up to V. Overlapping subproblems: What shall we store in the memo array? FIT2004: Lec-4: Dynamic Programming Quiz time! https://flux.qa - RFIBMB Coins Change Problem Problem: A country uses N coins with denominations {a1, a2, …, aN}. Given a value V, find the minimum number of coins that add up to V. Overlapping subproblems: What shall we store in the memo array? We want to know the minimum number of coins which add up to V, so lets try MinCoins[v] = {The fewest coins required to make exactly $v} Note: your first guess at what to put in the memo array may not be right, so try the most obvious thing and then play around if you can’t make it work FIT2004: Lec-4: Dynamic Programming Coins Change Problem Problem: A country uses N coins with denominations {a1, a2, …, aN}. Given a value V, find the minimum number of coins that add up to V. Overlapping subproblems: MinCoins[v] = {The fewest coins required to make exactly $v} Optimal substructure: To find the optimal substructure, we first deal with the base case(s). In this case, to make $0 requires 0 coins, so MinCoins[0] = 0 Assume we have optimal solutions for all v < V (stored in MinCoins[0..V-1] How could we determine MinCoins[V]? FIT2004: Lec-4: Dynamic Programming Quiz time! https://flux.qa - RFIBMB Coins Change Problem - Example Coins: [9, 5, 6, 1] V: 12 MinCoins: What options do we have to try and make $12? We have to use a coin! Lets try using the 9… After choosing the 9, what would be the optimal thing to do? Look at MinCoins[12-9] since now we need to make the other $3, and we already know the best way to do that Repeat this idea for the other coins and see which is best FIT2004: Lec-4: Dynamic Programming 0 1 2 3 4 1 1 2 3 1 2 2 0 1 2 3 4 5 6 7 8 9 10 11 12 Coins Change Problem - Example Coins: [9, 5, 6, 1] V: 12 MinCoins: MinCoins[12] = 1+min(MinCoins[12-9], MinCoins[12-5], MinCoins[12-6], MinCoins[12-1] = 1 + Min(3, 2, 1, 2) = 2 In general, MinCoins[v] = 1 + min(MinCoins[v-c] for all c in coins, where c <= v) Note also that if the value is less than every coin, then it cannot be made. This can be ignored if there is a $1 coin FIT2004: Lec-4: Dynamic Programming 0 1 2 3 4 1 1 2 3 1 2 2 0 1 2 3 4 5 6 7 8 9 10 11 12 Coins Change Problem - Example Coins: [9, 5, 6, 1] V: 12 MinCoins: In general, MinCoins[v] = 1 + min(MinCoins[v-c] for all c in coins, where c <= v) Why is that restriction on c necessary? Note also that if v is less than every coin, then it cannot be made. This can be ignored if there is a $1 coin FIT2004: Lec-4: Dynamic Programming 0 1 2 3 4 1 1 2 3 1 2 2 0 1 2 3 4 5 6 7 8 9 10 11 12 Coins Change Problem - Example Coins: [9, 5, 6, 1] V: 12 MinCoins: FIT2004: Lec-4: Dynamic Programming 0 1 2 3 4 1 1 2 3 1 2 2 0 1 2 3 4 5 6 7 8 9 10 11 12 Coins Change Problem - Example FIT2004: Lec-4: Dynamic Programming Overlapping subproblems: MinCoins[v] = {The fewest coins required to make exactly $v} Optimal substructure: Coins Change – Implementation (bottom up) With DP, you can generally implement straight from the recurrence to code Coin_change(c[1..n], V) min_coins[0..v] = infinity (note we start from 0 index here) min_coins[0] = 0 (from recurrence) for each value 1 to V if v less than every value in c[1..n] (from recurrence) do nothing else option = [ all values of MinCoins[v-c[i]], provided v >= c[i] ] (from recurrence)
set min_coins[value] to min(options)+1
return min_coins[V]
FIT2004: Lec-4: Dynamic Programming

//Assume that the coin_change function has appropriately initialised memo to an //array of nulls, and called our auxiliary function
Coin_change_aux(c[1..n], V)
if V = 0, return 0
if memo[v] = null
min_coins = infinity
for i in 1 to n
if c[i] <= V min_coins = min(min_coins, 1 + coin_change_aux(c, V-c[i])) memo[v] = min_coins return memo[v] FIT2004: Lec-4: Dynamic Programming Coins Change – Implementation (top down) This recursive call just returns memo[V-c[i]] instantly if we have already calculated it (because of this “if”) Outline Introduction to Dynamic Programming Coins Change Unbounded Knapsack 0/1 Knapsack Edit Distance Constructing Optimal Solution FIT2004: Lec-4: Dynamic Programming Unbounded Knapsack Problem Problem: Given a capacity C and a set of items with their weights and values, you need to pick items such that their total weight is at most C and their total value is maximized. What is the maximum value you can take? In unbounded knapsack, you can pick an item as many times as you want. Example: What is the maximum value for the example given below given capacity is 12 kg? Answer: $780 (take two Bs and two Ds) Greedy solution does not always work. FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 9kg 5kg 6kg 1kg Value $550 $350 $180 $40 DP Solution for Unbounded Knapsack FIT2004: Lec-4: Dynamic Programming Problem: Given a capacity C and a set of items with their weights and values, you need to pick items such that their total weight is at most C and their total value is maximized. What is the maximum value you can take? In unbounded knapsack, you can pick an item as many times as you want. We want the most value given that we are under a given weight. Overlapping subproblems: Memo[i] = Most value with capacity at most i If we know optimal solutions to all subproblems, how can we build an optimal solution to a larger problem? Similar logic to coin change: We need to choose an item For each possible item choice, find out how much value we could get (using subproblems) and then take the best one DP Solution for Unbounded Knapsack Similar logic to coin change: We need to choose an item For each possible item choice, find out how much value we could get (using subproblems) and then take the best one If we take item 1, then we have 3kg left The best we can do with 3kg is memo[3] = $120 So one option for memo[12] would be value[1] + memo[12-weight[1]] 40 80 120 160 350 390 430 470 550 700 740 1 2 3 4 5 6 7 8 9 10 11 12 Memo FIT2004: Lec-4: Dynamic Programming Item 1 2 3 4 Weight 9kg 5kg 6kg 1kg Value $550 $350 $180 $40 DP Solution for Unbounded Knapsack Memo[12] could be: value[1] + memo[12-weight[1]] = 550 + 120 = 670 Value[2] + memo[12-weight[2]] = 350 + 430 = 780 Value[3] + memo[12-weight[3]] = 390 + 180 = 570 Value[4] + memo[12-weight[4]] = 740 + 40 = 780 Choose the best! 40 80 120 160 350 390 430 470 550 700 740 1 2 3 4 5 6 7 8 9 10 11 12 Memo FIT2004: Lec-4: Dynamic Programming Item 1 2 3 4 Weight 9kg 5kg 6kg 1kg Value $550 $350 $180 $40 DP Solution for Unbounded Knapsack Memo[12] could be: value[1] + memo[12-weight[1]] = 550 + 120 = 770 Value[2] + memo[12-weight[2]] = 350 + 430 = 780 Value[3] + memo[12-weight[3]] = 390 + 180 = 570 Value[4] + memo[12-weight[4]] = 740 + 40 = 780 Choose the best! 40 80 120 160 350 390 430 470 550 700 740 1 2 3 4 5 6 7 8 9 10 11 12 Memo FIT2004: Lec-4: Dynamic Programming Item 1 2 3 4 Weight 9kg 5kg 6kg 1kg Value $550 $350 $180 $40 DP Solution for Unbounded Knapsack Memo[12] could be: value[1] + memo[12-weight[1]] = 550 + 120 = 770 Value[2] + memo[12-weight[2]] = 350 + 430 = 780 Value[3] + memo[12-weight[3]] = 390 + 180 = 570 Value[4] + memo[12-weight[4]] = 740 + 40 = 780 Choose the best! 40 80 120 160 350 390 430 470 550 700 740 780 1 2 3 4 5 6 7 8 9 10 11 12 Memo FIT2004: Lec-4: Dynamic Programming Item 1 2 3 4 Weight 9kg 5kg 6kg 1kg Value $550 $350 $180 $40 DP Solution for Unbounded Knapsack Lets write our recurrence What is our base case? With no capacity, we cannot take any items Also note, as before, that if an item is heavier than the capacity we have left, we cannot take it Otherwise, we want the maximum over all values (1 <= i <= n, vi) of items that we could take (wi <= c) But also taking into account the optimal value we could fit into the rest of our knapsack, one we took that item (MaxValue[c-wi]) Quiz time! https://flux.qa - RFIBMB DP Solution for Unbounded Knapsack Lets write our recurrence What is our base case? With no capacity, we cannot take any items Also note, as before, that if an item is heavier than the capacity we have left, we cannot take it Otherwise, we want the maximum over all values (1 <= i <= n, vi) of items that we could take (wi <= c) But also taking into account the optimal value we could fit into the rest of our knapsack, one we took that item (MaxValue[c-wi]) DP Solution for Unbounded Knapsack Overlapping subproblems: Memo[i] = Most value with capacity at most i Optimal substructure: Bottom-up Solution // Construct Memo[ ] starting from 1 until C in a way similar to previous slide . Initialize Memo[ ] to contain 0 for all indices for c = 1 to C maxValue = 0 for i=1 to N if Weight[ i ] <= c thisValue = Value[i] + Memo[c - Weight[ i ] ] if thisValue > maxValue
maxValue = thisValue
Memo[c] = maxValue

E.g., Fill Memo[13]

Time Complexity:
O(NC)
Space Complexity:
O(C + N)

FIT2004: Lec-4: Dynamic Programming
40 80 120 160 350 390 430 470 550 700 740 780

1 2 3 4 5 6 7 8 9 10 11 12 13

Memo
Item 1 2 3 4
Weight 9kg 5kg 6kg 1kg
Value $550 $350 $180 $40

Top-down Solution
Initialize Memo[ ] to contain -1 for all indices // -1 indicates solution for this index has not yet been computed
Memo[0] = 0
function knapsack(Capacity)
if Memo[ Capacity ] != -1:
return Memo[Capacity]
else:
maxValue = 0
for i=1 to N
if Weight[ i ] <= Capacity thisValue = Value[i] + knapsack(Capacity - Weight[ i ] ) if thisValue > maxValue
maxValue = thisValue
Memo[Capacity] = maxValue
return Memo[Capacity]

FIT2004: Lec-4: Dynamic Programming
Values[i] + Memo[ Capacity – Weights[i] ]
Bottom up solution:

Top Down vs Bottom Up
FIT2004: Lec-4: Dynamic Programming

Top-down may save some computations (E.g., some smaller subproblems may not needed to be solved)
Space saving trick may be applied for bottom-up to reduce space complexity
You may find one easier to think about
In some cases, the solution cannot be written bottom-up without some silly contortions

Outline
Introduction to Dynamic Programming
Coins Change
Unbounded Knapsack
0/1 Knapsack
Edit Distance
Constructing Optimal Solution

FIT2004: Lec-4: Dynamic Programming

0/1 Knapsack Problem
Same as unbounded knapsack except that each item can only be picked at most once.

Example: What is the maximum value for the example given below given capacity is 11 kg?
Answer: $590 (B and D)
Greedy solution may not always work.

FIT2004: Lec-4: Dynamic Programming
Item A B C D
Weight 6kg 1kg 5kg 9kg
Value $230 $40 $350 $550

0/1 Knapsack Problem
Same as unbounded knapsack except that each item can only be picked at most once.

Different from unbounded: If we pick an item X, giving us a remaining capacity R, we have to somehow make sure that X is not part of the optimal solution to our new subproblem of size R

Idea: Lets have two axes on which we think about subproblems.
Capacity
Which items are part of the subproblem

FIT2004: Lec-4: Dynamic Programming

0/1 Knapsack Problem
Problem: What is the solution for 0/1 knapsack for items {A,B,C,D} where capacity = 11.
Assume that we have computed solutions for every capacity<=11 considering the items {A,B,C} (see table below). What is the solution for capacity=11 and set {A,B,C,D} ? Case 1: the knapsack must NOT contain D Solution for 0/1 knapsack with set {A,B,C} and capacity 11. FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 6kg 1kg 5kg 9kg Value $230 $40 $350 $550 1 2 3 4 5 6 7 8 9 10 11 {A,B,C} 40 40 40 40 350 390 390 390 390 390 580 0/1 Knapsack Problem Problem: What is the solution for 0/1 knapsack for items {A,B,C,D} where capacity = 11. Assume that we have computed solutions for every capacity<=11 considering the items {A,B,C} (see table below). What is the solution for capacity=11 and set {A,B,C,D} ? Case 1: the knapsack must NOT contain D Solution for 0/1 knapsack with set {A,B,C} and capacity 11 = 580 Case 2: the knapsack must contain D The value of item D + solution for 0/1 knapsack with set {A,B,C} and capacity 11-9=2 This gives a value of 550+40 FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 6kg 1kg 5kg 9kg Value $230 $40 $350 $550 1 2 3 4 5 6 7 8 9 10 11 {A,B,C} 40 40 40 40 350 390 390 390 390 390 580 0/1 Knapsack Problem Problem: What is the solution for 0/1 knapsack for items {A,B,C,D} where capacity = 11. Assume that we have computed solutions for every capacity<=11 considering the items {A,B,C} (see table below). What is the solution for capacity=11 and set {A,B,C,D} ? Case 1: the knapsack must NOT contain D Solution for 0/1 knapsack with set {A,B,C} and capacity 11 = 580 Case 2: the knapsack must contain D The value of item D + solution for 0/1 knapsack with set {A,B,C} and capacity 11-9=2 This gives a value of 550+40 Solution = max(Case1, Case2) FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 6kg 1kg 5kg 9kg Value $230 $40 $350 $550 1 2 3 4 5 6 7 8 9 10 11 {A,B,C} 40 40 40 40 350 390 390 390 390 390 580 0/1 Knapsack Problem 1 2 3 4 5 6 7 8 9 10 11 12 0 Φ 0 0 0 0 0 0 0 0 0 0 0 0 1 A 0 0 0 0 0 230 230 230 230 230 230 230 2 B 40 40 40 40 40 230 270 270 270 270 270 270 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 Assume we know the optimal solutions for every subproblem and results are stored in Memo[ ][ ] Memo[ i ][ c ] contains the solution of knapsack for Set[1 … i] and capacity c FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 6kg 1kg 5kg 9kg Value $230 $40 $350 $550 i 0/1 Knapsack Problem 1 2 3 4 5 6 7 8 9 10 11 12 0 Φ 0 0 0 0 0 0 0 0 0 0 0 0 1 A 0 0 0 0 0 230 230 230 230 230 230 230 2 B 40 40 40 40 40 230 270 270 270 270 270 270 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 Assume we know the optimal solutions for every subproblem and results are stored in Memo[ ][ ] Memo[ i ][ c ] contains the solution of knapsack for Set[1 … i] and capacity c FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 6kg 1kg 5kg 9kg Value $230 $40 $350 $550 i max( 0/1 Knapsack Problem 1 2 3 4 5 6 7 8 9 10 11 12 0 Φ 0 0 0 0 0 0 0 0 0 0 0 0 1 A 0 0 0 0 0 230 230 230 230 230 230 230 2 B 40 40 40 40 40 230 270 270 270 270 270 270 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 Assume we know the optimal solutions for every subproblem and results are stored in Memo[ ][ ] Memo[ i ][ c ] contains the solution of knapsack for Set[1 … i] and capacity c FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 6kg 1kg 5kg 9kg Value $230 $40 $350 $550 i max(580 0/1 Knapsack Problem 1 2 3 4 5 6 7 8 9 10 11 12 0 Φ 0 0 0 0 0 0 0 0 0 0 0 0 1 A 0 0 0 0 0 230 230 230 230 230 230 230 2 B 40 40 40 40 40 230 270 270 270 270 270 270 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 Assume we know the optimal solutions for every subproblem and results are stored in Memo[ ][ ] Memo[ i ][ c ] contains the solution of knapsack for Set[1 … i] and capacity c FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 6kg 1kg 5kg 9kg Value $230 $40 $350 $550 i max(580, 550 + 40) 0/1 Knapsack Problem 1 2 3 4 5 6 7 8 9 10 11 12 0 Φ 0 0 0 0 0 0 0 0 0 0 0 0 1 A 0 0 0 0 0 230 230 230 230 230 230 230 2 B 40 40 40 40 40 230 270 270 270 270 270 270 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 590 Assume we know the optimal solutions for every subproblem and results are stored in Memo[ ][ ] Memo[ i ][ c ] contains the solution of knapsack for Set[1 … i] and capacity c FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 6kg 1kg 5kg 9kg Value $230 $40 $350 $550 i max(580, 550 + 40) 0/1 Knapsack Problem 1 2 3 4 5 6 7 8 9 10 11 12 0 Φ 0 0 0 0 0 0 0 0 0 0 0 0 1 A 0 0 0 0 0 230 230 230 230 230 230 230 2 B 40 40 40 40 40 230 270 270 270 270 270 270 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 590 Assume we know the optimal solutions for every subproblem and results are stored in Memo[ ][ ] Memo[ i ][ c ] contains the solution of knapsack for Set[1 … i] and capacity c FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 6kg 1kg 5kg 9kg Value $230 $40 $350 $550 i max( 0/1 Knapsack Problem 1 2 3 4 5 6 7 8 9 10 11 12 0 Φ 0 0 0 0 0 0 0 0 0 0 0 0 1 A 0 0 0 0 0 230 230 230 230 230 230 230 2 B 40 40 40 40 40 230 270 270 270 270 270 270 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 590 Assume we know the optimal solutions for every subproblem and results are stored in Memo[ ][ ] Memo[ i ][ c ] contains the solution of knapsack for Set[1 … i] and capacity c FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 6kg 1kg 5kg 9kg Value $230 $40 $350 $550 i max(620 0/1 Knapsack Problem 1 2 3 4 5 6 7 8 9 10 11 12 0 Φ 0 0 0 0 0 0 0 0 0 0 0 0 1 A 0 0 0 0 0 230 230 230 230 230 230 230 2 B 40 40 40 40 40 230 270 270 270 270 270 270 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 590 Assume we know the optimal solutions for every subproblem and results are stored in Memo[ ][ ] Memo[ i ][ c ] contains the solution of knapsack for Set[1 … i] and capacity c FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 6kg 1kg 5kg 9kg Value $230 $40 $350 $550 i max(620, 550 + 40) 0/1 Knapsack Problem 1 2 3 4 5 6 7 8 9 10 11 12 0 Φ 0 0 0 0 0 0 0 0 0 0 0 0 1 A 0 0 0 0 0 230 230 230 230 230 230 230 2 B 40 40 40 40 40 230 270 270 270 270 270 270 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 590 620 Assume we know the optimal solutions for every subproblem and results are stored in Memo[ ][ ] Memo[ i ][ c ] contains the solution of knapsack for Set[1 … i] and capacity c FIT2004: Lec-4: Dynamic Programming Item A B C D Weight 6kg 1kg 5kg 9kg Value $230 $40 $350 $550 i max(620, 550 + 40) 0/1 Knapsack Problem 1 2 3 4 5 6 7 8 9 10 11 12 0 Φ 0 0 0 0 0 0 0 0 0 0 0 0 1 A 0 0 0 0 0 230 230 230 230 230 230 230 2 B 40 40 40 40 40 230 270 270 270 270 270 270 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 590 620 Complexity: We need to fill the grid Filling each cell is O(1) since it is the max of 2 numbers, each of which can be computer in a constant number of lookups Therefore, the time and space complexity are both O(NC) where N is the number of items and C is the capacity of the knapsack FIT2004: Lec-4: Dynamic Programming i 0/1 Knapsack Problem 1 2 3 4 5 6 7 8 9 10 11 12 0 Φ 0 0 0 0 0 0 0 0 0 0 0 0 1 A 0 0 0 0 0 230 230 230 230 230 230 230 2 B 40 40 40 40 40 230 270 270 270 270 270 270 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 590 620 Complexity: We need to fill the grid Filling each cell is O(1) since it is the max of 2 numbers, each of which can be computer in a constant number of lookups Therefore, the time and space complexity are both O(NC) where N is the number of items and C is the capacity of the knapsack FIT2004: Lec-4: Dynamic Programming i 0/1 Knapsack Problem 1 2 3 4 5 6 7 8 9 10 11 12 0 Φ 0 0 0 0 0 0 0 0 0 0 0 0 1 A 0 0 0 0 0 230 230 230 230 230 230 230 2 B 40 40 40 40 40 230 270 270 270 270 270 270 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 590 620 Complexity: Think about how many bits it takes to specify input N is the number of items. The N items require O(N) bits to describe C is the capacity. C can be described with log(C) bits Instead of C, lets talk about B, the number of bits to specify C Now we can say our algorithm runs in O(CN) = O( which is not polynomial in the size of the input (as expected for an NP-complete problem) FIT2004: Lec-4: Dynamic Programming i 1 2 3 4 5 6 7 8 9 10 11 12 3 C 40 40 40 40 350 390 390 390 390 390 580 620 4 D 40 40 40 40 350 390 390 390 550 590 Reducing Space Complexity While generating each row, we only need to look at values from the previous row So all values from the earlier rows may be discarded Reduces space complexity to O(C) (or O(2B) as we saw) Note: Space saving not possible for top-down dynamic programming (since we don’t know the order we solve subproblems) FIT2004: Lec-4: Dynamic Programming Outline Introduction to Dynamic Programming Coins Change Unbounded Knapsack 0/1 Knapsack Edit Distance Constructing Optimal Solution FIT2004: Lec-4: Dynamic Programming Edit Distance The words computer and commuter are very similar, and a change of just one letter, p  m, will change the first word into the second. The word sport can be changed into sort by the deletion of p, or equivalently, sort can be changed into sport by the insertion of p'. Notion of editing provides a simple and handy formalisation to compare two strings. The goal is to convert the first string (i.e., sequence) into the second through a series of edit operations The permitted edit operations are: insertion of a symbol into a sequence. deletion of a symbol from a sequence. substitution or replacement of one symbol with another in a sequence. FIT2004: Lec-4: Dynamic Programming Edit Distance Edit distance between two sequences Edit distance is the minimum number of edit operations required to convert one sequence into another For example: Edit distance between computer and commuter is 1 Edit distance between sport and sort is 1. Edit distance between shine and sings is ? Edit distance between dnasgivethis and dentsgnawstrims is ? FIT2004: Lec-4: Dynamic Programming Some Applications of Edit Distance Natural Language Processing Auto-correction Query suggestions BioInformatics DNA/Protein sequence alignment FIT2004: Lec-4: Dynamic Programming Computing Edit Distance We want to convert s1 to s2 containing n and m letters, respectively To gain an intuition for this problem, lets look at some situations we might run into This is a good technique in general, try playing around with the problem and see what happens FIT2004: Lec-4: Dynamic Programming ? ? ? . . . ? ? ? x ? ? ? . . . ? x s1: s2: n m How much does it cost to turn s1 into s2 if the last characters are the same? We can leave the last character, and just convert the front part of one string into the front part of the other edit(s1[1..n], s2[1..m]) =edit(s1[1..n-1], s2[1..m-1]) Computing Edit Distance We want to convert s1 to s2 containing n and m letters, respectively To gain an intuition for this problem, lets look at some situations we might run into This is a good technique in general, try playing around with the problem and see what happens FIT2004: Lec-4: Dynamic Programming ? ? ? . . . ? ? ? x ? ? ? . . . ? y s1: s2: n m How much does it cost to turn s1 into s2 if the last characters are different? We have some options Computing Edit Distance Remember! We can assume that we have solved ALL subproblems already. In other words, we know Edit(s1[1..i], s2[1..j]) for all i<=n, j<=m BUT NOT when i = n AND j = m (since this is the exact problem we are trying to solve) Alternatively, we could think about it visually In this table, cell[i][j] is the cost of turning s1[1..i] into s2[1..j] 1 2 3 . . . m 1 2 3 . . . n Known: Unknown: Computing Edit Distance We know: Edit(s1[1..i], s2[1..j]) for all i<=n, j<=m BUT NOT i = n AND j = m Equivalently, we know all the blue cells 1 2 3 . . . m 1 2 3 . . . n From the bottom right corner, there are three things we can do: Go up Go left Go left and up Computing Edit Distance We know: Edit(s1[1..i], s2[1..j])for all i<=n, j<=m BUT NOT i = n AND j = m Equivalently, we know all the blue cells 1 2 3 . . . m 1 2 3 . . . n From the bottom right corner, there are three things we can do: Go up Go left Go left and up Going up: Subproblem: edit(s1[1..n-1], s2[1..m]) First delete s1[n] Then turn s1[1..n-1] into s2[1..m] Total cost: cost(delete) + edit(s1[1..n-1], s2[1..m]) Computing Edit Distance We know: Edit(s1[1..i], s2[1..j]) for all i<=n, j<=m BUT NOT i = n AND j = m Equivalently, we know all the blue cells 1 2 3 . . . m 1 2 3 . . . n From the bottom right corner, there are three things we can do: Go up Go left Go left and up Going left: Subproblem: edit(s1[1..n], s2[1..m-1]) First turn s1[1..n] into s2[1..m-1] First insert s2[m] at the end of s2 Total cost: edit(s1[1..n], s2[1..m-1]) + cost(insert) Computing Edit Distance We know: Edit(s1[1..i], s2[1..j]) for all i<=n, j<=m BUT NOT i = n AND j = m Equivalently, we know all the blue cells 1 2 3 . . . m 1 2 3 . . . n From the bottom right corner, there are three things we can do: Go up Go left Go left and up Going left: Subproblem: edit(s1[1..n-1], s2[1..m-1]) Replace s1[n] with s2[m] Turn s1[1..n-1] into s2[1..m-1] Total cost: edit(s1[1..n-1], s2[1..m-1]) + cost(replace) Computing Edit Distance Base cases? When one string is empty, the cost is just the length of the other string we would have to insert each character in the other string, starting from nothing So edit(s1[], s2[1..j]) = j edit(s1[1..i], s2[]) = i FIT2004: Lec-4: Dynamic Programming Computing Edit Distance If the last characters are the same: edit(s1[1..n-1], s2[1..m-1]) If the last characters are different, three options: cost(delete) + edit(s1[1..n-1], s2[1..m]) edit(s1[1..n], s2[1..m-1]) + cost(insert) edit(s1[1..n-1], s2[1..m-1]) + cost(replace) We want the minimum cost, so our optimal substructure will be (if all costs are 1) FIT2004: Lec-4: Dynamic Programming Computing Edit Distance Overlapping subproblems: Dist[I,j] = cost of operations to turn S[1...i] into S[1…j] Optimal substructure: FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ S I N G S FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S I N G S FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 N 3 G 4 Now you Try! S 5 FIT2004: Lec-4: Dynamic Programming Example Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Outline Introduction to Dynamic Programming Coins Change Unbounded Knapsack 0/1 Knapsack Edit Distance Constructing Optimal Solution FIT2004: Lec-4: Dynamic Programming Constructing optimal solutions FIT2004: Lec-4: Dynamic Programming The algorithms we have seen determine optimal values, e.g., Minimum number of coins Maximum value of knapsack Edit distance How do we construct optimal solution that gives the optimal value, e.g., The coins to give the change The items to put in knapsack Converting one string to the other There may be multiple optimal solutions and our goal is to return just one solution! Two strategies can be used. Create an additional array recording decision at each step Backtracking Decision Array Φ S H I N E Φ 0 S I N G S Make a second array of the same size Each time you fill in a cell of the memo array, record your decision in the decision array Remember, going right (or coming from the left) is insert Going down (or coming from up) is delete Going down and right (or coming from up and left) is replace OR do nothing FIT2004: Lec-4: Dynamic Programming Decision Array Φ S H I N E Φ 0 1 S I N G S FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S S I N G S Decision Array Φ S H I N E Φ 0 1 2 S I N G S FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H S I N G S Decision Array Φ S H I N E Φ 0 1 2 3 S I N G S FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I S I N G S Decision Array Φ S H I N E Φ 0 1 2 3 4 S I N G S FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N S I N G S Decision Array Φ S H I N E Φ 0 1 2 3 4 5 S I N G S FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S I N G S Decision Array Φ S H I N E Φ 0 1 2 3 4 5 S 1 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S I Delete I N Delete N G Delete G S Delete S Decision Array Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing I Delete I N Delete N G Delete G S Delete S Decision Array Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H I Delete I N Delete N G Delete G S Delete S Decision Array Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I I Delete I N Delete N G Delete G S Delete S Decision Array Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N I Delete I N Delete N G Delete G S Delete S Decision Array Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N Insert E I Delete I N Delete N G Delete G S Delete S Decision Array Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 N 3 G 4 S 5 FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N Insert E I Delete I Delete I N Delete N G Delete G S Delete S Decision Array FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N Insert E I Delete I Delete I replace I,H Do nothing Insert N Insert E N Delete N Delete N Choice? Choice? Do nothing Insert E G Delete G Delete G Choice? Choice? Delete G replace G, E S Delete S Delete S Choice? Choice? Delete S Choice? Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 Decision Array FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N Insert E I Delete I Delete I replace I,H Do nothing Insert N Insert E N Delete N Delete N replace N,H Delete N Do nothing Insert E G Delete G Delete G Delete G Delete G Delete G replace G, E S Delete S Delete S Delete S Delete S Delete S Delete S Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 Decision Array FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N Insert E I Delete I Delete I replace I,H Do nothing Insert N Insert E N Delete N Delete N replace N,H Delete N Do nothing Insert E G Delete G Delete G Delete G Delete G Delete G replace G, E S Delete S Delete S Delete S Delete S Delete S Delete S Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 Decision Array FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N Insert E I Delete I Delete I replace I,H Do nothing Insert N Insert E N Delete N Delete N replace N,H Delete N Do nothing Insert E G Delete G Delete G Delete G Delete G Delete G replace G, E S Delete S Delete S Delete S Delete S Delete S Delete S Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 Decision Array FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N Insert E I Delete I Delete I replace I,H Do nothing Insert N Insert E N Delete N Delete N replace N,H Delete N Do nothing Insert E G Delete G Delete G Delete G Delete G Delete G replace G, E S Delete S Delete S Delete S Delete S Delete S Delete S Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 Decision Array FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N Insert E I Delete I Delete I replace I,H Do nothing Insert N Insert E N Delete N Delete N replace N,H Delete N Do nothing Insert E G Delete G Delete G Delete G Delete G Delete G replace G, E S Delete S Delete S Delete S Delete S Delete S Delete S Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 Decision Array FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N Insert E I Delete I Delete I replace I,H Do nothing Insert N Insert E N Delete N Delete N replace N,H Delete N Do nothing Insert E G Delete G Delete G Delete G Delete G Delete G replace G, E S Delete S Delete S Delete S Delete S Delete S Delete S Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 Decision Array FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N Insert E I Delete I Delete I replace I,H Do nothing Insert N Insert E N Delete N Delete N replace N,H Delete N Do nothing Insert E G Delete G Delete G Delete G Delete G Delete G replace G, E S Delete S Delete S Delete S Delete S Delete S Delete S Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 Decision Array FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N Insert E I Delete I Delete I replace I,H Do nothing Insert N Insert E N Delete N Delete N replace N,H Delete N Do nothing Insert E G Delete G Delete G Delete G Delete G Delete G replace G, E S Delete S Delete S Delete S Delete S Delete S Delete S Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 Decision Array FIT2004: Lec-4: Dynamic Programming Φ S H I N E Φ null Insert S Insert H Insert I Insert N Insert E S Delete S Do nothing Insert H Insert I Insert N Insert E I Delete I Delete I replace I,H Do nothing Insert N Insert E N Delete N Delete N replace N,H Delete N Do nothing Insert E G Delete G Delete G Delete G Delete G Delete G replace G, E S Delete S Delete S Delete S Delete S Delete S Delete S Sequence of operations: Delete S (from position 5) replace G with E (at position 4) insert H (at position 2) SINGS SING SINE SHINE Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Start in bottom right Are the letters the same? Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Start in bottom right Are the letters the same? No Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Start in bottom right Are the letters the same? No From recurrence… We know that our current value (3) was obtained from any of the three previous cells by adding 1 Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Start in bottom right Are the letters the same? No From recurrence… We know that our current value (3) was obtained from any of the three previous cells by adding 1 So our options are up or up-and-left Choose one arbitrarily Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue from our new cell (but remember the path) Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue from our new cell (but remember the path) Letters are different Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue from our new cell (but remember the path) Letters are different Must have come from the cell above Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Letter are the same From our recurrence, we know IF our value is the same as the up-and-left cell, then we could have came from there IF our value is one more than the up cell or the left cell, then we could have come from there In this case, we came from up-and-left Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Letter are the same From our recurrence, we know IF our value is the same as the up-and-left cell, then we could have came from there IF our value is one more than the up cell or the left cell, then we could have come from there In this case, we came from up-and-left Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue in this way Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue in this way Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue in this way Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue in this way Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue in this way When you reach the top left cell, you are done So the sequence of operations is Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue in this way When you reach the top left cell, you are done So the sequence of operations is Replace(5, E) Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue in this way When you reach the top left cell, you are done So the sequence of operations is Replace(5, E), delete[4] Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue in this way When you reach the top left cell, you are done So the sequence of operations is Replace(5, E), delete[4], nothing Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue in this way When you reach the top left cell, you are done So the sequence of operations is Replace(5, E), delete[4], nothing, nothing Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue in this way When you reach the top left cell, you are done So the sequence of operations is Replace(5, E), delete[4], nothing, nothing, insert(2, H) Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue in this way When you reach the top left cell, you are done So the sequence of operations is Replace(5, E), delete[4], nothing, nothing, insert(2, H), nothing Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 FIT2004: Lec-4: Dynamic Programming Continue in this way When you reach the top left cell, you are done So the sequence of operations is Replace(5, E), delete[4], nothing, nothing, insert(2, H), nothing SINGS SINGE (replace position 5 with E) SINE (delete G in position 4) SHINE (insert H at position 2) Backtracking Vs Decision array? FIT2004: Lec-4: Dynamic Programming Space usage Backtracking requires less space as it does not require creating an additional array However, space complexity is the same Efficiency Backtracking requires to determine what decision was made which costs additional computation However, time complexity is the same Note the space saving tricks discussed for 0/1 knapsack and edit distance can only be used when solution is not to be constructed e.g., all rows are needed for backtracking, and all rows must be stored for 2D-decision array FIT2004: Lec-4: Dynamic Programming Dynamic Programming Strategy Assume you already know the optimal solutions for all subproblems and have memoized these solutions Observe how you can solve the original problem using this memoization Iteratively solve the sub-problems and memoize Things to do (this list is not exhaustive) Practice, practice, practice http://www.geeksforgeeks.org/tag/dynamic-programming/ https://www.topcoder.com/community/data-science/data-science-tutorials/dynamic-programming-from-novice-to-advanced/ http://weaklearner.com/problems/search/dp Revise hash tables and binary search tree Coming Up Next Hashing, Binary Search Tree, AVL Tree Concluding Remarks Finding coins: Using Decision array Initialize Memo[ ] to contain infinity for all indices Memo[0] = 0 Initialize Decisions[ ] to contain zeroes for v = 1 to V minCoins = Infinity for i=1 to N if Coins[ i ] <= v c = 1 + Memo[v - Coins[ i ] ] if c < minCoins minCoins = c coin = Coins[i] Memo[v] = minCoins Decisions[v] = coin 1 2 3 4 1 1 2 3 1 2 2 1 2 3 4 5 6 7 8 9 10 11 12 9 5 6 1 i 1+ memo[3] = 1 + 3 = 4 Memo 4 i 1+ memo[7] = 1 + 2 = 3 1+ memo[6] = 1 + 1 = 2 1+ memo[11] = 1 + 2 = 3 3 2 3 i i Coins 2 FIT2004: Lec-4: Dynamic Programming 1 1 1 1 5 6 6 6 9 9 5 1 2 3 4 5 6 7 8 9 10 11 12 Decisions 6 Do not store ALL coins needed to make the change at each step. Just store the chosen coin at that step. Finding coins: Using Decision array Solution = [] while V!=0: Solution.append(Decisions[V]) V = V – Decision[V] E.g., If V= 12 Look at Decisions[12], append 6  Solution = [6] Remaining change, V = 12-6=6 Look at Decisions[6], append 6  Solution = [6,6]. Stop because V = 6-6 = 0 If V = 11 Look at Decisions[11], append 5  Solution = [5] Remaining change, V = 11-5= 6 Look at Decisions[6], append 6  Solution = [5,6] Stop because V = 6-6 = 0 9 5 6 1 Coins FIT2004: Lec-4: Dynamic Programming 1 1 1 1 5 6 6 6 9 9 5 1 2 3 4 5 6 7 8 9 10 11 12 Decisions 6 Finding Coins: Backtracking Execution to be shown in class // Find coins for optimal solution for V = 13 without using Decision[] Solution = [] while V > 0:
for coin_value in Coins:
if coin_value <= V: if Memo[V] == 1 + Memo[V - coin_value] chosen_coin = coin_value break Solution.append(chosen_coin) V = V-chosen_coin 1 2 3 4 1 1 2 3 1 2 2 2 3 1 2 3 4 5 6 7 8 9 10 11 12 13 9 5 6 1 Memo Coins FIT2004: Lec-4: Dynamic Programming Solution: V: chosen_coin: Finding string conversion: Backtracking Φ S H I N E Φ 0 1 2 3 4 5 S 1 0 1 2 3 4 I 2 1 1 1 2 3 N 3 2 2 2 1 2 G 4 3 3 3 2 2 S 5 4 4 4 3 3 Backtracking: Use the Matrix to determine where the values are coming from (if multiple, pick any of those). Recall: Diagonal means substitution if letters are not same Upward arrow means removing the letter s1[i] Left arrow means adding the letter s2[i] in s1 Substitute S with E Delete G Add H after S S I N G S s1 E H FIT2004: Lec-4: Dynamic Programming If s1[n] == s2[m] cost = dist(s1[1…n-1],s2[1… m-1]) Else if substituting s1[n] with s2[m] cost = 1 + dist(s1[1…n-1],s2[1…m-1]) if adding s2[m] in s1 after s1[n] cost = 1 + dist(s1[1…n],s2[1…m-1]) if removing s1[n] cost = 1 + dist(s1[1…n-1],s2[1…m]) 1 2 … n 1 2 … m Review yourself: Subset Sum Problem Given a set of numbers N = {a1, a2, …, an} and a value V. Is their a subset of N such that the sum of elements is exactly V. Note: Unlike Coins Change problem, a number can only be used once to make the value V. Example: Suppose N = {1, 5, 6, 9} and the value V is 13. The answer is FALSE because no subset of N adds to 13. For V=15, the answer is TRUE because 9 + 6 = 15. What is the answer for V = 12? FIT2004: Lec-4: Dynamic Programming Subset Sum Problem Suppose N = {1, 5, 6, 9} and V = 16. Assume that I tell you that the subset must contain the value 9. What is the answer of subset problem? E.g., is there a subset that includes 9 and adds up to 16? If the subset must contain 9 The answer is True if and only if {1, 5, 6} has a subset adding up to 16-9 = 7 Suppose N = {1, 5, 6, 9} and V = 11. Assume that I tell you that the subset must NOT contain the value 9. What is the answer of subset problem? E.g., is there a subset that excludes 9 and adds up to 11? If the subset must not contain 9 The answer is True if {1, 5, 6} has a subset adding up to 11 FIT2004: Lec-4: Dynamic Programming If the Subset contains a number x Answer is True if {Set \ x} has a subset adding up to V - x Else Answer is True if {Set \ x} has a subset adding up to V Subset Sum Problem 0 1 2 3 4 5 6 7 8 9 Φ T F F F F F F F F 1 T T F F F F F F F 3 T T F T T F F F F 6 T T F T T F T ? ? Set = {1, 3, 6}. We need to check for V = 7 (e.g., is there a subset with sum = 7) Assume we know the optimal solutions for every subproblem and results are stored in Memo[ ][ ]. Memo[ v ][ i ] contains True if and only if there exists a subset of Set[1 … i] that adds to v for i=1 to n: for v in 1 to V: x = Set[ i ] if Memo[v-x][i-1]==True or Memo[v][i–1]==True Memo [v][i] = True Else Memo [v][i] = False //Fill column for 9 If the Subset contains a number x (e.g., number 6) Answer is True if {Set \ x} has a subset adding up to V - x Else Answer is True if {Set \ x} has a subset adding up to V T F Time Complexity: O(nV) Space Complexity: O(nV) FIT2004: Lec-4: Dynamic Programming /docProps/thumbnail.jpeg