# 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.