← All notes

Design and Analysis of Algorithms

Contents
  1. Minimum Spanning Tree
  2. Greedy Idea 1: Kruskal’s algorithm
  3. Greedy Idea 2: Prim’s Algorithm
  4. Other algorithms
  5. Union-Find data structure
  6. More Greedy Problems
  7. Needle in Haystack
  8. Matroids
  9. Task Scheduling
  10. Huffman Codes
  11. Shannon’s source coding theorem
  12. Split-array largest sum
  13. Minimum fractional ST
  14. Master Theorem
  15. Closest Point
  16. Fast Multiplication
  17. Convolution
  18. Convolution Theorem
  19. Longest path on a DAG
  20. Knapsack Problem
  21. General observation
  22. Knapsack with unlimited items
  23. Knapsack with limited items
  24. 2D Knapsack
  25. Summary

Greedy Algorithms

Minimum Spanning Tree

Consider a graph GG describe by VV and EE (positive weights). A spanning tree of a graph is defined as an edge set T⊂ET \subset E such that (V,T)(V, T) is a tree. A minimum spanning tree is such that ∑l∈Tle\sum_{l \in T} l_e is minimized.

For a graph with nn vertices, there are nn−2n^{n - 2} spanning trees for a complete graph (Cayley’s formula).

How do we calculate the number of spanning trees for a general graph? Kirchoff’s theorem states the following -

  • Let MM be the adjacency matrix of GG, and let DD be the diagonal matrix with Dii=deg⁡(i)D_{ii}=\deg(i).
  • Define the graph Laplacian as L=D−ML = D - M.
  • Then, the number of spanning trees is the determinant of any n−1n-1 by n−1n-1 principal submatrix of LL (obtained by removing the same row and column).

Notice how any sub-matrix yields the same value!

Greedy Idea 1: Kruskal’s algorithm

  • Sort all the edges with their weights
  • Pick edges as long as they don’t form a cycle

Does this work? If it does, how do we prove it?

Firstly, why is it a greedy idea? At each point of the algorithm, we select the current greedy edge (a local minimum) to obtain the minimum spanning tree (a global optimum).

  • The cut property - Let S⊆VS \subseteq V such that SS and V−SV - S are non-empty. If ee is an edge across SS and V−SV - S with the minimum cost, then there always exists a minimum spanning tree with ee.

    Proof. Exchange argument. If an MST omits ee, its tree path between the endpoints of ee contains an edge e’e’ across SS and V−SV - S. Replace e’e’ with ee; since ee has minimum cost across the cut, the result is also an MST.

    Shouldn’t this argument be more delicate? Why is there a single edge from S to V - S?

    Essentially, the exchange argument argues replacing a part of the solution improves the solution but does not worsen it.

  • The time complexity of the algorithm comes out to be O(mlog⁡m+mα(n))O(m \log m + m \alpha(n)). The second term in the expression comes from union-find data structures.

  • Correctness of the algorithm - We shall prove this via induction.

    • Induction hypothesis - The edges selected in the iith round of Kruskal’s algorithm can form an MST along with a subset of edges from the remaining edges.
    • Base statement - True for i=0i = 0
    • Induction step - Cut property
  • Union-find data structure - A data structure that supports

    • Merging elements of two sets into a single set - union(x, y)
    • Checking whether two elements are in the same set - find(x)

    efficiently. The amortized time complexity for these operations is α(n)\alpha(n) where α(n)≤4\alpha(n) \leq 4 for nn of the order 2222162^{2^{2^{2^{16}}}}. As a result, α(n)\alpha(n) can be regarded as a constant for practical purposes.

    In our case, the elements are edges and sets represent connected components.

Greedy Idea 2: Prim’s Algorithm

Start with any node and expand with the smallest edge connecting to the remaining set of edges. Note that this is different from Kruskal’s algorithm where we sort all the edges and create individual connected components that eventually merge together.

The proof for Prim’s algorithm is very similar to that of Kruskal’s. The time complexity is O(n2+m)O(n^2 + m) similar to Djikstra’s algorithm without a data structure. We can maintain a priority queue to maintain all edges that come from SS to reduce the time-complexity to O((n+m)log⁡m)O((n + m) \log m) (without decrease-key). With decrease key and a binary heap, the complexity becomes O((n+m)log⁡n)O((n + m) \log n). Furthermore, with decrease key and a Fibonacci heap, the complexity reduces to O(nlog⁡n+m)O(n\log n + m).

