Feb 13. Dynamic Programming II

All Pairs Shortest Path

Let A[i][j][k] be the shortest path in G (a weighted graph with non-negative edge weights) from i to j that uses only vertices \{1, 2, 3, \cdots, k\}. Then we can express A[i][j][k] as A[i][j][k] = \min \{ A[i][j][k-1], A[i][k][k-1] + A[k][j][k-1]\}. This is because either the shortest path from i to j using \{1, 2, 3, \cdots, k\} does not use the vertex k at all (thus the term A[i][j][k-1]) or it uses the vertex k in which case it only visits k once (since it is a shortest path and the edge weights are non-negative) and hence we get the term A[i][k][k-1] + A[k][j][k-1]. Thus one can fill the table A in a bottom up manner giving a running time of \Theta(n^3).

Longest Increasing Subsequence

Given a sequence of integers s_1, s_2, \cdots, s_n find the length of the longest increasing sub-sequence. To apply the dynamic programming paradigm we need to find a table that can be filled efficiently and that gives us the answer. Let A[j] denote the longest subsequence that ends with s_j. We can express A[j] as

A[j] = 1 + \displaystyle\max_{\substack{1\le i < j \\ s_i \le s_j}} \{A[i]\}

This gives us an \Theta(n^2) algorithm to solve this problem.

Edit Distance

We are given two words a_1a_2\cdots a_m and b_1b_2\cdots b_n and we wish to compute the edit distance between them. The edit distance is defined as the minimum number of insert, delete and replace operations that we need to do to transform the first string into the second. Insert operation allows us to insert a character, delete allows us to delete a character and replace allows us to replace a character with another character.

Let A[i][j] represent the edit distance between a_1a_2\cdots a_i and b_1b_2\cdots b_j. Then we may write A[i][j] as

A[i][j] = \min\{ 1 + A[i-1][j], 1 + A[i][j-1], 1_{a_i\neq b_j} + A[i-1][j-1]\}

where 1_{a_i\neq b_j}=1 if a_i\neq b_j and 0 otherwise. Filling up the table either row wise or column wise gives us an algorithm with running time \Theta(n^2).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s