Dynamic Programming for the Rod-Cutting Problem in Algorithm Analysis" (64 characters)

comp 550 algorithm and analysis n.w
1 / 33
Embed
Share

Learn about the Rod-Cutting Problem in dynamic programming based on CLRS (Introduction to Algorithms). Understand the recursive structure, recursive algorithm, and bottom-up DP approach to maximize revenue. Walk through the iterative table-filling process and explore the time complexity. (293 characters)

  • Algorithm
  • Dynamic Programming
  • Rod-Cutting
  • Analysis
  • Programming (Maximum 5 tags)
rayaanacharya
tal_del Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. COMP 550 Algorithm and Analysis Dynamic Programming Based on CLRS Sec. 14

  2. The Rod-Cutting Problem Buy long rods, cut them into shorter rods, and sell them Input: a rod of length n, a list of prices ? = {?1,?2, ,??} (??denotes the price of length-i rod) Output: The maximum achievable revenue (and corresponding rod cuts) length ? price ?? 1 1 2 5 3 8 4 9 5 10 6 17 7 17 8 9 10 30 20 24 8 ways to cut a rod of length 4 (from CLRS) COMP550@UNC 2

  3. Determine a Recursive Structure Let ???(?) be the maximum revenue of cutting a rod of length ? Express ???(?) w.r.t smaller ???( ) and ?? values ??? ? 1 + ?1 ??? ? 2 + ?2 . . . ??? 0 + ?? ?1 ???(? 1) ??? ? = ??? ?1 ???(? 2) ???(0) ?? COMP550@UNC 3

  4. Recursive Algorithm ?(?): Recursive calls made for given value of ?. ? 1 ? ? = 1 + ?(?) ?=0 ? ? = 2? COMP550@UNC 4

  5. Bottom-Up DP What should be the table dimension and size? 1D array: ???[0:?] What are the base cases? ??? 0 = 0 No price to sell 0-length rod. 0 Length i Cut(i) 1 2 3 4 5 6 7 8 9 10 0 COMP550@UNC 5

  6. Bottom-Up DP Fill up the table iteratively using the recurrence relation length ? price ?? 1 1 2 5 3 8 4 9 5 10 6 17 7 17 8 9 10 30 20 24 ??? 1 = max(??? 0 + ?1) 0 Length i Cut(i) 1 1 2 3 4 5 6 7 8 9 10 0 COMP550@UNC 6

  7. Bottom-UP DP Fill up the table iteratively using the recurrence relation length ? price ?? 1 1 2 5 3 8 4 9 5 10 6 17 7 17 8 9 10 30 20 24 ??? 2 = max(??? 1 + ?1,??? 0 + ?2) 0 Length i Cut(i) 1 1 2 5 3 4 5 6 7 8 9 10 0 COMP550@UNC 7

  8. Bottom-UP DP Fill up the table iteratively using the recurrence relation length ? price ?? 1 1 2 5 3 8 4 9 5 10 6 17 7 17 8 9 10 30 20 24 ??? 3 = max(??? 2 + ?1,??? 1 + ?2,??? 0 + ?3) 0 Length i Cut(i) 1 1 2 5 3 4 5 6 7 8 9 10 0 8 COMP550@UNC 8

  9. Bottom-UP DP The inner loop executes for 1+2+ +n times Running Time: (?2) COMP550@UNC 9

  10. Determining Rod Cuts Determine the rod lengths that produce the maximum revenue Two ways: Store the best cut for each length (one additional table needed) Trace back the computation to determine the best cut COMP550@UNC 10

  11. Determining Rod Cuts COMP550@UNC 11

  12. Longest Common Subsequence (LCS) Input: Two sequences, ? = ?1, ,?? and ? = ?1, ,?? Output: A common subsequence of ? and ? whose length is the maximum. springtime ncaa tournament basketball printing north carolina krzyzewski Subsequence need not be consecutive but must be in order COMP550@UNC 12

  13. Longest Common Subsequence (LCS) Application: Measuring similarity between DNA sequences of different organisms DNA sequences for with letters: A, T, C, G Source: https://medlineplus.gov/geneti cs/understanding/basics/dna/ COMP550@UNC 13

  14. Nave Algorithm For every subsequence of X, check whether it s a subsequence of Y . Running Time: (?2?). 2msubsequences of X to check. Each subsequence takes (n)time to check: scan Y for first letter, for second, and so on COMP550@UNC 14

  15. Determine A Recursive Structure Let ?[?,?] be the length of the LCS of ??= ?1, ,?? and ??= ?1, ,?? ?? is a prefix of ? Can we express ?[?,?] w.r.t ?[ , ] of smaller sequences? A T A G A A T A G A C ?? 1 ?? + 1 c c = ?? 1 ?? A T A T C If ??= ??, then LCS of ?? and ?? must end in ?? and ?[?,?] = ?[? 1,? 1] + 1 COMP550@UNC 15

  16. Determine A Recursive Structure Let ?[?,?] be the length of the LCS of ??= ?1, ,?? and ??= ?1, ,?? ?? is a prefix of ? A T A G A ?? 1 c A T C T ?? A T A G A C ?? max c = ?? A T C T A T A G A C ?? c A T C ?? 1 If ?? ??, then The end of LCS is either ?? or ??, and ? ?,? = max(? ? 1,? ,? ?,? 1 ) COMP550@UNC 16

  17. Determine A Recursive Structure Let ?[?,?] be the length of the LCS of ??= ?1, ,?? and ??= ?1, ,?? ?? is a prefix of ? A T A G A C ?? = 0 c ?? Empty string If ? = 0 or ? = 0, then ? ?,? = 0 COMP550@UNC 17

  18. Determine A Recursive Structure Let ?[?,?] be the length of the LCS of ??= ?1, ,?? and ??= ?1, ,?? ?? is a prefix of ? , if ? = 0 or ? = 0 0 , if ??= ?? ?[?,?] = ? ? 1,? 1 + 1 max(? ? 1,? ,? ?,? 1 ), if ?? ?? COMP550@UNC 18

  19. Determine A Recursive Structure Optimal substructure property We can give the following theorem based on the same idea CLRS gives this Theorem before providing the recursive solution Theorem Let Z = z1, . . . , zk be any LCS of X and Y. 1. If xm= yn, then zk= xm= ynand Zk-1 is an LCS of Xm-1 and Yn-1. 2. If xm yn, then either zk xmand Z is an LCS of Xm-1 and Y . 3. or zk ynand Z is an LCS of X and Yn-1. Please go through the proof before next class and let me know if we need to cover this in class COMP550@UNC 19

  20. Bottom-Up DP ?[?,?]: length of the LCS of ??= ?1, ,?? and ??= ?1, ,?? The original sequences are ? = ?1, ,?? and ? = ?1, ,?? So, our goal is to determine ?[?,?] What should be our table dimension and size? 2D table c[0:m,0:n] COMP550@UNC 20

  21. Bottom-Up DP ?[?,?]: length of the LCS of ??= ?1, ,?? and ??= ?1, ,?? From recurrence, the base case is when i=0 or j=0 C T G A G ? 3 0 1 2 4 5 ? 0 0 0 0 0 0 0 1 2 0 A T 0 0 3 4 C G 0 COMP550@UNC 21

  22. Bottom-Up DP ?[?,?]: length of the LCS of ??= ?1, ,?? and ??= ?1, ,?? Which order should the table be populated? (What are the dependencies?) C T G A G ? 3 0 1 2 4 5 ? 0 0 0 0 0 0 0 1 2 0 A T 0 0 3 4 C G 0 COMP550@UNC 22

  23. Bottom-Up DP LCS-LENGTH (X, Y) 1. m= length[X] 2. n= length[Y] 3. for i = 1 to m 4. c[i,0] = 0 5. for j = 0 to n 6. c[0,j] = 0 7. for i = 1 to m 8. for j 1 to n 9. 10. c[i, j ] c[i 1, j 1] + 1 11. b[i, j ] 12. else if c[i 1, j ] c[i, j 1] 13. c[i, j ] c[i 1, j ] 14. b[i, j ] 15. else 16. c[i, j ] c[i, j 1] 17. b[i, j ] 18. return c and b ?[?,?] points to table entry whose subproblem we used in solving LCS of Xi and Yj. c[m,n] contains the length of an LCS of X and Y. Running Time: (? ?) if xi= yj COMP550@UNC 23

  24. Bottom-Up DP LCS-LENGTH (X, Y) 1. m= length[X] 2. n= length[Y] 3. for i = 1 to m 4. c[i,0] = 0 5. for j = 0 to n 6. c[0,j] = 0 7. for i = 1 to m 8. for j 1 to n 9. 10. c[i, j ] c[i 1, j 1] + 1 11. b[i, j ] 12. else if c[i 1, j ] c[i, j 1] 13. c[i, j ] c[i 1, j ] 14. b[i, j ] 15. else 16. c[i, j ] c[i, j 1] 17. b[i, j ] 18. return c and b C T G A G ? 3 0 1 2 4 5 ? if xi= yj 0 0 0 0 0 0 0 1 2 0 A T 0 0 3 4 C G 0 COMP550@UNC 24

  25. Bottom-Up DP LCS-LENGTH (X, Y) 1. m= length[X] 2. n= length[Y] 3. for i = 1 to m 4. c[i,0] = 0 5. for j = 0 to n 6. c[0,j] = 0 7. for i = 1 to m 8. for j 1 to n 9. 10. c[i, j ] c[i 1, j 1] + 1 11. b[i, j ] 12. else if c[i 1, j ] c[i, j 1] 13. c[i, j ] c[i 1, j ] 14. b[i, j ] 15. else 16. c[i, j ] c[i, j 1] 17. b[i, j ] 18. return c and b C T G A G ? 3 0 1 2 4 5 ? if xi= yj 0 0 0 0 0 0 0 1 2 0 A T 0 0 0 3 4 C G 0 COMP550@UNC 25

  26. Bottom-Up DP LCS-LENGTH (X, Y) 1. m= length[X] 2. n= length[Y] 3. for i = 1 to m 4. c[i,0] = 0 5. for j = 0 to n 6. c[0,j] = 0 7. for i = 1 to m 8. for j 1 to n 9. 10. c[i, j ] c[i 1, j 1] + 1 11. b[i, j ] 12. else if c[i 1, j ] c[i, j 1] 13. c[i, j ] c[i 1, j ] 14. b[i, j ] 15. else 16. c[i, j ] c[i, j 1] 17. b[i, j ] 18. return c and b C T G A G ? 3 0 1 2 4 5 ? if xi= yj 0 0 0 0 0 0 0 1 2 0 0 A T 0 0 0 3 4 C G 0 COMP550@UNC 26

  27. Bottom-Up DP LCS-LENGTH (X, Y) 1. m= length[X] 2. n= length[Y] 3. for i = 1 to m 4. c[i,0] = 0 5. for j = 0 to n 6. c[0,j] = 0 7. for i = 1 to m 8. for j 1 to n 9. 10. c[i, j ] c[i 1, j 1] + 1 11. b[i, j ] 12. else if c[i 1, j ] c[i, j 1] 13. c[i, j ] c[i 1, j ] 14. b[i, j ] 15. else 16. c[i, j ] c[i, j 1] 17. b[i, j ] 18. return c and b C T G A G ? 3 0 1 2 4 5 ? if xi= yj 0 0 0 0 0 0 0 1 2 0 0 0 A T 0 0 0 3 4 C G 0 COMP550@UNC 27

  28. Bottom-Up DP LCS-LENGTH (X, Y) 1. m= length[X] 2. n= length[Y] 3. for i = 1 to m 4. c[i,0] = 0 5. for j = 0 to n 6. c[0,j] = 0 7. for i = 1 to m 8. for j 1 to n 9. 10. c[i, j ] c[i 1, j 1] + 1 11. b[i, j ] 12. else if c[i 1, j ] c[i, j 1] 13. c[i, j ] c[i 1, j ] 14. b[i, j ] 15. else 16. c[i, j ] c[i, j 1] 17. b[i, j ] 18. return c and b C T G A G ? 3 0 1 2 4 5 ? if xi= yj 0 0 0 0 0 0 0 1 2 0 0 0 A T 0 1 0 0 3 4 C G 0 COMP550@UNC 28

  29. Bottom-Up DP LCS-LENGTH (X, Y) 1. m= length[X] 2. n= length[Y] 3. for i = 1 to m 4. c[i,0] = 0 5. for j = 0 to n 6. c[0,j] = 0 7. for i = 1 to m 8. for j 1 to n 9. 10. c[i, j ] c[i 1, j 1] + 1 11. b[i, j ] 12. else if c[i 1, j ] c[i, j 1] 13. c[i, j ] c[i 1, j ] 14. b[i, j ] 15. else 16. c[i, j ] c[i, j 1] 17. b[i, j ] 18. return c and b C T G A G ? 3 0 1 2 4 5 ? if xi= yj 0 0 0 0 0 0 0 1 2 0 0 0 A T 0 1 1 0 0 3 4 C G 0 COMP550@UNC 29

  30. Bottom-Up DP LCS-LENGTH (X, Y) 1. m= length[X] 2. n= length[Y] 3. for i = 1 to m 4. c[i,0] = 0 5. for j = 0 to n 6. c[0,j] = 0 7. for i = 1 to m 8. for j 1 to n 9. 10. c[i, j ] c[i 1, j 1] + 1 11. b[i, j ] 12. else if c[i 1, j ] c[i, j 1] 13. c[i, j ] c[i 1, j ] 14. b[i, j ] 15. else 16. c[i, j ] c[i, j 1] 17. b[i, j ] 18. return c and b C T G A G ? 3 0 1 2 4 5 ? if xi= yj 0 0 0 0 0 0 0 1 2 0 0 0 A T 0 1 1 0 1 0 3 4 C G 0 COMP550@UNC 30

  31. Bottom-Up DP LCS-LENGTH (X, Y) 1. m= length[X] 2. n= length[Y] 3. for i = 1 to m 4. c[i,0] = 0 5. for j = 0 to n 6. c[0,j] = 0 7. for i = 1 to m 8. for j 1 to n 9. 10. c[i, j ] c[i 1, j 1] + 1 11. b[i, j ] 12. else if c[i 1, j ] c[i, j 1] 13. c[i, j ] c[i 1, j ] 14. b[i, j ] 15. else 16. c[i, j ] c[i, j 1] 17. b[i, j ] 18. return c and b C T G A G ? 3 0 1 2 4 5 ? if xi= yj 0 0 0 0 0 0 0 1 2 0 A T 0 0 0 1 1 0 1 1 1 1 1 0 1 1 2 2 2 3 4 C G 0 1 2 2 2 3 COMP550@UNC 31

  32. Bottom-Up DP PRINT-LCS (b, X, i, j) 1. if i = 0 or j = 0 2. return 3. if b[i, j] = 4. PRINT-LCS(b, X, i 1, j 1) 5. print xi 6. else if b[i, j] = 7. PRINT-LCS(b, X, i 1, j) 8. else 9. PRINT-LCS(b, X, i, j 1) C T G A G ? 3 0 1 2 4 5 ? 0 0 0 0 0 0 0 1 2 0 A T 0 0 0 1 1 0 1 1 1 1 1 0 1 1 2 2 2 3 4 C G 0 1 2 2 2 3 Print: ??? Initial call is PRINT-LCS(b, X, m, n) When b[i, j ] = , we have extended LCS by one character. So LCS = entries with in them Running Time: ?(? + ?) COMP550@UNC 32

  33. Thank You! COMP550@UNC 33

Related


No related presentations.

More Related Content