EECE 330 Other Extra Lecture About Dynamic Programming, Spring 2017

Dynamic Programming Examples not included in slides: take notes Dynamic Programming (DP) • Not a specific algorithm, but a technique, like divide-and-conquer. • Used for: – decision problems (YES/NO answer) – optimization problems: Find a solution with the optimal value. Minimization or maximization – Counting problems • Term “dynamic” for historical reasons Recall the divide-and-conquer design technique • Divide and conquer paradigm involves 3 steps: – Divide problem into a number of sub-problems – Conquer the problem by solving them recursively – Combine the solutions of the sub-problems into the original problem solution • Examples: Binary Search, Merge Sort, Tower of Hanoi, and other recursive functions we have seen. Dynamic Programming versus divide-and-conquer • Similarity: both recursive • Main difference: we have many repeated sub-problems • Direct recursion leads to an exponential time algorithm Dynamic Programming versus divide-and-conquer (continued) • We can overcome this problem using a table (1- dimentional or 2-dimentional array) indexed by the sub- problems • Store, don’t re-compute: – When solving a sub-problem: – Lookup in table. – If answer is there, use it. – Else, compute answer, then store it. • This called the Memoization approach • Another approach is the Bottom up approach: avoid recursion completely by filling table bottom up Main step of Dynamic programming • Characterize the structure of the solution. • Recursively define the value of an solution • Direct recursive solutions is not efficient at all due repeated sub-problems • Use a table indexed by the sub-problems, and proceed by – Memoization, or – the bottom up approach • Construct the solution from computed information. Plan • We will illustrate the above steps on two problems: – Subset Sum problem – Longest Common Subsequence problem Subset Sum problem • Given a set of n positive integers A[0],A[1], …, A[n-1], and a non-negative target integer tar, check whether or not the set contains a subset whose sum is equal to the target • The elements of the desired subset need not be consecutive in the list • The subset can consist of an arbitrary number of elements: 0(if tar=0), 1, 2, 3, 4, … Examples • Set: 9 2 1 5 10 20 29 tar= 27 Answer: YES (2+5+20=27) • Set: 9 2 1 5 10 20 29 tar= 59 Answer: YES (9+1+20+29=59) • Set: 9 2 1 5 10 20 29 tar= 4 Answer: NO (no subset has sum = 4) • Set: 9 2 1 5 10 20 29 tar= 0 Answer: YES (the empty subset has sum = 0) Problem Difficulty • We cannot use nested loops as in the 2- SUM [PSS3] because: – we don’t know beforehand the subset size, and hence the number of need nested loops – and even if we knew the subset size, e.g. size =10, it is not efficient at all to use 10 nested loops as it takes in the order of n10 steps Recursive structure • Original problem: “Does the set A[0],A[1], …, A[n-1] contain a subset whose sum = tar?” • Look at the last element A[n-1] • Either we take it or we don’t take it Recursive structure (Continued) • If we take it, we get the sub-problem: “Does the set A[0],A[1], …, A[n-2] contain a subset whose sum = tar-A[n-1]?” (sub-prob size = n-1) • If we don’t, we get the sub-problem: “Does the set A[0],A[1], …, A[n-2] contain a subset whose sum = tar” (sup-prob size = n-1) • We try both cases recursively • Base case: Recursive structure (Continued) • If we take it, we get the sub-problem: “Does the set A[0],A[1], …, A[n-2] contain a subset whose sum = tar-A[n-1]?” (size = n-1) • If we don’t, we get the sub-problem: “Does the set A[0],A[1], …, A[n-2] contain a subset whose sum = tar” (size = n-1) • We try both cases recursively • Base case: size= 1 return TRUE iff tar== 0 or A[0] • Also return FALSE if tar<0 Recursive solution bool subsetSum(int A[], int i, int tar) // A[0…i] // intitial call cout<<subsetSum(A,n-1,tar); { if(i==0) return (tar==0)||(tar==A[0]); if(tar<0) return false; bool found1= subsetSum(A, i-1,tar-A[i]); bool found2= subsetSum(A, i-1,tar); return (found1 || found2); } Recursive solutions is not efficient at all due repeated sub-problems • Draw recursion on n=5 • Many repeated sub-problems • Exponentially many recursive calls • Takes in the order of 2n steps How many possible sub-problems do we have? How many possible sub-problems do we have? • They are: “Does the size set A[0],A[1], …, A[i] contain a subset whose sum = j?” for i=0….n-1 and for j=0….tar • That is, number of sub-probs = n*(tar+1) • It is quadratic not exponential ! Memoization approach • Use a 2-dimentional array T[0... n-1][0…tar] indexed by the n*(tar+1) sub-problems intialize it to -1’s (i.e., answer not computed yet) • Store, don’t re-compute: – When solving a sub-problem: – Lookup in table. – If answer is there, use it. – Else, compute answer, then store it. Draw table for: 9 2 1 5 (n = 4) and tar=3 Memoized SubsetSum bool memoizedSubSum(int A[], int i, int tar, int **T) // intitial call cout<< memoizedSubSum(A,n-1,tar,T); //table T[0... n-1][0…tar] pre-allocated and initialized to -1’s { if(i==0) return (tar==0)||(tar ==A[0]); //size 1 set if(tar<0) return false; if(tar-A[i]>=0 && T[i-1][tar-A[i]] == -1 ) T[i-1][tar-A[i]] =memoizedSubSum(A, i-1,tar-A[i], T); if( T[i-1][tar] == -1 ) T[i-1][tar] = memoizedSubSum(A, i-1,tar, T); return (tar-A[i]>=0) &&T[i-1][tar-A[i]] || T[i-1][tar] ; } Alternative bottom up approach We can avoid recursion completely by filling table bottom up: bool bottomUpSubsetSum(int A[], int n, int tar) // non-recursive function { bool **T = new bool*[n];// allocate memory for table bool T[0...n-1][0…tar] for(int i=0;i<n;i++) T[i] = new bool[tar+1]; T[0][0] = true; // Initialize first column for(int j=1;j<=tar;j++) T[0][j] = (j ==A[0]); // Initialize first column for(i=1;i<n;i++) // fill table for(int j = 0;j<=tar;j++) // bottom-up if( j-A[i] >=0) T[i][j] = T[i-1][j] || T[i-1][j-A[i]]; else T[i][j] = T[i-1][j]; bool answer = T[n-1][tar]; for(i=0;i< n;i++) delete [] T[i]; delete [] T; return answer; } Draw table for: 9 2 1 5 (n = 4) and tar=3 Finding the subset • If the answer is YES, we want to display a subset of the set whose sum is equal to the target • How? Finding the subset (continued) • Illustrate on previous example Finding the subset by backtracking If answer==true, backtrack using table (before deleting it): int i=n-1; int j=tar; while(j != 0) { if( i>0 && j-A[i]>=0 && T[i-1][j-A[i]] || i==0 && j==A[0] ) { cout<<A[i]<<" "; // take A[i] j=j-A[i]; // backtrack } i--; } Total time • In the order of n*tar to build table • Backtracking takes time linear in n • Thus total time: in the order of n*tar • Much faster than the direct recursive solution which takes in the order of 2n steps Next • Longest Common Subsequence problem • It is an optimization problem (unlike subset sum, which is a decision problem) Longest Common Subsequence (LCS) problem • A subsequence of a string S[1…N] is any sequence S[i1], S[i2], …, S[it], where 1≤i1< i2<…< it ≤N • Example: “Art” is a subsequence of “Algorithms” • Thus, unlike substrings, subsequences need not consist of consecutive characters • LCS problem: Given 2 strings X[1….m] and Y[0…n-1] find the length of the longest subsequence common to both • Note: we are starting from 1 and not from 0 for technical convenience Longest Common Subsequence (LCS) problem (Continued) • Example: X: A B C B D A B Y: B D C A B A Longest Common Subsequence (LCS) problem (Continued) • Example: X: A B C B D A B Y: B D C A B A BCBA is LCS of X and Y BDA is CS but not a LCS (BCBA is longer) BCAB is another LCS Applications • Comparing files, e.g.,. C++ file in EECE 230 to detect cheating • Comparing DNA’s Problem Difficulty • Brute force algorithm: Try every subsequence of X, check if it is subsequence of Y, and take the longest • There are 2m Subsequences of X • Exponential time, takes forever • Greedy approach: take a character of X and try to match to a character of Y, and so on .. • Does not give the longest common subsequence. Try it. Structure of the optimal solution • Look at the last chars of X and Y: X[m] and Y[n] and compare them Structure of the optimal solution (Continued) • Look at the last chars of X and Y: X[m] and Y[n] and compare them • Case 1: If X[m]=Y[n], then the LCS(X,Y) must end with X[m] Why? Otherwise, it can be made longer by adding X[m], which contradicts the LCS optimality Structure of the optimal solution (Continued) • Case 2: If X[m]≠Y[n] Let U be a LCS(X[1…m-1],Y[1…n]) V be a LCS(X[1…m],Y[1…n-1]) W longest among U and V Then W is a LCS(X,Y) Why? Structure of the optimal solution (Continued) Proof: Take any LCS Z of (X,Y) If Z does not end with X[m], then Z is a CS(X[1…m- 1],Y[1…n]). It must be also a LCS of (X[1…m-1],Y[1…n]) since otherwise Z can be made a longer CS of (X,Y), contradicting the maximality of Z. Thus length(Z)=length(U) If Z does not end with Y[n], then by a similar argument length(Z)=length(V) Thus length(W) ≥ length(Z) by the definition of Z But length(Z) ≥ length(W) since Z is a LCS(X,Y) Hence length(W) = length(Z), i.e., W is a LCS(X,Y) Recursive structure of the optimal solution Recursive structure of the optimal solution (Continued) Define C(i,j) = length of the a LCS(X[1…i], Y[1…j]) for i=1,….,m and j=1,….,n. Extended to i=0 and j=0, by leting C(i,j)=0 if i=0 or j=0 (one of the strings is empty) Original problem: C(m,n) Recursive structure of the optimal solution (Continued) Recurrence: If i,j≥1 and X[i]=Y[j] C(i,j) = C(i-1,j-1)+1 If i,j≥1 and X[i]≠Y[j] C(i,j) = max(C(i-1,j),C(i,j-1)) If i=0 or j=0 (base case) C(i,j) = 0 Recursive solution int LCS( char* X, int i, char* Y, int j) //X[1..i] and Y[1…i] start from index 1 not 0 for convenience // intitial call cout<<LCS(X,m,Y,n); { if(i==0 || j==0) return 0; if(X[i]==Y[j]) return LCS(X,i-1,Y,j-1)+1; else { int a = LCS(X,i-1,Y,j); int b = LCS(X,i,Y,j-1); if(a>b) return a; else return b; } } Recursive solutions is not efficient at all due repeated sub-problems • Draw recursion on m=4 and n=3 • Many repeated sub-problems • Exponentially many recursive calls • In the worst case, takes at least 2min(m,n) steps How many possible sub-problems do we have? How many possible sub-problems do we have? • They are: C(i,j) = length of the a LCS(X[1…i], Y[1…j]) for i=0,….,m and j=0,….,n. • That is, number of sub-probs = (m+1)*(n+1) • It is quadratic not exponential ! Memoization approach • Use a 2-dimentional array C[0... m][0…n] indexed by the (m+1)*(n+1) sub-problems intialize it to -1’s (i.e., answer not computed yet) • Store, don’t re-compute: – When solving a sub-problem: – Lookup in table. – If answer is there, use it. – Else, compute answer, then store it. Draw table for X = “ABCB” and Y = “BDC” Memoized LCS int memoizedLCS( char* X, int i, char* Y, int j, int **T) // intitial call cout<< memoizedLCS(X,m,Y,n,T); //table T[0... n][0…m] pre-allocated and initialized to -1’s { if(i==0 || j==0) return 0; if( X[i]==Y[j]) { if(T[i-1][j-1]== -1 ) T[i-1][j-1] =memoizedLCS(X,i-1,Y,j-1,T); return T[i-1][j-1]+1; } else { if(T[i-1][j] == -1) T[i-1][j] =memoizedLCS(X,i-1,Y,j,T); if(T[i][j-1] == -1) T[i][j-1] =memoizedLCS(X,i,Y,j-1,T); if(T[i][j-1] > T[i-1][j]) return T[i][j-1]; else return T[i-1][j]; } } Alternative bottom up approach We can avoid recursion completely by filling table bottom up: int bottomUpLCS(char* X, int m, char* Y, int n) // non-recursive function { //strings X[1..m] and Y[1…n] start from index 1 not 0 for convenience int **T = new int*[m+1];// allocate memory for table int T[0...m][0…n] for(int i=0;i<=m;i++) T[i] = new int[n+1]; for(i=0;i<=m;i++) T[i][0] = 0; // Initialize first row for(int j=1;j<=n;j++) T[0][j] = 0; // Initialize first column for(i=1;i<=n;i++) // fill table for(int j = 1;j<=n;j++) // bottom-up if(X[i]==Y[j]) T[i][j] = T[i-1][j-1]+1; else { if (T[i-1][j]>T[i][j-1]) T[i][j] = T[i-1][j]; else T[i][j] = T[i][j-1]; } int length = T[m][n]; for(i=0;i<=m;i++) delete [] T[i]; delete [] T; return lenght;} Finding the LCS • The above function finds the length of the LCS, we want to find a LCS of X and Y • How? Finding the LCS (Continued) • Use an auxiliary table Aux[1…m][1…n] to store the arrows: up-left (‘\\’), up (‘|’), or left (‘-’), which indicate where the min come from each cell in the table C • Illustrate on previous example • The backtracking using Aux table • We can fill table Aux while filling C by modifying the function bottomUpLCS Modified BottonUpLCS int bottomUpFindLCS(char* X, int m, char* Y, int n, char* char* char* char* LLLL) { // LCS will be stored in L. Assume enough memory is allocated // LCS will be stored in L. Assume enough memory is allocated // LCS will be stored in L. Assume enough memory is allocated // LCS will be stored in L. Assume enough memory is allocated int **T = new int*[m+1];// allocate memory for table int T[0...m][0…n] for(int i=0;i<=m;i++) T[i] = new int[n+1]; char**Aux = new char* [m+1] ; char**Aux = new char* [m+1] ; char**Aux = new char* [m+1] ; char**Aux = new char* [m+1] ; // allocate memory for auxiliary table // allocate memory for auxiliary table // allocate memory for auxiliary table // allocate memory for auxiliary table for (i=1;i<=m; i++) for (i=1;i<=m; i++) for (i=1;i<=m; i++) for (i=1;i<=m; i++) Aux[i Aux[i Aux[i Aux[i] = new char [n+1]; ] = new char [n+1]; ] = new char [n+1]; ] = new char [n+1]; //Aux[1...m][1 //Aux[1...m][1 //Aux[1...m][1 //Aux[1...m][1… …… …n] n] n] n] for(i=0;i<=m;i++) T[i][0] = 0; // Initialize first row for(int j=1;j<=n;j++) T[0][j] = 0; // Initialize first column for(i=1;i<=m;i++) // fill table for(int j = 1;j<=n;j++) // bottom-up if(X[i]==Y[j]) { T[i][j] = T[i-1][j-1]+1; Aux[i][j Aux[i][j Aux[i][j Aux[i][j] = ] = ] = ] = ‘‘‘‘\\\\\\\\’’’’;;;; } // up left // up left // up left // up left else { if (T[i-1][j]>T[i][j-1]) {T[i][j] = T[i-1][j]; Aux[i][j Aux[i][j Aux[i][j Aux[i][j] = ] = ] = ] = ‘‘‘‘----’’’’;;;; } // left // left // left // left else { T[i][j] = T[i][j-1]; Aux[i][j Aux[i][j Aux[i][j Aux[i][j] = ] = ] = ] = ‘‘‘‘||||’’’’;;;; } // up // up // up // up } int length= T[m][n]; Finding a LCS by backtracking //Then we backtrack using the arrows stored in table Aux: //Then we backtrack using the arrows stored in table Aux: //Then we backtrack using the arrows stored in table Aux: //Then we backtrack using the arrows stored in table Aux: i=m; j = n; i=m; j = n; i=m; j = n; i=m; j = n; int int int int k = length k = length k = length k = length----1;1;1;1; while while while while (i>0 (i>0 (i>0 (i>0 & & j>0) { j>0) { j>0) { j>0) { ifififif( ( ( ( Aux[i][j Aux[i][j Aux[i][j Aux[i][j] == ] == ] == ] == ‘‘‘‘\\\\\\\\’’’’) { ) { ) { ) { L[k L[k L[k L[k]= ]= ]= ]=X[i X[i X[i X[i];];];]; iiii--------; j ; j ; j ; j--------; k ; k ; k ; k--------;;;; }}}} else if else if else if else if( ( ( ( Aux[i][j Aux[i][j Aux[i][j Aux[i][j] == ] == ] == ] == ‘‘‘‘||||’’’’) i ) i ) i ) i--------;;;; else else else else jjjj--------;;;; // if // if // if // if Aux[i][j Aux[i][j Aux[i][j Aux[i][j] == ] == ] == ] == ‘‘‘‘----’’’’ }}}} L[length L[length L[length L[length]= ]= ]= ]=‘‘‘‘\\\\0000’’’’; // ; // ; // ; // Null terminate L Null terminate L Null terminate L Null terminate L [delete tables T and Aux] [delete tables T and Aux] [delete tables T and Aux] [delete tables T and Aux] return length; } Total time • In the order of m*n to fill tables T and Aux • Backtracking takes time linear in (m+n) • Thus total time: in the order of m*n • Much faster than the direct recursive solution which takes in the order of 2min(m,n) steps Backtracking in DP • Backtracking is not needed if the desired answer is YES/NO or the size of the object we are looking for (e.g., the length of the LCS), • It is needed if we want to produce the object, e.g., the subset in the subset sum problem if the answer is YES, or a LCS in the LCS problem. Summary • Dynamic Programming (DP) is a design technique like divide-and-conquer • Typically used for optimization problems and also for decision problems and counting problems (counting examples in the Programming Assignment) • Main difference compared to divide-and- conquer: we have many repeated sub-problems • We start by characterizing the structure of the solution and we recursively define the value of an solution Summary (Continued) • If the direct recursive solutions is not efficient (e.g., exponential) due to repeated sub- problems and if the number of sub-problems is small (e.g., quadratic, cubic, or even linear), we use a table indexed by the sub-problems, and proceed by Memoization, or the bottom up approach • To find the object we are looking for, we use backtracking • To backtrack, we may have to use an auxiliary table which we fill while filling the main DP table.