Other algorithms

  • Reverse deletion - For every cycle in the original graph and the edge ee with the maximum cost, there always exists an MST without ee. Until there are no cycles in the graph, find a cycle and delete the edge with a maximum cost. Note that this algorithm has a higher time complexity since we try and find a cycle for each iteration of the algorithm. How do we implement this?

Union-Find data structure

The idea is to maintain trees with pointers to merge and find elements. The main complication comes while merging the individual sets.

  • Merging by size (consuming smaller ones by larger sets) - The complexity of merging sets of size nn, mm times takes O(mlog⁡n)O(m \log n)

  • To optimize this further, we merge by rank (generalizing the previous approach where rank was simply the size of the set). We add another trick to reduce the amortized time complexity.

    • Path compression - When find(x) is called, attach the found elements along the path directly to the root to reduce the path size.

    The time complexity then becomes O(mlog⁡∗n)O(m \log^* n) where log⁡∗n\log^* n is the minimum kk such that log⁡(k)n≤1\log^{(k)} n \leq 1.

More Greedy Problems related to MST

kk-clustering

A maximum spacing for kk-clustering of G=(V,E)G =(V, E) is defined as

  • An edge set T⊂ET \subset E such that (V,T)(V, T) has exactly kk connected components
  • The spacing is then min⁡d(u,v)\min d(u, v) for u,vu, v in different connected components
  • The goal is to maximize the spacing

This problem can be solved again with Kruskal’s algotihm to find kk-connected components - perform the union operation for n−kn - k times. Why is this correct? WE can show this using a contradiction.

  • Consider two nodes that lie in the same connected component in the result obtained by Kruskal’s (with spacing d’d’). Let them be in different connected components in the optimal solution (with spacing dd). Then,

Second MST

A second MST is essentially the spanning tree with the second lowest edge summation cost. How do we find this tree?

  • Find an MST with weight ww
  • For every edge ee not in the MST, if adding ee yields a cycle in the graph; then remove the largest edge e’e’ other than ee in the cycle to obtain the second MST
  • The cost of the tree would be w+le−le’w + l_e - l_{e’}

The time complexity of this algorithm is O(TMST+mn)\mathcal O(T_{MST} + mn) and can be improved to O(TMST+mlog⁡n)\mathcal O(T_{MST} + m \log n) with better data-structures and divide-and-conquer.

Lemma. The second MST only differs by one edge from the MST. Multiple MSTs? Proof. Can be shown using contradiction. The idea is that one can move from one spanning tree to another with local changes in the trees. The argument is that you can replace the edges in the second MST with the edges in the MST to obtain a tree with a lower cost. This process can be repeated until there is only one edge that is different from an MST and replacing that would cause the tree to become the MST.

More Greedy Problems

Needle in Haystack

Given two strings s,ts, t, decide whether there is a subsequence (need not be contiguous) in ss that matches with tt. A naive greedy algorithm is depicted as follows -

i, j = 0, 0
while True:
    if j == len(t):
        break 
    if s[i] == t[j]:
        j += 1 # s[i] is matched with t[j]
    else:
        i += 1

On first glance, it looks as if this is a very intuitive algorithm. However, there are more intricate details and the proof makes these clearer. The proof relies on the Exchange argument. If there exists a subsequence i1i2…imi_1 i_2 \dots i_m in ss matching tt (∣t∣=m\vert t \vert = m). If i1∗<i1i^*_1 < i_1 is the first index that s[i1]=t[1]s[i_1] = t[1], then i1∗i2…imi^*_1i_2\dots i_m also matches tt. This way we can find a set of indices i1∗i2∗…im∗i^*_1i^*_2 \dots i^*_m through the greedy algorithm that gives the correct answer.

In general, greedy algorithms can be proven in two general ways

  • Consider any iteration of the algorithm and show that the decision made by the greedy algorithm is the best and conclude using induction
  • Exchange argument: Pick an optimal solution and gradually change it to the solution produced by the greedy algorithm showing that the optimality is not affected.

Matroids

A finite matroid MM consists of (E,I)(E, I) where

  • EE is a finite set (called the ground set). For example, EE is the set of all edges in the graph G=(V,E)G = (V, E)
  • II is a collection of subsets of EE (called the independent set). For example, II consists all subsets of SS of EE such that all the edges in s∈Ss \in S form a forest.

