# Chapter 2: Using Objects

RAIK 283: Data Structures & Algorithms Dynamic Programming Computing Binomial Coefficient and Longest Common Subsequence Dr. Ying Lu [email protected] 1 RAIK 283: Data Structures & Algorithms Giving credit where credit is due: Most of the lecture notes are based on the slides from the Textbooks companion website http://www.aw-bc.com/info/levitin Some of the notes are based on slides by Dr. Tao Jiang at University of California - Riverside I have modified many of their slides and added new slides 2 Dynamic programming Dynamic Programming is a general algorithm design technique Invented by American mathematician Richard Bellman in the 1950s to solve optimization problems Programming here means planning Main idea: set up a recurrence relating a solution to a larger instance to solutions of some smaller instances solve smaller instances once record solutions in a table

extract solution to the initial instance from that table 3 Example: Fibonacci numbers Recall definition of Fibonacci numbers: f(0) = 0 f(1) = 1 f(n) = f(n-1) + f(n-2) Computing the nth Fibonacci number recursively (top-down): f(n) f(n-1) f(n-2) ... + + f(n-3) f(n-2) f(n-3) + f(n-4) 4 Example: Fibonacci numbers Computing the nth Fibonacci number using bottom-up iteration: f(0) = 0 f(1) = 1 f(2) = 0+1 = 1 f(3) = 1+1 = 2 f(4) = 1+2 = 3

f(5) = 2+3 = 5 f(n-2) = f(n-1) = f(n) = f(n-1) + f(n-2) 5 Examples of dynamic programming algorithms Coin-row problem Computing binomial coefficients Longest Common Subsequence (LCS) Warshalls algorithm for transitive closure Floyds algorithm for all-pairs shortest paths Some instances of difficult discrete optimization problems: 0-1 knapsack 6 Coin-row problem There is a row of n coins whose values are some positive integers c, c,...,c, c,...,c,...,cn, not necessarily distinct. The goal is to pick up the maximum amount of money subject to the constraint that no two coins adjacent in the initial row can be picked up. E.g.: 5, 1, 2, 10, 6, 2, the best selection is 5, 10, 2, giving the maximum amount of 17. 7 DP solution to the coin-row problem Let F(n) be the maximum amount that can be picked up from the row of n coins. To derive a recurrence for F(n), we partition all

the allowed coin selections into two groups: those without last coin the max amount is ? those with the last coin -- the max amount is ? 8 DP solution to the coin-row problem Let F(n) be the maximum amount that can be picked up from the row of n coins. To derive a recurrence for F(n), we partition all the allowed coin selections into two groups: those without last coin the max amount is ? those with the last coin -- the max amount is ? Thus we have the following recurrence F(n) = max{cn + F(n-2), F(n-1)} for n > 1, F(0) = 0, F(1)=c, c,...,c 9 DP solution to the coin-row problem (cont.) F(n) = max{cn + F(n-2), F(n-1)} for n > 1, F(0) = 0, F(1)=c, c,...,c index coins 0 1 2 3 4 5

6 -- 5 1 2 10 6 2 F( ) Max amount: Coins of optimal solution: Time efficiency: Space efficiency: Note: All smaller instances were solved. 10 Computing a binomial coefficient by DP Binomial coefficients are coefficients of the binomial formula: (a + b)n = C(n,0)anb0 + . . . + C(n,k)an-kbk + . . . + C(n,n)a0bn C(n, k), the number of combinations of k elements from an nelement set (0 k n) Recurrence: C(n,k) = ? Computing a binomial coefficient by DP Binomial coefficients are coefficients of the binomial formula: (a + b)n = C(n,0)anb0 + . . . + C(n,k)an-kbk + . . . + C(n,n)a0bn C(n, k), the number of combinations of k elements from an nelement set (0 k n)

Recurrence: C(n,k) = ? those without last element the number of such combinations is ? those with the last element -- the number of such combinations is ? Computing a binomial coefficient by DP Binomial coefficients are coefficients of the binomial formula: (a + b)n = C(n,0)anb0 + . . . + C(n,k)an-kbk + . . . + C(n,n)a0bn Recurrence: C(n,k) = C(n-1,k) + C(n-1,k-1) for n > k > 0 C(n,0) = 1, C(n,n) = 1 for n 0 Value of C(n,k) can be computed by filling a table: 0 1 2 . . . k-1 k 0 1 1 1 1 . . . n-1 C(n-1,k-1) C(n-1,k) n C(n,k) Computing C(n,k): pseudocode and analysis Time efficiency: ? Space efficiency: ? Computing C(n,k): pseudocode and analysis Time efficiency: (nk) Space efficiency: (nk) In-class exercise

Compute C(6, 3) by applying the dynamic programming algorithm Design and Analysis of Algorithms - Chapter 8 16 In-Class Exercise Several coins are placed in cells of an nm board. A robot, located in the upper left cell of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell. On each step, the robot can move either one cell to the right or one cell down from its current location. 1 2 3 4 5 6 1 2 3 4 5 17 Longest Common Subsequence (LCS)

A subsequence of a sequence/string S is obtained by deleting zero or more symbols from S. For example, the following are some subsequences of president: pred, sdn, predent. In other words, the letters of a subsequence of S appear in order in S, but they are not required to be consecutive. The longest common subsequence problem is to find a maximum length common subsequence between two sequences. LCS For instance, Sequence 1: president Sequence 2: providence Its LCS is priden. president providence LCS Another example: Sequence 1: algorithm Sequence 2: alignment One of its LCS is algm. a l g o r i t h m a l i g n m e n t How to compute LCS?

