Dynamic Programming (DP) is a powerful problem-solving paradigm in which a problem is solved by breaking it down into smaller subproblems. These subproblems are then tackled one by one, so that the answers to small problems are used to solve the larger ones. The simplicity of the DP paradigm, as well as its broad applicability have made it a fundamental technique for solving various search and optimization problems.
The word “programming” in “dynamic programming” has actually very little to do with computer programming and writing code. The term was first coined by Richard Bellman in the 1950s, back when programming meant planning, and dynamic programming meant to optimally plan a solution process. Indeed, the challenge of devising a good solution process is in deciding what are the subproblems, and in what order they should be computed. Apart from the obvious requirement that an optimal solution to a problem can be obtained by optimal solutions to its subproblems, an efficient DP is one that induces only a “small” number of distinct subproblems. Each subproblem is then reused again and again for solving multiple larger problems.
This idea of reusing subproblems is the main advantage of the DP paradigm over recursion. Recursion is suited for design techniques such as divide and-conquer, where a problem is reduced to subproblems that are substantially smaller, say half the size. In contrast, in a typical DP setting, a problem is reduced to subproblems that are only slightly smaller (e.g., smaller by only a constant factor). However, it is often convenient to write out a top-down recursive formula and then use it to describe the corresponding bottom-up DP solution. In many cases, this transformation is not immediate since in the final DP we can often achieve a space complexity that is asymptotically smaller than the total number of subproblems. This is enhanced by the fact that we only need to store the answer of a subproblem until the larger subproblems depending on it have been solved.
The simplicity of the DP paradigm is what makes it appealing, both as a full problem solving method as well as a subroutine solver in more complicated algorithmic solutions. However, while DP is useful when more specialized methods fail, this generality often incurs a cost in efficiency. In this thesis, we explore a toolkit for speeding up straightforward DPs, and algorithms that use DPs as subroutines.
Contents
1 Introduction
1.1 Searching for DP Repeats
1.2 Totally Monotone Matrices
1.3 Partial Tables and Fractional Subproblems
2 Acceleration via Compression
2.1 Decoding and Training Hidden Markov Models
- 2.1.1 The Viterbi Algorithm
2.1.2 The Forward-Backward Algorithms
2.2 Exploiting Repeated Substrings
2.3 Five Different Implementations of the General Framework
- 2.3.1 Acceleration via the Four Russians Method
2.3.2 Acceleration via Run-length Encoding
2.3.3 Acceleration via LZ78 Parsing
2.3.4 Acceleration via Straight-Line Programs
2.3.5 Acceleration via Byte-Pair Encoding
2.4 Optimal state-path recovery
2.5 TheTrainingProblem
- 2.5.1 Viterbitraining
2.5.2 Baum-Welch training
2.6 Parallelization
3 Totally Monotone Matrices and Monge Matrices
3.1 Preliminaries
- 3.1.1 Monotonicity,MongeandMatrixSearching
3.1.2 Jordan Separators for Embedded Planar Graphs
3.2 A Bellman-Ford Variant for Planar Graphs
3.3 The Replacement-Paths Problem in Planar Graphs
4 Combining Compression and Total-Monotonicity
4.1 Accelerating String Edit Distance Computation
- 4.1.1 Straight-line programs
4.1.2 Our results
4.1.3 Related Work
4.2 The DIST Table and Total-Monotonicity
4.3 Acceleration via Straight-Line Programs
4.3.1 Constructing an xy-partition
4.4 Improvement for Rational Scoring Functions
4.5 Four-Russian Interpretation
5 Partial Tables
5.1 Tree Edit Distance
- 5.1.1 Shasha and Zhang’s Algorithm
5.1.2 Klein’s Algorithm
5.1.3 The Decomposition Strategy Framework
5.2 Our Tree Edit Distance Algorithm
5.3 AS pace-Efficient DP formulation
5.4 A Tight Lower Bound for Decomposition Algorithms
5.5 Tree Edit Distance for RNA Comparison
- 5.5.1 RNA Alignment
5.5.2 Affine Gap Penalties
6 Fractional Sub problems
6.1 Finding an Optimal Tree Searching Strategy in Linear Time
6.2 Machinery for Solving Tree Searching Problems
6.3 Computing a Minimizing Extension
- 6.3.1 Algorithm Description
6.4 Linear Time Solution via Fractional Sub problems
6.5 From a Strategy Function to a Decision Tree in Linear Time
Bibliography
Download
PDF Ebook Accelerating Dynamic Programming by Oren Weimann
