# Week 10. Dynamic Programming

## Algorithms and Data Structures

### 11 Week 10. Dynamic Programming

Reading 10 Goodrich & Tamassia: Chapter 12.5

##### 11.0.1 Compulsory Assignment

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

##### 11.0.2 Other Exercises

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}\mathrm{log}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.