(E,I)(E, I) should satisfy the following properties -

  • Null set should be in II - ϕ∈I\phi \in I
  • if A⊂BA \subset B and B∈IB \in I then A∈IA \in I
  • If A,B∈IA, B \in I, ∣A∣>∣B∣\vert A\vert > \vert B \vert then ∃e∈A−B\exists e \in A - B, such that B∪{e}∈IB \cup \{e\} \in I

Isn’t 2 inclusive of 1 and 3?

How does this data structure help us? Suppose we have a graph G=(V,E)G = (V, E) with weights ce≥0c_e \geq 0. Then, design an algorithm to find an independent set SS that maximizes ∑e∈Sce\sum_{e \in S} c_e. Consider the following algorithm -

  • Sort ee in decreasing order of weights
  • Let S=ϕS = \phi. Add ee to SS if ee does not add cycles in SS

This algorithm is very similar to the reverse deletion algorithm and has a time complexity O(∣E∣log⁡∣E∣+Tcheck IS)\mathcal O(\vert E \vert \log \vert E \vert + T_{check \text{ IS}}).

Lemma. Let e∈Ee \in E have the maximum cost cec_em then there always exists an IS AA with maximum weight containing ee.

The proof is very similar to what we have shown with MSTs. This example can be applied to MSTs, and it demonstrates how Matroids can be useful for greedy algorithms.

Task Scheduling

Given nn jobs each with tit_i time to finish and deadlines did_i. Consider that there is a single resource solving tasks sequentially from time 00, and a job has to completely finished before moving onto the next one.

Suppose in a scheduling algorithm, job ii finishes at time fif_i, then the lateness is defined as li=max⁡{0,fi−di}l_i = \max\{0, f_i - d_i\}. The goal is find an algorithm that minimizes the maximum lateness minimizemax⁡iliminimize \max_i l_i.

Let us consider a simple case. Suppose there are two jobs with di≤d2d_i \leq d_2. Note that any scheduling algorithm should not have any idle time between jobs. Why so? If there is idle time, you can always do a job earlier to reduce the lateness. Furthermore, a scheduling algorithm should not have an inversion. That is, if job 1 has deadline earlier than job 2, then it is always optimal to perform job 1 before job 2. This claim can be easily proved using the exchange argument.

Algorithm

Sort all jobs according to the increasing order of these deadlines did_i, then complete each job without any idle time.

Proof. Generalize the previous two observations to nn jobs.

Huffman Codes

How do we encode an alphabet in binaries to have no ambiguities.

Prefix codes

A prefix code for an alphabet TT is a function f:T→{0,1}∗f:T \to \{0, 1\}^*, such that for distinct x,y∈Tx, y \in T, f(x)f(x) is not a prefix of f(y)f(y).

It can be shown that a prefix code gives unique decoding.

How do we design an encoding that is most efficient? Let us define efficiency. For every letter xx in TT, let its frequency be px(∑x∈Tpx=1)p_x (\sum_{x \in T} p_x = 1). Let ff be a prefix code and for every letter x∈Tx \in T, let ∣f(x)∣\vert f(x)\vert is the number of bits. The goal is to find a prefix code ff that minimizes the expected number of bits when encoding RR under the frequency {px}\{p_x\}.

minimize ∑x∈Tpx⋅∣f(x)∣\text{minimize } \sum_{x \in T} p_x \cdot |f(x)|

It is beneficial to represent prefix codes as a binary tree. Each node has two children: 0 and 1. The paths from the root to other nodes in the tree represent the binary encodings.

  • For prefix codes, no node of a symbol is an ancestor of node of another symbol (from the alphabet).
  • Another observation is that any optimal prefix code is a full tree (every inner node has two children) - if anode has a single chide, the parent node can itself be used for the symbol deleting the leaf node making the encoding more efficient.
  • There is an optimal tree (prefix code) such that two lower frequent letters are siblings, and are as deep as possible in the tree. This claim can be proved easily with the exchange argument.

With these observations, consider the following algorithm

  • Initialize each letter xx as a node and label it with pxp_x

  • Put all nodes into a min-heap (according to the frequency)

  • While min-heap has atleast two elements

    • Pop out the two smallest elements u,vu, v (corresponds to two trees)

    • Combine them to a single tree

    • Push it into the heap, label with pu+pvp_u + p_v

