Unit 4: Dynamic Programming - Subjective Questions

Dynamic programming is an algorithm-design technique that solves a problem by dividing it into interdependent subproblems, solving each distinct subproblem once, and storing its result for reuse.

A problem should possess the following properties:

• Optimal substructure: An optimal solution can be constructed from optimal solutions to smaller subproblems.
• Overlapping subproblems: The same subproblems occur repeatedly during computation.
• Well-defined states: Each subproblem can be represented using a finite set of state parameters.
• Recurrence relation: The solution of a state can be expressed in terms of smaller states.
• Base cases: Solutions to the smallest subproblems are directly known.

By storing intermediate results, dynamic programming avoids repeated computations and often converts an exponential-time recursive algorithm into a polynomial-time algorithm.

The general method of dynamic programming consists of the following steps:

1. Characterize the structure of an optimal solution: Determine how an optimal solution depends on solutions to smaller subproblems.
2. Define the states: Select parameters that uniquely identify each subproblem.
3. Develop a recurrence: Express the value of a state using previously defined smaller states.
4. Specify base cases: Give direct solutions for the smallest possible states.
5. Select an evaluation strategy: Use either top-down memoization or bottom-up tabulation.
6. Compute the optimal value: Fill the table or evaluate memoized states.
7. Reconstruct the solution: Store decisions, such as split points, if the actual solution is required.
8. Analyze complexity: Count the number of states and the work performed for each state.

In general,

Dynamic programming, divide-and-conquer, and greedy methods differ as follows:

• Nature of subproblems: Divide-and-conquer normally creates independent subproblems, whereas dynamic programming handles overlapping subproblems.
• Reuse of results: Dynamic programming stores previously computed results. A basic divide-and-conquer algorithm generally does not.
• Decision strategy: A greedy algorithm makes the best local choice and never revises it. Dynamic programming evaluates all relevant alternatives represented by its recurrence.
• Required properties: Dynamic programming requires optimal substructure and overlapping subproblems. Greedy algorithms additionally require the greedy-choice property.
• Optimality: A correct dynamic programming recurrence guarantees an optimal result. A greedy method is optimal only when its local choices can be proved safe.
• Resource usage: Dynamic programming often uses more memory because it maintains a table of states.

For example, matrix-chain multiplication is naturally solved by dynamic programming because several parenthesizations share the same subchains.

Bellman's principle of optimality states that an optimal solution has the property that, regardless of the initial decision, the remaining decisions must constitute an optimal solution for the state resulting from that decision.

Suppose an optimal solution to a problem contains a solution to a smaller subproblem. If that smaller solution were not optimal, it could be replaced by a better one, improving the complete solution. This would contradict the assumption that the complete solution was optimal.

In matrix-chain multiplication, if an optimal parenthesization of splits after , then the parenthesizations of and must both be optimal. Otherwise, replacing either part with a cheaper parenthesization would reduce the total multiplication cost.

Top-down memoization starts with the original problem and recursively evaluates required subproblems. Each computed value is stored so that later calls can reuse it.

Bottom-up tabulation begins with the base cases and evaluates states in an order that ensures all dependencies are already available.

Key differences include:

• Control: Memoization uses recursion, while tabulation normally uses iteration.
• States evaluated: Memoization evaluates only reachable states; tabulation often evaluates every table entry.
• Overhead: Memoization has function-call and recursion-stack overhead. Tabulation usually has lower constant overhead.
• Evaluation order: Memoization determines the order automatically through recursion. Tabulation requires an explicit dependency order.
• Stack safety: Deep memoized recursion may overflow the call stack, whereas tabulation avoids this problem.

Both methods have the same asymptotic complexity when they evaluate the same set of states.

The complexity of a dynamic programming algorithm is determined from its state space, transitions, and stored information.

If there are distinct states and each state examines at most transitions, then the running time is generally

If each state stores one constant-sized value, the table requires

space. Additional space may be required to reconstruct the solution or maintain a recursion stack.

For matrix-chain multiplication:

• There are intervals .
• Each interval examines up to split positions.
• Therefore, the time complexity is .
• The cost and split tables each contain entries, so the space complexity is .

Space can sometimes be reduced when a state depends on only a limited number of earlier rows or columns.

The matrix-chain multiplication problem asks for the parenthesization of a sequence of compatible matrices that minimizes the number of scalar multiplications.

Let matrix have dimensions . Matrix multiplication is associative, so every valid parenthesization computes the same mathematical product:

However, the intermediate matrix dimensions differ. Multiplying a matrix by a matrix requires

scalar multiplications. Consequently, different parenthesizations can have substantially different costs.

The problem does not change the order of the matrices; it only determines where the chain should be split and parenthesized.

Let have dimensions , and let represent the minimum number of scalar multiplications needed to compute .

A chain containing one matrix requires no multiplication, so

For , suppose the final multiplication splits the chain after . The two subchains are and . Their optimal costs are and .

The resulting matrices have dimensions and , so their multiplication costs

Therefore,

A second table stores the value of that attains the minimum, allowing the optimal parenthesization to be reconstructed.

The bottom-up algorithm fills the dynamic programming table in increasing order of chain length.

• Initialize for every matrix.
• For each chain length from to , consider every interval of that length.
• For each interval, try every split point from to .
• Store the minimum cost in and its split point in .

