Coin-Row Problem

Find the maximum total value of a sequence of coins such that no two adjacent coins are selected.

F(n) = \max\{c_n + F(n-2), F(n-1)\}

Base cases:

\begin{aligned} F(0) &= 0 \\ F(1) &= c_1 \end{aligned}

0-1 Knapsack Problem

Find the maximum total value of a subset of items that fit into a knapsack of capacity W. Each item has a weight w_i and value v_i. We evaluate two cases for each item: either we include the i-th item (if it fits) or we don’t.

F[i,j] = \begin{cases} \max\{F[i-1, j], v_i + F[i-1, j-w_i]\} & \text{if } j - w_i \ge 0 \\ F[i-1, j] & \text{if } j - w_i < 0 \end{cases}

Base cases:

\begin{aligned} F[0, j] &= 0 \text{ for } j \ge 0 \\ F[i, 0] &= 0 \text{ for } i \ge 0 \end{aligned}

Optimal Binary Search Tree

An optimal binary search tree minimizes the average search time by placing more frequently accessed keys closer to the root. We build the tree using dynamic programming¹1. Dynamic Programming involves solving an optimization problem by breaking it down into simpler overlapping subproblems, solving each subproblem just once, and storing their solutions. to fill out a table containing the minimum search cost for subtrees.

ALGORITHM OptimalBST(P[1..n])
    // Finds an optimal binary search tree by dynamic programming
    // Input: An array P[1..n] of search probabilities for n keys
    // Output: Average number of comparisons in optimal BST and table R of roots
    for i \leftarrow 1 to n do
        C[i, i-1] \leftarrow 0
        C[i, i] \leftarrow P[i]
        R[i, i] \leftarrow i
    C[n+1, n] \leftarrow 0
    for d \leftarrow 1 to n \text{$-$} 1 do // diagonal count
        for i \leftarrow 1 to n \text{$-$} d do
            j \leftarrow i \text{$+$} d
            minval \leftarrow infinity
            for k \leftarrow i to j do
                if C[i, k-1] \text{$+$} C[k+1, j] \lt minval
                    minval \leftarrow C[i, k-1] \text{$+$} C[k+1, j]
                    kmin \leftarrow k
            R[i, j] \leftarrow kmin
            sum \leftarrow 0
            for s \leftarrow i to j do sum \leftarrow sum \text{$+$} P[s]
            C[i, j] \leftarrow minval \text{$+$} sum
    return C[1, n], R

Analysis — Time Efficiency: O(n^3), but can be reduced to O(n^2) by using monotonicity. Space Efficiency: O(n^2) for the DP tables.

Note — What about monotonicity? The optimal root k for the range i..j will always be between the root of i..j-1 and i+1..j. This narrows down the inner loop search and saves time.

Transitive Closure

Transitive Closure: Representation of a directed graph with n vertices, as a n \times n boolean matrix where a 1 at (i,j) means there’s a nontrivial path from i \to j.

Definition — Nontrivial: Basically, if there is a path from i \to j (doesn’t need to be direct, can route through other nodes).

To do this algorithmically, we must do dynamic programming (grow the answer little-by-little).

Warshall’s Algorithm

Main Idea: A path exists between i and j iif:

• There’s an edge from i to j; or
• There’s a path from i to j going through intermediate vertices from a restricted subset. By incrementally expanding the allowed intermediate vertices from \{1\} to \{1, 2, \dots, n\}, we build the transitive closure matrix.

The update rule is:

R^{(k)}[i,j] = R^{(k-1)}[i,j] \lor (R^{(k-1)}[i,k] \land R^{(k-1)}[k,j])

(We use the adjacency matrix to do Washall’s algorithm. It’s something about intersections.)

ALGORITHM Warshall(A[1..n, 1..n])
    // Implements Warshall's algorithm for computing the transitive closure
    // Input: Adjacency matrix A of a digraph with n vertices
    // Output: Transitive closure matrix R
    R(0) \leftarrow A
    for k \leftarrow 1 to n do
        for i \leftarrow 1 to n do
            for j \leftarrow 1 to n do
                R(k)[i, j] \leftarrow R(k-1)[i, j] or (R(k-1)[i, k] and R(k-1)[k, j])
    return R(n)

Analysis — Time complexity is \Theta(n^3). Space complexity is \Theta(n^2).

Floyd’s Algorithm

Problem: Find shortest path between each pair of verticies in a weighted digraph.

This ends up actually being pretty similar to Warshalls (using increasing subsets of vertices allowed as intermediate).

• Difference is we also want to find the minimum distance rather than just a boolean presence.

The update rule becomes:

D^{(k)}[i,j] = \min(D^{(k-1)}[i,j], D^{(k-1)}[i,k] + D^{(k-1)}[k,j])

ALGORITHM Floyd(W[1..n, 1..n])
    // Implements Floyd's algorithm for all-pairs shortest paths
    // Input: Weight matrix W of a graph
    // Output: Distance matrix D containing shortest path lengths
    D \leftarrow W
    for k \leftarrow 1 to n do
        for i \leftarrow 1 to n do
            for j \leftarrow 1 to n do
                D[i, j] \leftarrow min(D[i, j], D[i, k] \text{$+$} D[k, j])
    return D

Analysis — Time complexity is \Theta(n^3). Space complexity is \Theta(n^2).