Lecture 19 - Notes

March 17, 2016

Shortest Path Algorithms Continued

Bellman-Ford

definition: We begin by setting the distance to $s$ to $0$ and the distance to $w$ to $\infty$ for all other vertices $v$. We relax every node $E$ exactly $V$ times.

Dynamic Programming

definition: Like greedy, Dynamic Programming is a problem solving technique particularly applicable to optimization. An example would be the Floyd-Warshall All-Pairs Shortest Path Algorithm.

Suppose I create a variable,

$$\begin{aligned} d_{i}^{(k)} = \min\left(d_{i}^{(k-1)}, \min_{j \in E}\left( d_{j}^{(k-1)} + w_{ij} \right) \right) \end{aligned}$$

where $d_{i}^{(k)}$ is the shortest path from $s$ to $i$ using at most $k$ edges. This is an example of the Bellman-Ford algorithm.

Longest Common Substring

definition: Given two strings, $S_1$ and $S_2$, what is their longest common substring? It's possible we could allow skipping letters in the the strings.

We can solve this using dynamic programming, let's call our strings,

$$\begin{aligned} x &= x_1 x_2 x_3 \ldots x_n \\\\ y &= y_1 y_2 y_3 \ldots y_m \\\\ \end{aligned}$$

and,

$$\begin{aligned} c[i,j] &= \begin{cases} 0 & \text{if}~ i=0 ~\text{or}~ j=0 \\\\ 1 + c[i -1,j-1] & \text{if}~ x_i = y_i \\\\ \max\left(c[i-1,j], c[i,j-1] \right) & \text{if}~ x_i \neq y_i \\\\ \end{cases} \\\\ &~ \end{aligned}$$

where $c[i,j]$ is the longest common string of $x[1 \ldots i]$ and $y[1 \ldots j]$.