Algorithms and Data Structures 2020

# 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\left(n\cdot m\right)$ 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×2$, $2×5$, $5×20$, $20×8$, $8×10$ and $10×4$.

Use dynamic programming and fill in the $5×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\left({n}^{2}\mathrm{log}n\right)$-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.