Week 10. Dynamic Programming

Reading 10 Goodrich & Tamassia: Chapter 12.5

Problem 11.1 (based on textbook problem P-12.37/38) The edit distance between two strings $A$ and $B$ is defined as the minimum number of edit operations needed to transfor $A$ into $B$. Three different edit operations are allowed, delete a character, insert a character, or replace a character. Note that the edit distance is symmetric, i.e. the distance from $A$ to $B$ and from $B$ to $A$ are the same.

Design an $O(n\cdot m)$ algorithm to calculate the edit distance for a pair of strings $A$ and $B$.

Problem 11.2 What is the best way to multiply a chain of matrices with dimensions $10\times 2$, $2\times 5$, $5\times 20$, $20\times 8$, $8\times 10$ and $10\times 4$.

Use dynamic programming and fill in the $5\times 5$ array by hand.

Problem 11.3 Let three integer arrays, $A$, $B$, and $C$, be given, each of size $n$. Given an arbitrary integer $k$, design an $O(n^2\log <!--FUNCTION\; APPLICATION-->n)$-time algorithm to determine if there exists numbers $a\in A$, $b\in B$, $c\in C$ such that $k=a+b+c$.

Problem 11.4 Given an $O\left(n^2\right)$-time algorithm for the previous problem.