Dynamic programming algorithm

dynamic programming bioinformatics and dynamic programming code generation algorithm
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
ECE 250 Algorithms and Data Structures Dynamic Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering programming University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Dynamic programming 2 Dynamic programming To begin, the word programming is used by mathematicians to describe a set of rules which must be followed to solve a problem – Thus, linear programming describes sets of rules which must be solved a linear problem – In our context, the adjective dynamic describes how the set of rules worksDynamic programming 3 Outline We will begin by looking at two problems: – Fibonacci numbers – Newton polynomial coefficients – Determining connectedness in a DAG We will examine the naïve top-down approach – We will implement the naïve top-down approach – We will discuss the run-times of these algorithms – We will consider the application of memoization – We will discuss the benefits of a bottom-up approachDynamic programming 4 Fibonacci numbers Consider this function: double F( int n ) return ( n = 1 ) ? 1.0 : F(n - 1) + F(n - 2); The run-time of this algorithm is  (1) n 1  T n   T n1 T n 2(1) n1  Dynamic programming 5 Fibonacci numbers Consider this function calculating Fibonacci numbers: double F( int n ) return ( n = 1 ) ? 1.0 : F(n - 1) + F(n - 2); The runtime is similar to the actual definition of Fibonacci numbers:  (1) n 1  11 n  T n   Fn   T n1 T n 2(1) n1  F n1 F n 21 n1    n Therefore, T(n) = W(F(n)) = W(f ) Tn  n lim 2 – In actual fact, T(n) = (f ), only n  Fn Dynamic programming 6 Fibonacci numbers To demonstrate, consider: double F( int n ) include iostream return ( n = 1 ) ? 1.0 : F(n - 1) + F(n - 2); include ctime using namespace std; int main() cout.precision( 16 ); // print 16 decimal digits of precision for doubles // 53/lg(10) = 15.95458977... for ( int i = 33; i 100; ++i ) cout "F(" i ") = " F(i) '\t' time(0) endl; return 0; Dynamic programming 7 Fibonacci numbers The output:  F(33) = 5702887 1206474355  F(34) = 9227465 1206474355 F(33), F(34), and F(35) in 1 s   F(35) = 14930352 1206474355  F(36) = 24157817 1206474356 F(37) = 39088169 1206474358 F(38) = 63245986 1206474360 F(39) = 102334155 1206474363 F(40) = 165580141 1206474368 F(41) = 267914296 1206474376 F(42) = 433494437 1206474389 F(43) = 701408733 1206474411 F(44) = 1134903170 1206474469 1 min to calculate F(44)Dynamic programming 8 Fibonacci numbers Problem: – To calculate F(44), it is necessary to calculate F(43) and F(42) – However, to calculate F(43), it is also necessary to calculate F(42) – It gets worse, for example • F(40) is called 5 times • F(30) is called 620 times • F(20) is called 75 025 times • F(10) is called 9 227 465 times • F(0) is called 433 494 437 times Surely we don’t have to recalculate F(10) almost ten million times…Dynamic programming 9 Fibonacci numbers Here is a possible solution: – To avoid calculating values multiple times, store intermediate calculations in a table – When storing intermediate results, this process is called memoization • The root is memo – We save (memoize) computed answers for possible later reuse, rather than re-computing the answer multiple timesDynamic programming 10 Fibonacci numbers Once we have calculated a value, can we not store that value and return it if a function is called a second time? – One solution: use an array – Another: use an associative hash tableDynamic programming 11 Fibonacci numbers static const int ARRAY_SIZE = 1000; double array = new doubleARRAY_SIZE; array0 = 1.0; array1 = 1.0; // use 0.0 to indicate we have not yet calculated a value for ( int i = 2; i ARRAY_SIZE; ++i ) arrayi = 0.0; double F( int n ) if ( arrayn == 0.0 ) arrayn = F( n – 1 ) + F( n – 2 ); return arrayn; Dynamic programming 12 Fibonacci numbers Recall the characteristics of an associative container: template typename S, typename T class Hash_table public: // is something stored with the given key? bool member( S key ) const; // returns value associated with the inserted key T retrieve( S key ) const; void insert( S key, T value ); // ... ; Dynamic programming 13 Fibonacci numbers This program uses the Standard Template Library: include map / calculate the nth Fibonacci number / double F( int n ) static std::mapint, double memo; // shared by all calls to F // the key is int, the value is double if ( n = 1 ) return 1.0; else if ( memon == 0.0 ) memon = F(n - 1) + F(n - 2); return memon; Dynamic programming 14 Fibonacci numbers This prints the output up to F(1476): int main() std::cout.precision( 16 ); for ( int i = 0; i 1476; ++i ) std::cout "F(" i ") = " F(i) std::endl; return 0; The last two lines are F(1475) = 1.306989223763399e+308 F(1476) = inf Exact value: F(1475) = 13069892237633993180363115538027198309839244390741264072 600665946019279307047923174028868108777701772109546315497901227623432224693693964718536670636 848936266084414744994134846280092275581896963474334898291642495406274413596986561540727649241 0653721774590669544801490837649161732095972658064630033793347171632Dynamic programming 15 Top-down and bottom-up algorithms This also allows for another approach: – Our implementation is top-down – From the very top, we break the problem into sub-problems – All divide-and-conquer algorithms we have seen are top-down An alternative approach is bottom-up approach – Solve smaller problems and use these to build a solution for the problem – Merge sort could be implemented bottom-up: • Divide the array into groups of size m and sort each group with insertion sort • Merge adjacent pairs into groups of size 2m where possible • Repeat this successively until the entire list is sortedDynamic programming 16 Top-down and bottom-up algorithms Here is a bottom-up approach to calculating Fibonacci numbers: double F( int n ) if ( n = 1 ) return 1.0; double a = 1.0, b = 1.0; for ( int i = 2; i = n; ++i ) a += b; b = a - b; return a; Dynamic programming 17 Newton polynomials The coefficient of a Newton polynomial which allows a polynomial of degree n – 1 passing through n points may be calculated by: yy kk ,...,21,...,1 y k,...,1 xx k 1 where k = 1, …, n and the coefficients are defined recursively: yy i,..., j 1 i 1,..., j y ij ,..., xx jk yy jj1 y jj,1 xx jj1Dynamic programming 18 Newton polynomials A recursive implementation for calculating Newton polynomials n coefficients would have a run time of (2 ) double Newton_polynomials( int i, int j, double xs, double ys ) if ( i == j ) return ysi; else if ( i + 1 == j ) return ( ysj – ysi )/( xsj – xsi ); else return ( Newton_polynomials( i + 1, j, xs, ys ) - Newton_polynomials( i, j - 1, xs, ys ) ) / (xsj - xi); Dynamic programming 19 Newton polynomials nn1  Note, however, that there are only coefficients 2 – This shouldn’t require such recursion x y 0 0 y y 1 0 y 1,0 x x 1 0 y y 2,1 1,0 x y 1 1 y 2,1,0 y y x x 2 1 y y 2 0 y 3,2,1 2,1,0 2,1 y 3,2,1,0 x x 2 1 y y x x 3,2 2,1 3 0 x y y 2 2 3,2,1 y y 3 2 x x 3 1 y 3,2 x x 3 2 x y 3 3Dynamic programming 20 Newton polynomials Here is an array-based implementation: include cmath static const int ARRAY_SIZE = 1000; double array = new doubleARRAY_SIZEARRAY_SIZE; for ( int i = 0; i ARRAY_SIZE; ++i ) for ( int j = 0; j ARRAY_SIZE; ++j ) arrayij = nan( "" ); double Newton_polynomials( int i, int j, double xs, double ys ) if ( i == j ) return ysi; else if ( i + 1 == j ) return ( ysj – ysi )/( xsj – xsi ); else if ( isnan( arrayij ) arrayij = ( Newton_polynomials( i + 1, j, xs, ys ) - Newton_polynomials( i, j - 1, xs, ys ) ) / (xsj - xi); return arrayij;