week 14

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

4 Responses to week 14

1. Ann May 4, 2016 at 12:28 pm #

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!

• yuliy May 5, 2016 at 9:39 am #

You edit both sequences.

2. Tianyi He May 4, 2016 at 9:44 pm #

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

• yuliy May 5, 2016 at 9:36 am #

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