Scribd Logo
Upload

Welcome to Scribd!

  • 51 views

    Dynamic Programming Applications

    Uploaded by

    Jaya Bisht
    The document describes using dynamic programming to solve several problems: 1. Finding the longest increasing subsequence in a sequence of numbers by computing the length of the longest subsequence ending at each number. 2. Encoding text for high density barcodes by considering the optimal encoding that ends in each possible mode for a prefix. 3. Matching line segments between two images to morph one into the other using operations like full run matching, merging runs, and splitting runs. Dynamic programming finds the lowest cost matching.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Dynamic Programming Applications

    Uploaded by

    Jaya Bisht
    51 views9 pages
    The document describes using dynamic programming to solve several problems: 1. Finding the longest increasing subsequence in a sequence of numbers by computing the length of the longest subsequence ending at each number. 2. Encoding text for high density barcodes by considering the optimal encoding that ends in each possible mode for a prefix. 3. Matching line segments between two images to morph one into the other using operations like full run matching, merging runs, and splitting runs. Dynamic programming finds the lowest cost matching.

    Original Description:

    Programming Applications

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes using dynamic programming to solve several problems: 1. Finding the longest increasing subsequence in a sequence of numbers by computing the length of the longest subsequence ending at each number. 2. Encoding text for high density barcodes by considering the optimal encoding that ends in each possible mode for a prefix. 3. Matching line segments between two images to morph one into the other using operations like full run matching, merging runs, and splitting runs. Dynamic programming finds the lowest cost matching.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    51 views9 pages

    Dynamic Programming Applications

    Uploaded by

    Jaya Bisht
    The document describes using dynamic programming to solve several problems: 1. Finding the longest increasing subsequence in a sequence of numbers by computing the length of the longest subsequence ending at each number. 2. Encoding text for high density barcodes by considering the optimal encoding that ends in each possible mode for a prefix. 3. Matching line segments between two images to morph one into the other using operations like full run matching, merging runs, and splitting runs. Dynamic programming finds the lowest cost matching.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 9

    16.3-5 Give an  2 algorithm to nd the longest montonically increasing sequence in a sequence of numbers.

    O n ; ; ; ; ; ;

    Build an example rst: 5 2 8 7 1 6 4 Ask yourself what would you like to know about the rst , 1 elements to tell you the answer for the entire sequence? 1. The length of the longest sequence in 1 2 n,1 . seems obvious 2. The length of the longest sequence n will extend! not as obvious - this is the idea! Let i be the length of the longest sequence ending with the th character:
    n s ;s ;:::;s s s i

    sequence 5 2 8 7 3 1 6 4 i 1 1 2 2 2 1 3 3
    s

    How do we compute ? i = max0 j i;seq j seq i j + 1 0=0 To nd the longest sequence - we know it ends somewhere, so Length = maxn=1 i i
    si s s s s

    To use dynamic programming, the problem must observe the principle of optimality, that whatever the initial state is, remaining decisions must be optimal with regard the state following from the rst decision. Combinatorial problems may have this property but may use too much memory time to be e cient.

    The Principle of Optimality

    Let  ; 1 2 k  be the cost of the optimal tour for to 1 that goes thru each of the other cities once
    T i j ;j ;:::;j i T

    Example: The Traveling Salesman Problem


    i i ;j ;:::;j

    ;

    1 2

    i = M in1mk C
    T i; j C i; j

    i; j

    m T jm; j1; j2; : : : ; jk 

      =   +  1
    C j; j ;j ;:::;j

    Here there can be any subset of 1 2 k instead of any subinterval - hence exponential. Still, with other ideas some type of pruning or bestrst search it can be e ective for combinatorial search. SHOW PICTURE OF PRUNING TREE

    Dynamic programming computes recurrences e ciently by storing partial results. Thus dynamic programming can only be e cient when there are not too many partial results to compute! There are ! permutations of an -element set we cannot use dynamic programming to store then best solution for each subpermutation. There are 2 subsets of an -element set we cannot use dynamic programming to store the best solution for each. However, there are only  , 1 2 continguous substrings of a string, each described by a starting and ending point, so we can use it for string problems. There are only  , 1 2 possible subtrees of a binary search tree, each described by a maximum and minimum key, so we can use it for optimizing binary search trees. Dynamic programming works best on objects which are linearly ordered and cannot be rearranged characters in a string, matrices in a chain, points around the boundary of a polygon, the left-to-right order of leaves in a search tree. Whenever your objects are ordered in a left-to-right way, you should smell dynamic programming!
    n n n n n = n n =

    When can you use Dynamic Programming?

    A triangulation of a polygon is a set of non-intersecting diagonals which partiions the polygon into diagonals.

    Minimum Length Triangulation

    The length of a triangulation is the sum of the diagonal lengths. We seek to nd the minimum length triangulation. For a convex polygon, or part thereof:
    k i j

    Once we identify the correct connecting vertex, the polygon is partitioned into two smaller pieces, both of which must be triangulated optimally!
    t i; i

    t i; j

    +1 = 0 j = min k=i

    t i; k

    t k; j

    +j j+j j
    ik kj

    Evaluation proceeds as in the matrix multiplication ex ample - 2 values of , each of which takes  ,  time if we evaluate the sections in order of increasing size.
    n t O j i
    1 J-i = 2 13, 24, 35, 46, 51, 62 6 J-i = 3 14, 25, 36, 41, 52, 63 3 4 5 J-i = 4 15, 26, 31, 42, 53, 64 Finish with 16 2

    What if there are points in the interior of the polygon?

    Symbol Technology has developed a new design for bar codes, PDF-417 that has a capacity of several hundred bytes. What is the best way to encode text for this design?

    Dynamic Programming and High Density Bar Codes

    They developed a complicated mode-switching data compression scheme.


    ALPHA latch latch latch shift LOWER CASE shift OTHER CHARS latch latch shift MIXED latch

    Latch commands permanently put you in a di erent mode. Shift commands temporarily put you in a different mode.

    Originally, Symbol used a greedy algorithm to encode a string, making local decisions only. We realized that for any pre x, you want an optimal encoding which might leave you in every possible mode.
    The Quick Brown Fox Alpha Lower Mixed Punct.

    = min , 1 + the cost of encoding the th character and ending up in node . Our simple dynamic programming algorithm improved to capacity of PDF-417 by an average of 8!
    M i; j M i ;k i j

    Morphing is the problem of creating a smooth series of intermediate images given a starting and ending image. The key problem is establishing a correspondence between features in the two images. You want to morph an eye to an eye, not an ear to an ear. We can do this matching on a line-by-line basis:
    Object As segments
    T=0 T = 0.5 T=1

    Dynamic Programming and Morphing

    Object Bs segments

    This should sound like string matching, but with a different set of operations: Full run match: We may match run on top to run on bottom for a cost which is a function of the di erence in the lengths of the two runs and their positions. Merging runs: We may match a string of consecutive runs on top to a run on bottom. The cost will be a function of the number of runs, their relative positions, and lengths.
    i j

    Splitting runs: We may match a big run on top to a string of consecutive runs on the bottom. This is just the converse of the merge. Again, the cost will be a function of the number of runs, their relative positions, and lengths. This algorithm was incorported into a morphing system, with the following results:

    You might also like