Longest common subsequence

Longest common subsequence

Contents

• Retracing our steps
• Simple example
• A recursive approach
• Problems with the recursive solution
• Dynamic programming
• Memoize
• Recursion limit
• Bottom up calculation
• Extracting an LCS from the grid
• Animation
• Performance
• Reducing the space for LCS lengths
• Hirschberg’s Linear Space Algorithm
• Applied to the New York Marathon Results
• Hirschberg’s linear space algorithm in C++
• Applications: edit distance
• Applications: genetic mutations
• Applications: version control
• Conclusions
• Next time
• Thanks
• Python 3 Notes