Feb 18. Dynamic Programming III

Matrix Chain Multiplication

Given a series of matrices $A_1, A_2, \cdots, A_n$, we wish to compute $A_1A_2\cdots A_n$. In order for the problem to be well defined, we assume that the dimensions of the matrices match, i.e. $A_i$ is $m_i\times m_{i+1}$ for some $\{m_i\}_{i=1}^n$.

Suppose we start multiplying naively from the left, then the total running time is $m_1m_2m_3 + m_1m_3m_4 + m_1m_4m_5 + \cdots + m_1m_nm_{n+1}$. However observe that the order in which we choose to multiply might give us better or worse running times. Let us denote by $B[i][j]$ (where $1 \le i, j \le n$) the optimal running time for multiplying $A_iA_{i+1} \cdots A_j$. Thus the entry we are interested in is $B[1][n]$. Consider the last multiplication in the computation for $A_i A_{i+1} \cdot A_j$ – it could be $(A_iA_{i+1}\cdots A_k)(A_{k+1}\cdots A_j)$ for any $1 \le k < j$. Thus we get the following recurrence relation: $B[i][j] = \min_{i \le k < j} \{B[i][k] + B[k+1][j] + m_im_{k+1}m_j$.

Order of filling the table

Observe that the recurrence relation for $B[i][j]$ is written in terms of entries $B[i'][j']$ such that $j'-i' < j-i$. This gives us the order in which to fill the table, i.e. compute entries $(i, j)$ in the order of $j-i$.

Running Time

Note that we need to fill $n^2$ entries and filling each entry requires us to multiply some appropriate matrix dimensions. If this is assumed to be $O(1)$ then the total running time is $O(n^2)$.

Independent Set

Given a vertex weighted graph $G=(V, E)$ we wish to find a maximum weight independent set $I$ in $G$. A set $I \subseteq V$ is called an independent set if for every $u, v \in I$, $(u, v) \notin E$. We will solve this problem for the special case when $G$ is a tree.

Note that greedy is a bad idea here. Consider a star graph on $n+1$ vertices where the central vertex has weight $2$ and every other vertex has weight $1$. The optimal solution is $n$ while greedy picks a solution of weight $2$.

Dynamic Programming Approach

Let us pick a vertex as a root and think of $G$ as a rooted tree. Let $A[i]$ denote the weight of the largest sub-tree rooted at vertex $i$.Thus we are interested in the entry $A[r]$ where $r$ is the root of the tree. Consider the entry $A[u]$. We have two possibilities: either the vertex $u$ is in the optimal set or it is not a part of the optimal set. Thus $A[u] = \max \{ w(u) + \sum_{v: \text{v is a grandchild of u}} A[v], \sum_{v:\text{v is a child of u}} A[v]\}$. We fill up the entries for the leaves first, then their parents and so on. We need to fill $n$ entries, while to compute an entry we may need $O(n)$ operations, giving us an upper bound of $O(n^2)$. However this is a loose upper bound and a more careful analysis shows that it is in fact $O(n)$, since each vertex of the three is examined at most 3 times: when filling the table entry for it, for its parent or for its grandparent.

One Comment

1. For the running time of Matrix Chain Multiplication, it states, “Note that we need to fill n^2 entries and filling each entry requires us to multiply some appropriate matrix dimensions. If this is assumed to be O(1)”. Why why assume filling each entry is O(1) when filling each entry requires us to look at B[i][k] and B[k+1][j] entries to find the minimum cost?