Advanced Techniques in Dynamic Programming: Algorithms and Applications
Explore the intricate concepts of dynamic programming through examples such as edit distance algorithms, bioinformatics applications, and recursive techniques. Delve into solving subproblems efficiently and optimizing solutions for various scenarios.
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.
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
Dynamic Programming in a nutshell Radu Mariescu-Istodor 24.9.2018
String distance ALGORITHM BIORHYTHM
String distance ALGORITHM BIORHYTHM
String distance ALG BI OR THM OR THM HY I
Used in DNA Sequence Alignment -GGATTACGGGCCCGCTAC- ACTACG-ATTA---G-CC-CTA-T
Three subproblems Edit distance = 42 -GGATTACGGGCCCGCTAC- ACTACG-ATTA---G-CC-CTA-T T A 42 + 1 substitution
Three subproblems Edit distance = 43 -GGATTACGGGCCCGCTAC-- ACTACG-ATTA---G-CC-CTA-T T A 42 + 1 43 + 1 removal
Three subproblems Edit distance = 41 -GGATTACGGGCCCGCTAC ACTACG-ATTA---G-CC-CTA-T T A 42 + 1 43 + 1 41 + 1 Edit distance = min insertion
Three subproblems -GGATTACGGGCCCGCTAC ACTACG-ATTA---G-CC-CTA-T T - A 42 + 1 43 + 1 41 + 1 Edit distance = min = 42
Recursive Algorithm a[m] = b[n] or not edit ( a[1..m], b[1..n] ) if m = 0 return n if n = 0 return m edit( a[1..m-1], b[1..n-1]) + 0/1 edit( a[1..m-1], b[1..n] ) + 1 edit( a[1..m] , b[1..n-1]) + 1 return min
Dynamic Programming Algorithm B I O R H Y T H M 0 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 9 9 8 8 7 6 6 7 6 5 edit ( a[1..m], b[1..n] ) 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 2 2 2 3 4 5 6 7 8 9 3 3 3 3 4 5 6 7 8 9 4 4 4 4 4 4 3 4 5 6 7 8 9 5 5 5 4 3 4 5 6 7 8 6 6 5 5 4 4 5 6 7 8 7 7 6 6 5 5 5 5 6 7 8 8 7 7 6 5 6 6 5 6 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 2 2 2 3 4 5 6 7 8 9 3 3 3 3 4 5 6 7 8 9 A L G O R I T H M [m] [n] dist for col 1 to m+1 dist[0][col] col for row 1 to n+1 dist[row][0] row for col 1 to m+1 for row 1 to n+1 dist[row-1][col-1] + 0/1 dist[row-1][col] + 1 dist[row] [col-1] + 1 dist[row][col] min
