\(\def\Real{\mathbb{R}}

\def\Comp{\mathbb{C}}

\def\Rat{\mathbb{Q}}

\def\Field{\mathbb{F}}

\def\Fun{\mathbf{Fun}}

\def\e{\mathbf{e}}

\def\f{\mathbf{f}}

\def\bv{\mathbf{v}}

\)

#### Dynamic programming

Finite horizon problems. Cost function. Backward induction. Idempotent rings.

(Use Blum’s notes.)

#### Sample problems

- If erasing a digit costs 2 cents, and correcting, 3 cents, what is the cheapest way to edit the sequences below so that they are the same?

1 7 6 7 6 8 5 6 5 0 3 1 2 1 3 6 7 9 5 3

to

3 4 4 5 6 7 6 5 1 9 3 6 2 3 9 3 4 1 7 2 -
In the \(15\times 20\)-array

8 6 0 1 8 2 0 0 8 9 2 5 0 8 4 7 0 7 8 2

2 0 4 7 6 0 4 9 9 5 6 2 5 7 3 3 4 0 3 4

7 2 5 6 9 1 8 4 5 9 0 8 0 4 3 6 8 8 7 3

1 6 2 8 7 7 0 3 7 7 2 3 1 6 3 5 3 5 2 3

0 8 3 7 8 8 2 2 2 2 2 2 6 3 3 2 8 1 8 1

3 3 9 1 7 2 7 5 4 0 2 6 0 6 5 0 5 8 2 3

2 1 4 6 9 2 4 8 5 9 0 4 7 9 9 0 1 5 4 6

0 2 4 5 0 7 4 1 4 9 6 4 8 1 9 5 1 7 8 6

3 0 3 3 2 7 6 5 4 2 6 1 2 8 1 9 2 9 3 2

4 5 0 4 5 0 8 5 0 7 5 7 2 1 3 7 8 6 5 0

5 1 0 3 7 8 7 8 6 8 5 7 8 0 5 9 0 7 5 6

9 4 0 4 2 3 6 2 5 6 9 9 9 8 4 2 1 4 4 7

5 2 1 9 1 5 5 1 7 2 4 0 7 0 6 3 4 7 8 6

6 6 5 9 4 9 0 3 9 3 3 5 5 0 0 2 0 7 3 5

1 3 6 1 1 7 2 9 1 6 8 1 0 9 5 3 1 9 5 9

find the least expensive path from upper left corner to lower right corner. The cost of a path is the sum of all entries it encounters; each step of the path is either South or East.

Hi Professor, should the insertion costs be added to problem 1? Without insertion, erasing can never make the first sentence the same as the second one. Thanks!

You edit both sequences.

For the first question, do we have cost for adding in a digit?

You are not allowed to add a digit. In other words, that cost is infinite.