Dynamic Programming: Longest Increasing Subsequence

dynamic programming even more fun n.w
1 / 78
Embed
Share

"Explore the concept of the longest increasing subsequence problem in dynamic programming with detailed explanations and recursive solutions. Learn how to find and optimize sequences for better performance."

  • Dynamic Programming
  • Subsequence Problem
  • Optimization
  • Recursive Solutions
  • Sequence
rayaanacharya
trin_61 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. DYNAMIC PROGRAMMING: EVEN MORE FUN! David Kauchak CS 140 Fall 2024

  2. Admin Assignment 5 Out later today Due Sunday (extra credit for submitting by Friday) Schedule changes this week soon Will post final schedule No group session for Elshiekh

  3. Longest increasing subsequence Given a sequence of numbers X = x1, x2, , xnfind the longest increasing subsequence (i1, i2, , im), i.e., a subsequence where numbers in the sequence increase. 5 2 8 6 3 6 9 7

  4. Longest increasing subsequence Given a sequence of numbers X = x1, x2, , xn find the longest increasing subsequence (i1, i2, , im), i.e., a subsequence where numbers in the sequence increase. 5 2 8 6 3 6 9 7

  5. Recursive solution 5 2 8 6 3 6 9 7 Is 5 part off the LIS?

  6. Recursive solution 5 2 8 6 3 6 9 7 Two options: Either 5 is in the LIS or it s not

  7. Recursive solution 5 2 8 6 3 6 9 7 include 5 5 + LIS(8 6 3 6 9 7)

  8. Recursive solution 5 2 8 6 3 6 9 7 include 5 5 + LIS(8 6 3 6 9 7) What is this function exactly? longest increasing sequence of the numbers longest increasing sequence of the numbers starting with 8

  9. Recursive solution 5 2 8 6 3 6 9 7 include 5 5 + LIS(8 6 3 6 9 7) What is this function exactly? This would allow for the option of sequences starting with 3 which are NOT valid! longest increasing sequence of the numbers

  10. Recursive solution 5 2 8 6 3 6 9 7 include 5 5 + LIS (8 6 3 6 9 7) longest increasing sequence of the numbers starting with 8 Do we need to consider anything else for subsequences starting at 5?

  11. Recursive solution 5 2 8 6 3 6 9 7 include 5 5 + LIS (8 6 3 6 9 7) 5 + LIS (6 3 6 9 7) 5 + LIS (6 9 7) 5 + LIS (9 7) 5 + LIS (7)

  12. Recursive solution 5 2 8 6 3 6 9 7 don t include 5 LIS(2 8 6 3 6 9 7) Anything else? Technically, this is fine, but now we have LIS and LIS to worry about. Can we rewrite LIS in terms of LIS ?

  13. Recursive solution = ( ) max i { ( ' )} LIS X LIS i Longest increasing sequence for X is the longest increasing sequence starting at any element And what is LIS defined as (recursively)?

  14. Recursive solution = ( ) max i { ( ' )} LIS X LIS i Longest increasing sequence for X is the longest increasing sequence starting at any element ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max Longest increasing sequence starting at i

  15. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max LIS : 5 2 8 6 3 6 9 7

  16. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max LIS : 1 5 2 8 6 3 6 9 7

  17. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max LIS : 1 5 2 8 6 3 6 9 7

  18. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max LIS : 1 1 5 2 8 6 3 6 9 7

  19. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max LIS : 1 1 5 2 8 6 3 6 9 7

  20. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max LIS : 2 1 1 5 2 8 6 3 6 9 7

  21. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max LIS : 3 2 1 1 5 2 8 6 3 6 9 7

  22. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max LIS : 2 3 2 1 1 5 2 8 6 3 6 9 7

  23. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max LIS : 2 2 3 2 1 1 5 2 8 6 3 6 9 7

  24. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max LIS : 4 2 2 3 2 1 1 5 2 8 6 3 6 9 7

  25. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max LIS : 3 4 2 2 3 2 1 1 5 2 8 6 3 6 9 7

  26. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max LIS : 3 4 2 2 3 2 1 1 5 2 8 6 3 6 9 7 = ( ) max i { ( ' )} LIS X LIS i

  27. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max What does the table for storing answers look like?

  28. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max 1-D array: only one thing changes for recursive calls

  29. DP solution (bottom-up) ??? ? = 1 + ?: ?<? ? ??? ??>????? (?) max What are the smallest possible subproblems? To calculate LIS (n), what are all the subproblems we need to calculate? This is the table . How should we fill in the table? Where will the answer be?

  30. DP solution (bottom-up) ??? ? = 1 + ?:?<? ? ??? ??>????? (?) max What are the smallest possible subproblems? LIS (n) and that is well-defined for this problem To calculate LIS (i), what are all the subproblems we need to calculate? This is the table . LIS (1) LIS (n) How should we fill in the table? n 1 Where will the answer be? max(LIS (1) LIS (n))

  31. DP solution (bottom-up)

  32. DP solution (bottom-up) start from the end (bottom)

  33. DP solution (bottom-up) ??? ? = 1 + ?:?<? ? ??? ??>????? (?) max

  34. DP solution (bottom-up) = ( ) max i { ( ' )} LIS X LIS i

  35. Analysis Space requirements? Running time?

  36. Analysis Space requirements: (n) Running time: (n2)

  37. Another solution Can we use LCS to solve this problem? 5 2 8 6 3 6 9 7 LCS 2 3 5 6 6 7 8 9

  38. Another solution Can we use LCS to solve this problem? 5 2 8 6 3 6 9 7 LCS 2 3 5 6 6 7 8 9

  39. Edit distance (aka Levenshtein distance) Edit distance between two strings is the minimum number of insertions, deletions and substitutions required to transform string s1 into string s2 Insertion: ABACED ABACCED DABACCED Insert C Insert D

  40. Edit distance (aka Levenshtein distance) Edit distance between two strings is the minimum number of insertions, deletions and substitutions required to transform string s1 into string s2 Deletion: ABACED

  41. Edit distance (aka Levenshtein distance) Edit distance between two strings is the minimum number of insertions, deletions and substitutions required to transform string s1 into string s2 Deletion: ABACED BACED Delete A

  42. Edit distance (aka Levenshtein distance) Edit distance between two strings is the minimum number of insertions, deletions and substitutions required to transform string s1 into string s2 Deletion: ABACED BACED BACE Delete A Delete D

  43. Edit distance (aka Levenshtein distance) Edit distance between two strings is the minimum number of insertions, deletions and substitutions required to transform string s1 into string s2 Substitution: ABACED ABADED ABADES Sub D for C Sub S for D

  44. Edit distance examples Edit(Kitten, Mitten) = 1 Operations: Mitten Sub M for K

  45. Edit distance examples Edit(Happy, Hilly) = 3 Operations: Hippy Sub a for i Hilpy Sub l for p Hilly Sub l for p

  46. Edit distance examples Edit(Banana, Car) = 5 Operations: anana Delete B nana Delete a naa Delete n Caa Sub C for n Car Sub a for r

  47. Edit distance examples Edit(Simple, Apple) = 3 Operations: imple Delete S Ample Sub A for i Sub m for p Apple

  48. Edit distance Why might this be useful?

  49. Is edit distance symmetric? that is, is Edit(s1, s2) = Edit(s2, s1)? Edit(Simple, Apple) =? Edit(Apple, Simple) Why? sub i for j sub j for i delete i insert i insert i delete i

  50. Calculating edit distance X = A B C B D A B Y = B D C A B A Ideas? How can we break this into subproblems?

Related


No related presentations.

More Related Content