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.

Leave a Reply