A compact description is:

1. Set .
2. For :
   • Set for each valid .
   • Initialize to infinity.
   • Compute

for every with .

3. If , update and set .

The final optimal cost is .

There are two possible complete parenthesizations.

1. Parenthesization

The first multiplication costs

It produces a matrix. Multiplying this result by costs

Thus, the total cost is

2. Parenthesization

The multiplication costs

It produces a matrix. Multiplying by this result costs

The total cost is

Therefore, the optimal parenthesization is , and the minimum cost is scalar multiplications.

During the cost computation, the split table stores the position at which the optimal solution for is divided.

The parenthesization is reconstructed recursively:

• If , output .
• Otherwise, output an opening parenthesis.
• Recursively reconstruct the chain .
• Recursively reconstruct the chain .
• Output a closing parenthesis.

Symbolically, if , then

The reconstruction visits each matrix and each internal split once. Therefore, it takes time, excluding the length of the printed output. The split table itself requires space.

For a chain of matrices, the algorithm considers every interval with .

• The number of intervals is .
• For each interval, the algorithm may examine up to split points.
• Hence, the running time is

The cost table has entries. If reconstruction is required, the split table also contains entries. Thus, the total auxiliary space is

The recursive memoized version has the same asymptotic time and table-space complexity, but it additionally uses recursion-stack space. The bottom-up version avoids that recursive overhead.

Consider an optimal parenthesization of the chain . Suppose its final multiplication splits the chain after , producing the subchains and .

Assume that the chosen parenthesization of is not optimal. Then there exists another parenthesization with a smaller cost. Replacing the original left subchain by this cheaper parenthesization would reduce the cost of the complete chain without changing the dimensions of the left result.

This contradicts the assumption that the complete parenthesization was optimal. The same argument applies to the right subchain.

Therefore, both subchains must be optimally parenthesized. Hence, matrix-chain multiplication possesses optimal substructure, which justifies the recurrence

The optimal storage on tapes problem determines the order in which files or programs should be stored sequentially on a tape so that the average or expected retrieval time is minimized.

Because a tape is a sequential-access medium, retrieving a file requires scanning all files placed before it as well as the file itself. If file has length and appears in position , its retrieval time is

For equally likely files, the mean retrieval time is

The objective is to find an ordering that minimizes this value. Under equal access probabilities and no special positioning overhead, the files should be stored in nondecreasing order of their lengths.

Let the files be stored in the order , with lengths .

The retrieval time of is the cumulative length

Since all files are equally likely to be accessed, their access probability is . Therefore,

Length occurs in all retrieval times, occurs in retrieval times, and so on. Hence, an equivalent formula is

This expression shows that earlier file lengths receive larger coefficients, so shorter files should be assigned to earlier positions.

Consider two adjacent files and with lengths and , where . Let be the total length of all files preceding them.

If is stored before , their combined retrieval-time contribution is

If their positions are exchanged, the contribution becomes

The first ordering exceeds the second by

Thus, placing the longer file before the shorter file cannot be optimal. Repeatedly exchanging every inverted adjacent pair produces a nondecreasing length order without increasing the retrieval time. Therefore, an optimal order satisfies

Because the files are assumed to be equally likely, they should be stored in nondecreasing order of length.

The optimal order is

The corresponding retrieval times are:

• First file:
• Second file:
• Third file:
• Fourth file:

The total retrieval time is

Therefore, the mean retrieval time is

Hence, the minimum mean retrieval time is units.

Let file have length and access probability . The expected retrieval time of an ordering is

where is the cumulative length up to file .

Consider adjacent files and . Storing before is no worse than storing before when

For positive probabilities, this is equivalent to

Therefore, files should be arranged in nondecreasing order of . This is the weighted shortest-processing-time rule.

For example, if the pairs are , , and , their ratios are , approximately , and . The optimal order is therefore the second file, first file, and third file.

With multiple tapes, a file is retrieved by selecting its tape and scanning the files preceding it on that tape. For equally likely files, the objective is to minimize the sum of cumulative retrieval times across all tapes.

The strategy is:

• Sort all files in nondecreasing order of length.
• Keep the numbers of files assigned to the tapes as balanced as possible.
• Assign shorter files to earlier positions because an early file contributes to the retrieval times of every later file on the same tape.
• Within each tape, store assigned files in nondecreasing order of length.

If files are stored on tapes, each tape normally receives either

or

files. A level-by-level or cyclic assignment of the sorted files is commonly used to place the shortest files in the high-contribution positions. The resulting mean retrieval time equals the total of all file retrieval times divided by .

Both problems minimize a cost, but their decision structures differ significantly.

Matrix-chain multiplication:

• The decision is the split position of every matrix subchain.
• Subproblems overlap across different parenthesizations.
• The problem is solved using the recurrence

• Dynamic programming is appropriate because all relevant split alternatives must be compared.

Optimal storage on tapes:

• The decision is the sequential ordering of files.
• Under equal probabilities, an exchange argument proves that sorting files by length is optimal.
• Under unequal probabilities, sorting by is optimal.
• Thus, the standard unconstrained version can be solved by sorting rather than a full dynamic programming table.

Both problems use optimality reasoning, but matrix-chain multiplication exhibits overlapping interval subproblems, whereas standard tape storage has a direct ordering rule.