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(n 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 × 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(n2 log n)-time algorithm to determine if there exists numbers a A, b B, c C such that k = a + b + c.

Problem 11.4 Given an O(n2)-time algorithm for the previous problem.