This is the Huffman’s coding algorithm which has a time complexity of nlog⁡nn \log n.

Shannon’s source coding theorem

Let TT be an alphabet with frequency {px}\{p_x\}. The entropy of the alphabet is defined as

H:=∑x∈Tpx⋅log⁡1pxH := \sum_{x \in T} p_x \cdot \log \frac{1}{p_x}

The Shannon’s source coding theorem then states that you cannot send a letter from TT with frequenct {px}\{p_x\}, with expected bits less than HH. Huffmman’s encoding gives a solution with expected bits at most H+1H + 1.

Important point. One can suggest to increase the alphabet size with dummy symbols to virtually reduce the value of HH significantly. However, this introduces complexity for encoding algorithms. Therefore, there is a tradeoff with space occupied by encoding and the time for encoding.

Even with augmented alphabet, the size of the encoding does not change for the original symbols in the alphabet?

Binary Search X Greedy Algorithms

The basic binary search takes advantage of the monotone structure in arrays to identify elements with certain properties. Any binary search problem can be converted to the following simpler version: For an array BB that has binary elements with all zeros occurring before all ones, find the index of the first occuring 11.

The binary search algorithm can be simply proved using induction.

Let us consider an example - Ternary search. Given an array A[1…n]A[1\dots n] that is first strictly increasing and then strictly decreasing, dind the largest element. The array B[1…n−1]B[1\dots n - 1] is constructed as

  • B[i]=1  ⟺  A[i+1]>A[i]B[i] = 1 \iff A[i + 1] > A[i]

  • B[i]=0  ⟺  A[i+1]<A[i]B[i] = 0 \iff A[i + 1] < A[i]

Split-array largest sum

Minimum fractional ST

Given an undirected graph G=(V,E)G = (V, E) and each edge has two costs ae,bea_e, b_e both of which are positive, find a spanning tree TT that minimizes

∑e∈Tae∑e∈Tbe\frac{\sum_{e \in T} a_e}{\sum_{e \in T} b_e}

How is this related to binary search? Firstly, we will convert this problem to a decisional version - Given an undirected graph G=(V,E)G = (V, E) and a real number UU, decide whether there exists a spanning tree TT such that ∑e∈Tae∑e∈Tbe≤U\frac{\sum_{e \in T} a_e}{\sum_{e \in T} b_e} \leq U.

This is equivalent to find a spanning tree such that ∑e∈Tae−Ube≤0\sum_{e \in T} a_e - U b_e \leq 0. Construct a new graph with the weights ae−Ubea_e - Ub_e. The reduction is easy to follow.

