Dynamic Programming Dynamic Programming July 8, 2019 CMPE 250 Dynamic Programming July 8, 2019 1 / 1 Why Dynamic Programming Often recursive algorithms solve fairly difficult problems efficiently BUT...

1 answer below »
ADDED QUESTION AS PNG


Dynamic Programming Dynamic Programming July 8, 2019 CMPE 250 Dynamic Programming July 8, 2019 1 / 1 Why Dynamic Programming Often recursive algorithms solve fairly difficult problems efficiently BUT in other cases they are inefficient because they recalculate certain function values many times. For example: Fibonacci numbers. CMPE 250 Dynamic Programming July 8, 2019 2 / 1 Recursive solution The Recursive solution for finding the nth Fibonacci number: int fib( int n ) { if( n <= 1="" )="" return="" 1;="" else="" return="" fib(="" n="" -="" 1="" )="" +="" fib(="" n="" -="" 2="" );="" }="" time="" complexity:="" t="" (n)="T" (n="" −="" 1)="" +="" t="" (n="" −="" 2)="" which="" is="" exponential.="" extra="" space:o(n)="" if="" we="" consider="" the="" function="" call="" stack="" size,="" otherwise="" o(1).="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 3="" 1="" the="" problem="" fib(5)="" fib(4)="" fib(3)="" fib(2)="" fib(1)="" fib(0)="" fib(1)="" fib(2)="" fib(1)="" fib(0)="" fib(3)="" fib(2)="" fib(1)="" fib(0)="" fib(1)="" many="" calls="" to="" fib(3),fib(2),="" fib(1)="" and="" fib(0)="" are="" made.="" it="" would="" be="" nice="" if="" we="" only="" made="" those="" calls="" once,="" then="" simply="" used="" those="" values="" as="" necessary.="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 4="" 1="" dynamic="" programming="" the="" idea="" of="" dynamic="" programming="" is="" to="" avoid="" making="" redundant="" function="" calls="" instead,="" one="" should="" store="" the="" answers="" to="" all="" necessary="" function="" calls="" in="" memory="" and="" simply="" look="" these="" up="" as="" necessary.="" using="" this="" idea,="" we="" can="" code="" up="" a="" dynamic="" programming="" solution="" to="" the="" fibonacci="" number="" question="" that="" is="" far="" more="" efficient="" than="" the="" recursive="" version:="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 5="" 1="" dynamic="" programming="" solution="" int="" fibonacci(int="" n)="" {="" declare="" an="" array="" to="" store="" fibonacci="" numbers.="" int="" fibnumbers[n+1];="" 0th="" and="" 1st="" number="" of="" the="" series="" are="" 0="" and="" 1="" fibnumbers[0]="1;" fibnumbers[1]="1;" for="" (int="" i="2;" i="">< n+1;="" i++)="" add="" the="" previous="" 2="" numbers="" in="" the="" series="" and="" store="" it="" fibnumbers[i]="fibnumbers[i" -="" 1]="" +="" fibnumbers[i="" -="" 2];="" return="" fibnumbers[n];="" }="" time="" complexity:="" o(n)="" extra="" space:="" o(n)="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 6="" 1="" dynamic="" programming="" the="" only="" requirement="" this="" program="" has="" that="" the="" recursive="" one="" doesn’t="" have="" is="" the="" space="" requirement="" of="" an="" entire="" array="" of="" values.="" in="" fact,="" at="" a="" particular="" moment="" in="" time="" while="" the="" recursive="" program="" is="" running,="" it="" has="" at="" least="" n="" recursive="" calls="" in="" the="" middle="" of="" execution="" all="" at="" once.="" the="" amount="" of="" memory="" necessary="" to="" simultaneously="" keep="" track="" of="" each="" of="" these="" is="" at="" least="" as="" much="" as="" the="" memory="" the="" array="" we="" are="" using="" above="" needs.="" usually="" however,="" a="" dynamic="" programming="" algorithm="" presents="" a="" time-space="" trade="" off.="" more="" space="" is="" used="" to="" store="" values,="" but="" less="" time="" is="" spent="" because="" these="" values="" can="" be="" looked="" up.="" can="" we="" do="" even="" better="" (with="" respect="" to="" memory)="" with="" our="" fibonacci="" method="" above?="" what="" numbers="" do="" we="" really="" have="" to="" keep="" track="" of="" all="" the="" time?="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 7="" 1="" improved="" dynamic="" programming="" solution="" we="" can="" optimize="" the="" space="" used="" the="" dynamic="" programming="" solution="" by="" storing="" the="" previous="" two="" numbers="" only,="" because="" that="" is="" all="" we="" need="" to="" get="" the="" next="" fibonacci="" number="" in="" series.="" int="" fibonacci(int="" n)="" {="" int="" prevfib1="0," prevfib2="1," newfib;="" if(="" n="=" 0)="" return="" prevfib1;="" for="" (int="" i="2;" i=""><= n; i++) { newfib = prevfib1 + prevfib2; prevfib1 = prevfib2; prevfib2 = newfib; } return prevfib2; } time complexity: o(n) extra space: o(1) cmpe 250 dynamic programming july 8, 2019 8 / 1 why the term "dynamic programming" the origin of the term dynamic programming has very little to do with writing code. it was first coined by richard bellman in the 1950s, a time when computer programming was practiced by so few people as to not even deserve a name. at the time, programming meant planning, and dynamic programming was developed to optimally plan multistage processes. cmpe 250 dynamic programming july 8, 2019 9 / 1 properties of problems that can be solved using dynamic programming dynamic programming is an algorithmic paradigm that solves a given complex problem by breaking it into subproblems and stores the results of subproblems to avoid computing the same results again. the two main properties of a problem that suggest that the given problem can be solved using dynamic programming are: 1 overlapping subproblems 2 optimal substructure cmpe 250 dynamic programming july 8, 2019 10 / 1 overlapping subproblems property dynamic programming combines solutions to sub-problems. dynamic programming is mainly used when solutions of the same subproblems are needed again and again. computed solutions to subproblems are stored in a table so that these do not have to recomputed. example: recursive version of fibonacci numbers. cmpe 250 dynamic programming july 8, 2019 11 / 1 storing values for reuse there are two different ways to store the values so that these values can be reused: memoization (top down) tabulation (bottom up) cmpe 250 dynamic programming july 8, 2019 12 / 1 memoization the memoized program for a problem is similar to the recursive version with a small modification that it looks into a lookup table before computing solutions. we initialize a lookup array with all initial values as a default value. whenever we need solution to a subproblem, we first look into the lookup table. if the precomputed value is there then we return that value, otherwise we calculate the value and put the result in lookup table so that it can be reused later. cmpe 250 dynamic programming july 8, 2019 13 / 1 tabulation the tabulated program for a given problem builds a table in bottom up fashion and returns the last entry from the table. starting from the first entry, all entries are filled one by one. cmpe 250 dynamic programming july 8, 2019 14 / 1 optimal substructure property a given problem has optimal substructure property if the optimal solution of the given problem can be obtained by using optimal solutions of its subproblems. example: the shortest path problem has the following optimal substructure property: if a vertex x lies in the shortest path from a source vertex u to destination vertex v then the shortest path from u to v is the combination of the shortest path from u to x and the shortest path from x to v . cmpe 250 dynamic programming july 8, 2019 15 / 1 common subproblems finding the right subproblem takes creativity and experimentation. but there are a few standard choices that seem to arise repeatedly in dynamic programming. the input is x1, x2, . . . , xn and a subproblem is x1, x2, . . . , xi . the number of subproblems is therefore linear. the input is x1, . . . , xn, and y1, . . . , ym. a subproblem is x1, . . . , xi and y1, . . . , yj . |x1 x2 x3 x4 x5 x6| x7 x8 x9 x10 |y1 y2 y3 y4 y5| x6 x7 x8 the number of subproblems is o(mn). the input is x1, . . . , xn and a subproblem is xi , xi+1, . . . , xj . x1 x2 |x3 x4 x5 x6| x7 x8 x9 x10 the number of subproblems is o(n2). the input is a rooted tree. a subproblem is a rooted subtree. cmpe 250 dynamic programming july 8, 2019 16 / 1 matrix chain multiplication matrix multiplication: the product c = ab of a p × q matrix a and a q × r matrix b is a p × r matrix given by c[i, j] = ∑q k=1 a[i, k ]b[k , j] for 1 ≤ i ≤ p and 1 ≤ j ≤ r . if ab is defined, ba may not be defined. multiplication is recursively defined by a1a2a3 . . .as−1as = a1(a2(a3 . . . (as−1as))) matrix multiplication is associative , e.g a1a2a3 = (a1a2)a3 = a1(a2a3)), so parenthesization does not change result. cmpe 250 dynamic programming july 8, 2019 17 / 1 matrix chain multiplication problem definition: given dimensions p0, p1, . . . , pn, corresponding to matrix sequence a1,a2, . . . ,an, where ai has dimension pi−1 × pi , find the most efficient way to multiply these matrices together. the problem is not to actually to perform the multiplications, but merely to decide in which order to perform the multiplications. many options to multiply a chain of matrices because matrix multiplication is associative. the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. for example, suppose a is a 10× 30 matrix, b is a 30× 5 matrix, and c is a 5× 60 matrix. then, (ab)c = (10× 30× 5) + (10× 5× 60) = 1500 + 3000 = 4500 operations a(bc) = (30× 5× 60) + (10× 30× 60) = 9000 + 18000 = 27000 operations. cmpe 250 dynamic programming july 8, 2019 18 / 1 properties of matrix chain multiplication (i) optimal substructure: a simple solution is to place parenthesis at all possible places, calculate the cost for each placement and return the minimum value. in a chain of matrices of size n, we can place the first set of parenthesis in n − 1 ways. for example, if the given chain consists of 4 matrices, assuming the chain to be abcd, then there are 3 ways to place the first set of parenthesis outer side: (a)(bcd), (ab)(cd) and (abc)(d). so when we place a set of parenthesis, we divide the problem into subproblems of smaller size. therefore, the problem has the optimal substructure property and can be easily solved using recursion. minimum number of multiplication needed to multiply a chain of size n = minimum of all n-1 placements (these placements create subproblems of smaller size). cmpe 250 dynamic programming july 8, 2019 19 / 1 properties of matrix chain multiplication (ii) overlapping subproblems: time complexity of the naive recursive approach is exponential. it should be noted that this function computes the same subproblems again and again. consider the following recursion tree for a matrix chain of size 4. the function matrixchainorder(p, 3, 3) is called four times. since the same subproblems are called again, this problem has the overlapping subproblems property. so matrix chain multiplication problem has both properties of a dynamic programming problem. recomputations of the same subproblems can be avoided by constructing a temporary array in bottom up manner. cmpe 250 dynamic programming july 8, 2019 20 / 1 developing a dynamic programming algorithm step 1: determine the structure of an optimal solution (in this case, a parenthesization). decompose the problem into subproblems: for each pair 1 ≤ i ≤ j ≤ n, determine the multiplication sequence for ai..j = aiai+1 . n;="" i++)="" {="" newfib="prevFib1" +="" prevfib2;="" prevfib1="prevFib2;" prevfib2="newFib;" }="" return="" prevfib2;="" }="" time="" complexity:="" o(n)="" extra="" space:="" o(1)="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 8="" 1="" why="" the="" term="" "dynamic="" programming"="" the="" origin="" of="" the="" term="" dynamic="" programming="" has="" very="" little="" to="" do="" with="" writing="" code.="" it="" was="" first="" coined="" by="" richard="" bellman="" in="" the="" 1950s,="" a="" time="" when="" computer="" programming="" was="" practiced="" by="" so="" few="" people="" as="" to="" not="" even="" deserve="" a="" name.="" at="" the="" time,="" programming="" meant="" planning,="" and="" dynamic="" programming="" was="" developed="" to="" optimally="" plan="" multistage="" processes.="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 9="" 1="" properties="" of="" problems="" that="" can="" be="" solved="" using="" dynamic="" programming="" dynamic="" programming="" is="" an="" algorithmic="" paradigm="" that="" solves="" a="" given="" complex="" problem="" by="" breaking="" it="" into="" subproblems="" and="" stores="" the="" results="" of="" subproblems="" to="" avoid="" computing="" the="" same="" results="" again.="" the="" two="" main="" properties="" of="" a="" problem="" that="" suggest="" that="" the="" given="" problem="" can="" be="" solved="" using="" dynamic="" programming="" are:="" 1="" overlapping="" subproblems="" 2="" optimal="" substructure="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 10="" 1="" overlapping="" subproblems="" property="" dynamic="" programming="" combines="" solutions="" to="" sub-problems.="" dynamic="" programming="" is="" mainly="" used="" when="" solutions="" of="" the="" same="" subproblems="" are="" needed="" again="" and="" again.="" computed="" solutions="" to="" subproblems="" are="" stored="" in="" a="" table="" so="" that="" these="" do="" not="" have="" to="" recomputed.="" example:="" recursive="" version="" of="" fibonacci="" numbers.="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 11="" 1="" storing="" values="" for="" reuse="" there="" are="" two="" different="" ways="" to="" store="" the="" values="" so="" that="" these="" values="" can="" be="" reused:="" memoization="" (top="" down)="" tabulation="" (bottom="" up)="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 12="" 1="" memoization="" the="" memoized="" program="" for="" a="" problem="" is="" similar="" to="" the="" recursive="" version="" with="" a="" small="" modification="" that="" it="" looks="" into="" a="" lookup="" table="" before="" computing="" solutions.="" we="" initialize="" a="" lookup="" array="" with="" all="" initial="" values="" as="" a="" default="" value.="" whenever="" we="" need="" solution="" to="" a="" subproblem,="" we="" first="" look="" into="" the="" lookup="" table.="" if="" the="" precomputed="" value="" is="" there="" then="" we="" return="" that="" value,="" otherwise="" we="" calculate="" the="" value="" and="" put="" the="" result="" in="" lookup="" table="" so="" that="" it="" can="" be="" reused="" later.="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 13="" 1="" tabulation="" the="" tabulated="" program="" for="" a="" given="" problem="" builds="" a="" table="" in="" bottom="" up="" fashion="" and="" returns="" the="" last="" entry="" from="" the="" table.="" starting="" from="" the="" first="" entry,="" all="" entries="" are="" filled="" one="" by="" one.="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 14="" 1="" optimal="" substructure="" property="" a="" given="" problem="" has="" optimal="" substructure="" property="" if="" the="" optimal="" solution="" of="" the="" given="" problem="" can="" be="" obtained="" by="" using="" optimal="" solutions="" of="" its="" subproblems.="" example:="" the="" shortest="" path="" problem="" has="" the="" following="" optimal="" substructure="" property:="" if="" a="" vertex="" x="" lies="" in="" the="" shortest="" path="" from="" a="" source="" vertex="" u="" to="" destination="" vertex="" v="" then="" the="" shortest="" path="" from="" u="" to="" v="" is="" the="" combination="" of="" the="" shortest="" path="" from="" u="" to="" x="" and="" the="" shortest="" path="" from="" x="" to="" v="" .="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 15="" 1="" common="" subproblems="" finding="" the="" right="" subproblem="" takes="" creativity="" and="" experimentation.="" but="" there="" are="" a="" few="" standard="" choices="" that="" seem="" to="" arise="" repeatedly="" in="" dynamic="" programming.="" the="" input="" is="" x1,="" x2,="" .="" .="" .="" ,="" xn="" and="" a="" subproblem="" is="" x1,="" x2,="" .="" .="" .="" ,="" xi="" .="" the="" number="" of="" subproblems="" is="" therefore="" linear.="" the="" input="" is="" x1,="" .="" .="" .="" ,="" xn,="" and="" y1,="" .="" .="" .="" ,="" ym.="" a="" subproblem="" is="" x1,="" .="" .="" .="" ,="" xi="" and="" y1,="" .="" .="" .="" ,="" yj="" .="" |x1="" x2="" x3="" x4="" x5="" x6|="" x7="" x8="" x9="" x10="" |y1="" y2="" y3="" y4="" y5|="" x6="" x7="" x8="" the="" number="" of="" subproblems="" is="" o(mn).="" the="" input="" is="" x1,="" .="" .="" .="" ,="" xn="" and="" a="" subproblem="" is="" xi="" ,="" xi+1,="" .="" .="" .="" ,="" xj="" .="" x1="" x2="" |x3="" x4="" x5="" x6|="" x7="" x8="" x9="" x10="" the="" number="" of="" subproblems="" is="" o(n2).="" the="" input="" is="" a="" rooted="" tree.="" a="" subproblem="" is="" a="" rooted="" subtree.="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 16="" 1="" matrix="" chain="" multiplication="" matrix="" multiplication:="" the="" product="" c="AB" of="" a="" p="" ×="" q="" matrix="" a="" and="" a="" q="" ×="" r="" matrix="" b="" is="" a="" p="" ×="" r="" matrix="" given="" by="" c[i,="" j]="∑q" k="1" a[i,="" k="" ]b[k="" ,="" j]="" for="" 1="" ≤="" i="" ≤="" p="" and="" 1="" ≤="" j="" ≤="" r="" .="" if="" ab="" is="" defined,="" ba="" may="" not="" be="" defined.="" multiplication="" is="" recursively="" defined="" by="" a1a2a3="" .="" .="" .as−1as="A1(A2(A3" .="" .="" .="" (as−1as)))="" matrix="" multiplication="" is="" associative="" ,="" e.g="" a1a2a3="(A1A2)A3" =="" a1(a2a3)),="" so="" parenthesization="" does="" not="" change="" result.="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 17="" 1="" matrix="" chain="" multiplication="" problem="" definition:="" given="" dimensions="" p0,="" p1,="" .="" .="" .="" ,="" pn,="" corresponding="" to="" matrix="" sequence="" a1,a2,="" .="" .="" .="" ,an,="" where="" ai="" has="" dimension="" pi−1="" ×="" pi="" ,="" find="" the="" most="" efficient="" way="" to="" multiply="" these="" matrices="" together.="" the="" problem="" is="" not="" to="" actually="" to="" perform="" the="" multiplications,="" but="" merely="" to="" decide="" in="" which="" order="" to="" perform="" the="" multiplications.="" many="" options="" to="" multiply="" a="" chain="" of="" matrices="" because="" matrix="" multiplication="" is="" associative.="" the="" order="" in="" which="" we="" parenthesize="" the="" product="" affects="" the="" number="" of="" simple="" arithmetic="" operations="" needed="" to="" compute="" the="" product,="" or="" the="" efficiency.="" for="" example,="" suppose="" a="" is="" a="" 10×="" 30="" matrix,="" b="" is="" a="" 30×="" 5="" matrix,="" and="" c="" is="" a="" 5×="" 60="" matrix.="" then,="" (ab)c="(10×" 30×="" 5)="" +="" (10×="" 5×="" 60)="1500" +="" 3000="4500" operations="" a(bc)="(30×" 5×="" 60)="" +="" (10×="" 30×="" 60)="9000" +="" 18000="27000" operations.="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 18="" 1="" properties="" of="" matrix="" chain="" multiplication="" (i)="" optimal="" substructure:="" a="" simple="" solution="" is="" to="" place="" parenthesis="" at="" all="" possible="" places,="" calculate="" the="" cost="" for="" each="" placement="" and="" return="" the="" minimum="" value.="" in="" a="" chain="" of="" matrices="" of="" size="" n,="" we="" can="" place="" the="" first="" set="" of="" parenthesis="" in="" n="" −="" 1="" ways.="" for="" example,="" if="" the="" given="" chain="" consists="" of="" 4="" matrices,="" assuming="" the="" chain="" to="" be="" abcd,="" then="" there="" are="" 3="" ways="" to="" place="" the="" first="" set="" of="" parenthesis="" outer="" side:="" (a)(bcd),="" (ab)(cd)="" and="" (abc)(d).="" so="" when="" we="" place="" a="" set="" of="" parenthesis,="" we="" divide="" the="" problem="" into="" subproblems="" of="" smaller="" size.="" therefore,="" the="" problem="" has="" the="" optimal="" substructure="" property="" and="" can="" be="" easily="" solved="" using="" recursion.="" minimum="" number="" of="" multiplication="" needed="" to="" multiply="" a="" chain="" of="" size="" n="Minimum" of="" all="" n-1="" placements="" (these="" placements="" create="" subproblems="" of="" smaller="" size).="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 19="" 1="" properties="" of="" matrix="" chain="" multiplication="" (ii)="" overlapping="" subproblems:="" time="" complexity="" of="" the="" naive="" recursive="" approach="" is="" exponential.="" it="" should="" be="" noted="" that="" this="" function="" computes="" the="" same="" subproblems="" again="" and="" again.="" consider="" the="" following="" recursion="" tree="" for="" a="" matrix="" chain="" of="" size="" 4.="" the="" function="" matrixchainorder(p,="" 3,="" 3)="" is="" called="" four="" times.="" since="" the="" same="" subproblems="" are="" called="" again,="" this="" problem="" has="" the="" overlapping="" subproblems="" property.="" so="" matrix="" chain="" multiplication="" problem="" has="" both="" properties="" of="" a="" dynamic="" programming="" problem.="" recomputations="" of="" the="" same="" subproblems="" can="" be="" avoided="" by="" constructing="" a="" temporary="" array="" in="" bottom="" up="" manner.="" cmpe="" 250="" dynamic="" programming="" july="" 8,="" 2019="" 20="" 1="" developing="" a="" dynamic="" programming="" algorithm="" step="" 1:="" determine="" the="" structure="" of="" an="" optimal="" solution="" (in="" this="" case,="" a="" parenthesization).="" decompose="" the="" problem="" into="" subproblems:="" for="" each="" pair="" 1="" ≤="" i="" ≤="" j="" ≤="" n,="" determine="" the="" multiplication="" sequence="" for="" ai..j="AiAi+1">
Answered Same DayAug 21, 2021

Answer To: Dynamic Programming Dynamic Programming July 8, 2019 CMPE 250 Dynamic Programming July 8, 2019 1 / 1...

Swapnil answered on Aug 22 2021
139 Votes
#include
#include
using namespace std;
string mod(long long l, string cur)
{

    if(l < 0)
    {
        return "";
    }
    if(l == 0)
    {
        return cur;
    }
    string tmp = mod(l >> 1, cur);
    if(tmp.length() != 0)
    {
        tmp ="(" + tmp + ")";
    }
    if(l & 1)
    {
        tmp +=...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here