Speeding up Dynamic Programming

A number of important computational problems in molecular biology, geology, speech recognition, and other areas can be expressed as recurrences which have typically been solved with dynamic programming. By using more sophisticated data structures, and by taking advantage of further structure from the applications, the authors speed up the computation of several of these recurrences by one or two orders of magnitude. The algorithms used are simple and practical. >

Authors

• David Eppstein
• Zvi Galil
• Raffaele Giancarlo

Keywords

• Dynamic programming
• Data structures
• Computer science
• Biology computing
• Computer science education
• Educational programs
• Computational biology
• Geology
• Speech recognition
• Binary search trees
• Diagonal
• Data Structure
• Lower Bound
• Weight Function
• Root Of The Tree
• RNA Secondary Structure
• Range Of Points
• Tree Search
• Binary Tree
• Recurrent Cases
• Edit Distance
• Program Time
• Binary Search
• Point Interval
• Outer Domain
• Original Owner
• Number Of Strips
• Convex Case
• Time Constant
• Subtree
• Multiple Loops
• Triangle Inequality
• Recursive Algorithm
• Log Time
• Start Of Interval