How do we find the monotone structure for binary search? If the decision problem (G,U)(G, U) is satisfiable, then (G,U′)(G, U') is also satisfiable for any U′>UU' > U. Conceptually, assume a function BB (with continuous index) such that B[0,S]→{0,1}B[0, S] \to \{0, 1\} where SS is an upper bound. B(U)=1B(U) = 1 iuf and only if (G,U)(G, U) is satisifiable, and BB is monotone.

Divide and Conquer

Master Theorem

Consider an algorithm that has the following relationship for running time complexity -

T(n)=2T(n2)+cnlog⁡kn(k≥0)T(n) = 2T \left(\frac{n}{2}\right) + c n \log^k n \quad (k \geq 0)

then T(n)=O(nlog⁡k+1n)T(n) = \mathcal O(n \log^{k + 1} n).

Closest Point

Fast Multiplication

Suppose we have two integers in binary a=∑0≤i<nai⋅2i,b=∑0≤i<nbi⋅2ia = \sum_{0 \leq i < n} a_i \cdot 2^i, b = \sum_{0 \leq i < n} b_i \cdot 2^i. The goal is to compute c=ab=∑0≤j<2ncj⋅2jc = ab = \sum_{0 \leq j < 2n} c_j \cdot 2^j, where cj=∑k=max⁡(0,j−(n−1))min⁡(j,n−1)akbj−kc_j = \sum_{k=\max(0,j-(n-1))}^{\min(j,n-1)} a_k b_{j-k} for 0≤j≤2n−20 \leq j \leq 2n-2 and c2n−1=0c_{2n-1}=0. The naïve brute force approach takes O(n2)\mathcal O(n^2) to compute the answer.

This question is related to matrix multiplication as well. The naïve algorithm takes O(n3)\mathcal O(n^3).

Algorithm 1

We segment a,ba, b as follows -

  • a=A1⋅2n2+A0a = A_1 \cdot 2^{\frac{n}{2}} + A_0 where A0=∑0≤i<n/2ai⋅2iA_0 = \sum_{0 \leq i < n/2} a_i \cdot 2^i and A1=∑n/2≤i<nai⋅2i−n/2A_1 = \sum_{n/2 \leq i < n} a_i \cdot 2^{i - n/2}

  • b=B1⋅2n2+B0b = B_1 \cdot 2^{\frac{n}{2}} + B_0 similarly.

Then, ab=(A1⋅2n2+A0)(B1⋅2n2+B0)ab = (A_1 \cdot 2^{\frac{n}{2}} + A_0)(B_1 \cdot 2^{\frac{n}{2}} + B_0). The strategy then is to do a divide and conquer on these halves to get the final answer.

ab=A1B12n+(A0B1+A1B0)2n/2+A0B0ab = A_1 B_1 2^n + (A_0 B_1 + A_1 B_0)2^{n/2} + A_0B_0

The time complexity is then T(n)=4T(n2)+O(n)T(n) = 4T(\frac{n}{2}) + \mathcal O(n). This is essentially O(n2)\mathcal O(n^2) that does not give any improvement.

This can be optimized further -

ab=A1B12n+((A0+A1)(B0+B1)−A0B0−A1B1)2n/2+A0B0ab = A_1 B_1 2^n + ((A_0 + A_1)(B_0 + B_1) - A_0B_0 - A_1 B_1)2^{n/2} + A_0B_0

The number of multiplications is reduced to 3, giving T(n)=3T(n2)+O(n)T(n) = 3T(\frac{n}{2}) + \mathcal O(n) and hence T(n)=O(nlog⁡23)T(n) = \mathcal O(n^{\log_2 3}).

This algorithm can be extended to matrix multiplications as well.

C=AB=[A00B00+A01B10A00B01+A01B11A10B00+A11B10A10B01+A11B11]C = AB = \begin{bmatrix} A_{00}B_{00} + A_{01}B_{10} & A_{00}B_{01} + A_{01} B_{11} \\A_{10}B_{00} + A_{11}B_{10} & A_{10}B_{01} + A_{11}B_{11}\end{bmatrix}

The naïve algorithm shown above is still O(n3)O(n^3). Strassen’s algorithm reduces the number of multiplications to 77 providing an improvement over the O(n3)\mathcal O(n^3) algorithm giving ≈O(n2.81)\approx \mathcal O(n^{2.81}).

The current state of the art algorithm for matrix multiplication achieves O(n2.371552)\mathcal O(n^{2.371552}). We do not know if there is an algorithm that achieves O(n2+o(1))\mathcal O (n^{2 + o(1)}).

Algorithm 2

Multiplication can be seen as a special case of convolution and we can use Fast Fourier Transform (FFT) to perform this in O(nlog⁡n)\mathcal O(n \log n). The details will be elaborated in the next section.

Convolution

Consider two vectors of the following form -

  • a=(an−1,an−2,…,a2,a1,a0)a = (a_{n - 1}, a_{n - 2}, \dots, a_2, a_1, a_0)

  • b=(bn−1,bn−2,…,b2,b1,b0)b = (b_{n - 1}, b_{n - 2}, \dots, b_2, b_1, b_0)

The convolution operation ⋆\star is defined as

c=a⋆b=(cn−1,…,c0) where cj=∑0≤k<nakb(j−k)mod  nc = a\star b = (c_{n - 1}, \dots, c_0) \quad \text{ where } c_j = \sum_{0 \leq k < n} a_k b_{(j - k)\mod n}

Convolution is a generalization of integer multiplication (padding + convolution = multiplication). Also, convolution is a central operation in signal processing - used for blurring images and also to learn features from spatial data.

The naïve algorithm can be done in O(n2)\mathcal O(n^2) time. We can perform convolution using O(nlog⁡n)\mathcal O(n\log n ) using Fourier Transform.

Fourier Transform

Consider the nn dimensional vector a=(an−1,an−2,…,a2,a1,a0)a = (a_{n - 1}, a_{n - 2}, \dots, a_2, a_1, a_0) and b=(bn−1,bn−2,…,b2,b1,b0)b = (b_{n - 1}, b_{n - 2}, \dots, b_2, b_1, b_0). Let {ei}i\{e_i\}_i form a unit basis of Rn\mathbb R^n such that a=∑0≤i<naiei,b=∑0≤i<nbieia = \sum_{0 \leq i < n} a_i e_i, b = \sum_{0 \leq i < n} b_i e_i.

Consider another basis of Cn\mathbb C^n with components e^i(j)=1nωnij\hat e_i(j) = \frac{1}{\sqrt{n}}\omega_n^{ij}, where ωn=e2πin\omega_n = e^{\frac{2\pi \bf{i}}{n}} is the nn-th root of unity. Therefore, e^i=1n(ωn(n−1)i,…,ωn2i,ωni,1)\hat e_i = \frac{1}{\sqrt{n}}(\omega_n^{(n - 1)i}, \dots, \omega_n^{2i}, \omega_n^{i}, 1).

It is easy to check that this is a valid basis. So, again, a,ba, b can be uniquely represented as

  • a=∑0≤i<na^ie^ia = \sum_{0 \leq i < n} \hat a_i \hat e_i, a^i=⟨a,e^i⟩=1n∑jajωn−ij\hat a_i = \langle a, \hat e_i\rangle = \frac{1}{\sqrt{n}} \sum_j a_j \omega_n^{-ij}

  • b=∑0≤i<nb^ie^ib = \sum_{0 \leq i < n} \hat b_i \hat e_i

A Fourier transform is then defined as - Given {ai}i∈[n]\{a_i\}_{i \in [n]}, compute F(a)={ai^}i∈[n]F(a) = \{\hat{a_i}\}_{i \in [n]}.

The inverse problem is to find F−1(a^)={ai}i∈[n]F^{-1} (\hat a) = \{a_i \}_{i \in [n]}. It essentially is a change of basis between {ei}  ⟺  {e^i}\{e_i\} \iff \{\hat e_i\}.

Convolution Theorem

Let a,ba, b be two vectors in Rn\mathbb R^n; then,

a⋆b=F−1(n F(a)⋅F(b))a \star b = F^{-1} (\sqrt{n}\,F(a) \cdot F(b))

With this claim, convolution can be f=done in O(2TFT+TIFT+n)\mathcal O(2T_{FT} + T_{IFT} + n).

Dynamic Programming

Longest path on a DAG

Given a DAF with nn vertices, mm edges, every edge ee has a weight lel_e, compute the longest path on the DAG. The length of a path is defined as the weight sum over all edges in the path.

Consider the following algorithm

DFS(u):
    if marked[u] = true:
        return DP[u]
    cost <- 0
    for all v that (v, u) in E:
        cost <- max(cost, DFS(v) + l_{v, u})
    marked[u] <- true
    DP[u] <- cost
    return cost

The time complexity of the algorithm is O(n+m)\mathcal O(n + m). The key point to notice is that instead of recomputing the cost of each path, we have essentially stored the costs in the array DP to reduce the redundant calculations. This step is known as memoization.

Knapsack Problem

Consider an integer UU representing total capacity and a list of integers {vi,ci}\{v_i, c_i\} that represents the volume and cost of each item respectively. The goal is to pick items such that their total volume is at most UU and their value is maximized.

Idea 1. Sort everything by vi/civ_i/c_i and pick the items until value if UU. It is easy to see that this greedy algorithm will not work.

A Backtracking algorithm

Consider an iterative algorithm that at step ii has CC volume left and is considering whether to pick or skip the ii-th item. Considering these two possibilities, we can implement a brute force algorithm with memoization for dynamic programming.

We set a 2D matrix of size (U,n)(U, n) where each row ii represents the set of items that need to be picked to maximize the cost within volume UU. Without memoization, this recursive search takes O(2n)\mathcal O(2^n) time; with memoization over the O(Un)\mathcal O(Un) states (C,i)(C,i), it takes O(Un)\mathcal O(Un) time.

The algorithm is as follows -

   dfs(C, i):
       if i = 0: return 0
       Cost <- dfs(C, i - 1)
       if C >= c_i:
           Cost <- max(Cost, dfs(C - c_i, i - 1) + v_i)
       return Cost

Alternative view

We can treat every possible (C,i)(C, i) as a vertex in a graph. Every vertex has at most two outcoming edges - (C,i)→(C−ci,i−1)(C, i) \to (C - c_i, i - 1) with cost viv_i and (C,i)→(C,i−1)(C, i) \to (C, i - 1) with cost 00. This constructed graph is a DAG and we essentially reduced Knapsack problem to longest path on a DAG.

Based on the algorithm we have seen earlier, we modify the algorithm to include memoization

   dfs(C, i):
       if marked[C][i] = true: return DP[C][i] // Modification
       if i = 0: return 0
       Cost <- dfs(C, i - 1)
       if C >= c_i:
           Cost <- max(Cost, dfs(C - c_i, i - 1) + v_i)
       marked[C][i] <- true // Modification
       DP[C][i] <- cost // Modification
       return Cost

The modified algorithm now has the time complexity O(Un)\mathcal O(Un) since there are UnUn vertices in total with atmost 2 edges each.

General observation

Dynamic Programming problems can be typically thought og as a decision-making processes. These decision problems can be converted to graphs where the states are vertices on a graph and the transitions are edges on a graph. Typically, the problem have a DP solution if the graph is a DAG and the number of states is not too large.

The algorithm shown above can then be used as a general procedure to solve the problems. Sometimes, it is beneficial to implement the algorithms with a loop rather than recursion.

Knapsack with unlimited items

The algorithm remains pretty much the same except that teh recrusion call has dfs(C - c_i, i) instead of dfs(C - c_i, i - 1).

Knapsack with limited items

We can consider another variant where item ii can be used at most kik_i times. Then, a similar algorithm would have the time complexity (U∑iki)\mathcal (U \sum_i k_i).

A better solution treats the iith item as ⌈log⁡2(ki+1)⌉\lceil \log_2(k_i+1)\rceil bounded-size items. For example, if ki=8k_i = 8, then divide the item as (ci,vi),(2ci,2vi),(4ci,4vi),(ci,vi)(c_i, v_i), (2c_i, 2v_i), (4c_i, 4v_i), (c_i, v_i). Then the time complexity would be reduced to O(U∑ilog⁡(ki+1))\mathcal O\left(U \sum_i \log(k_i+1)\right).

However, it can be improved to O(Un)\mathcal O(Un) using a monotonic queue.

2D Knapsack

In this variant, each item has value viv_i, volume integer ci>0c_i > 0 and a weight integer wi>0w_i > 0. The goal is to find a subset of items that has the total volume at most UU, total weight at most WW and the total value is maximized. The dynamic programming algorithm has a runtime of O(WUn)\mathcal O(WUn).

In the loop variant of the algorithm, it is better to iterate over the items first rather than the weights. Why is that? Furthermore, it is better to iterate decreasing the costs, because

Summary

Many intractable problems can be efficiently solved on trees - combining with DFS enforces the computation ordering.

Bellman-Ford algorithm

Single Source Shortest Path (SSSP)

Given a directed graph of nn vertices and mm edge, find the shortest paths for a vertex pair (s,t)(s, t).

Recently, researchers showed that Dijkstra’s algorithm is the most optimal algorithm possible with a specially designed heap.

Would dynamic programming work for SSSP? dp[u][i]dp[u][i] represents a path from ss to uu using at most i−1i - 1 edges. This simply is the Bellman-Ford algorithm.

Floyd-Warshall algorithm

All pair shortest path algorithm in O(n3)O(n^3).

Traveling Salesman Problem

Given.a complete graph of nn vertices, every edge has a cost lel_e. The goal is to find a path that visits every node exactly once while minimizing the total cost. It is an NP-hard problem where the brute-force algorithm takes mathcalO(n!)\\mathcal O(n!) - enumerating all possible permutations of nodes.

There is a dynamic programming solutions of the order O(2nn2)O(2^n n^2). This is computable with the modern computers upto n=15n = 15. We discuss the framework here -

  • States - At node uu, set of all unvisited states - minimum cost to finish the rest of the task. The number of states is O(n2n)\mathcal O(n2^n).

  • Decision-making

  • What will be the next node to visit? If we choose v∈Sv \in S, then the next state will be $$(v, S - {v})$

This can be implemented using a bitmask for representing the state - saves space and is faster.

Type to search the whole site.