Let A=a1a2am and B=b1b2bn . len(i, j): the length of an LCS between a1a2ai and b1b2bj How to compute LCS? Let A=a1a2am and B=b1b2bn . len(i, j): the length of an LCS between a1a2ai and b1b2bj With proper initializations, len(i, j) can be computed as follows 0 len ( i , j ) len ( i 1 , j 1 ) 1 max( len ( i , j 1 ), len ( i 1 , j ) if i 0 or j 0 , if i , j 0 and a i b j , if i , j 0 and a i b j . How to compute LCS? Let A=a1a2am and B=b1b2bn . len(i, j): the length of an LCS between a1a2ai and b1b2bj

With proper initializations, len(i, j) can be computed as follows 0 len ( i , j ) len ( i 1 , j 1 ) 1 max( len ( i , j 1 ), len ( i 1 , j ) if i 0 or j 0 , if i , j 0 and a i b j , if i , j 0 and a i b j . What is the corresponding LCS? p r o c e d u r e L C S -L e n g th (A , B ) 1 . f o r i 0 to m d o le n (i,0 ) = 0 2 . f o r j 1 to n d o le n ( 0 ,j) = 0 3 . fo r i 1 to m d o 4. fo r j 1 to n d o len ( i , j ) len ( i 1 , j 1 ) 1 5. if a i b j th e n " prev ( i , j ) " 6. 7. 8. 9. e l s e i f len ( i 1 , j ) len ( i , j 1 ) len ( i , j ) len ( i 1 , j ) th e n

prev ( i , j ) " " len ( i , j ) len ( i , j 1 ) e ls e " prev ( i , j ) " r e tu r n le n a n d p r e v i 0 1 2 3 4 5 6 7 8 9 j p r e s i d e n t 0 1 p

2 r 3 o 4 v 5 i 6 d 7 e 8 n 9 c 10 e 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Running time and memory: O(mn) and O(mn). i 0 1 2 3 4 5 6 7

8 9 j p r e s i d e n t 0 1 p 2 r 3 o 4 v 5 i 6 d 7

e 8 n 9 c 10 e 0 0 0 0 0 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 1 1 0 1 2 2 2 2 2 2 2

2 2 0 1 2 2 2 2 2 3 3 3 3 0 1 2 2 2

2 2 3 3 3 3 0 1 2 2 2 3 3 3 3 3 3 0

1 2 2 2 3 4 4 4 4 4 0 1 2 2 2 3 4 5

5 5 5 0 1 2 2 2 3 4 5 6 6 6 0 1 2 2

2 3 4 5 6 6 6 Running time and memory: O(mn) and O(mn). The backtracing algorithm p r o c e d u r e O u tp u t-L C S (A , p r e v , i, j) 1 if i = 0 o r j = 0 th e n r e tu r n Output LCS ( A , prev , i 1 , j 1 ) 2 if p r e v (i, j)= th e n ai print 3 e ls e if p r e v (i, j)= th e n O u tp u t-L C S (A , p r e v , i-1 , j) 4 e ls e O u tp u t-L C S (A , p r e v , i, j-1 ) i 0

1 2 3 4 5 6 7 8 9 j p r e s i d e n t 0 1 p 2 r 3 o 4 v

5 i 6 d 7 e 8 n 9 c 10 e 0 0 0 0 0 0 0 0 0

0 0 0 1 1 1 1 1 1 1 1 1 1 0 1 2 2 2

2 2 2 2 2 2 0 1 2 2 2 2 2 3 3 3 3 0

1 2 2 2 2 2 3 3 3 3 0 1 2 2 2 3 3 3

3 3 3 0 1 2 2 2 3 4 4 4 4 4 0 1 2 2

2 3 4 5 5 5 5 0 1 2 2 2 3 4 5 6 6 6

0 1 2 2 2 3 4 5 6 6 6 Output: priden In-class exercise Design and Analysis of Algorithms - Chapter 8 29

## Recently Viewed Presentations

• Philippians 2:1-4. Therefore if you have any encouragement from being united with Christ, if any comfort from his love, if any common sharing in the Spirit, if any tenderness and compassion, then make my joy complete by being like-minded, having...
• Formation of Gametes. Meiosis: cell division that produces gametes with half the number of chromosomes that are in the parent cell. Basically, it's the process that takes germ cells (aka sex cells) that have 2 sets of chromosomes and forms...
• PL Toutain Update 6 octobre 2010 Différences interspécifiques dans le développement du côlon 1. Estomac Le gros intestin Valvule iléo-cæcale Valvule iléo-cæcale Valvule iléo-cæcale Les 'lèvres' du côlon et de l'iléon Sphincter épaississement de l'iléon Ouverture favorisée par PN relâchement...
• Autumn Thought by Langston Hughes; Flowers are happy in summer. In autumn they die and are blown away. Dry and withered, Their petals dance on the wind Like little brown butterflies. * Poetry in which authors use both words and...
• Advanced Aero Vehicle Team took 1st place overall in the SAE Aero competition in Fort Worth, Texas over St. Patrick's weekend March 15 - 17, 2013. Baja will be competing April 18 - 21, 2013 in Clarksville, TN, wish them...
• For cube positioned on reflector ???=?⋅? ... Specular highlights. When illuminating the cubes some components depend on the view. The straightforward solution would be to store some SH coefficients for the radiance. Costly. Alternatively, can make all cube-shots produce the...
• Adding Integers with a Common Sign. When adding integers with the same sign, add the absolute values of the integers and use the sign of the integers for the sum. Absolute value refers to the integer's distance from zero on...
• Grand Overview Over consumption will lead to resource scarcity eventually - we are entering this era now but are in complete denial about it What are the consequences: Challenges traditional supply/demand economic models Requires some component of morality based decision...