Math 560 Optimization

Math 560 Homework 7 Fall 2020
Due: Tuesday, November 3

  1. 【Math 560 Optimization】Ski Optimization!1
    You have been hired as a consultant at the famed Forty-Two Black Diamonds Ski
    Resort. They will let you ski all winter for free in exchange for helping their ski rental
    shop with an algorithm to assign skis to skiers.
    Ideally, each skier should obtain a pair of skis whose height matches his or her own
    height exactly. Unfortunately, this is generally not possible. We define the disparity
    between a skier and his or her skis to be the absolute value of the different between the
    height of the skier and the pair of skis. Your objective is to find an assignment
    of skis to skiers that minimizes the sum of the disparities between all of the
    skiers and their skis.
    The input to this problem is an array of n skiers (represented just by their heights)
    and an array of m ≥ n pairs of skis (each ski pair is represented as just the height of
    the skis). These arrays are given in sorted order from shortest to tallest. For example,
    we might have (in inches):
    skiers = [61 67 73]
    skis = [58 62 66 68 72]
    (a) [1pt] The infamous Prof. I.M. Rong from the Pasadena Institute of Technology
    is trying to steal your job. He proposes the following simple and fast ‘greedy’
    algorithm for the problem:
    ‘The skiers and skis are already sorted from shortest to tallest. So, consider the
    skiers one-by-one from shortest to tallest. For each skier under consideration, assign
    that skier the pair of skis that most closely match that skier’s height. Then
    remove that skier and pair of skis from consideration and repeat the process.’
    Find a small example where Prof. I.M. Rong’s algorithm gives a solution that
    is worse than the optimal solution. You will need to provide a particular small
    set of skier heights, a small set of ski heights, show the solution that Prof. I.M.
    Rong’s algorithm would produce, and then show a solution that is better.
    ANSWER: Consider the set:
    skiers = [60 65]
    skis = [55 61]
    According to Prof. I.M. Rong’s algorithm, we would first consider the skier of
    height 60 and assign the skis of height 61. This leave the skis of height 55 for the
    1Adapted from problem sets created by Harvey Mudd College CS Professor Ran Libeskind-Hadas.
    1
    skier of height 65. This solution has a disparity of 1 + 10 = 11. It is clearly better
    in this case to give the height 55 skis to the height 60 skier, and the height 61
    skis to the height 65 skier, for a disparity of 5 + 4 = 9.
    (b) [1pt] Often, we need to infer (and prove) a mathematical fact about our problem
    that we can exploit in developing our algorithm. Another consultant, Prof. Sue
    Persmart, made the following conjecture: If we have a short person and a tall
    person, it is never better to give the shorter person a taller pair of skis than were
    given to the tall person (we will call this an inversion). Your task is to prove this
    conjecture!
    Specifically: Let x and y be the heights of two skiers with x < y and let sx and
    sy be the heights of the skis with sx > sy. We’d like to show that if the person
    with height x is given the skies with height sx and the person with height y is
    given the skies with height sy, then switching the skis between these two skiers
    would not increase the disparity (i.e., removing the inversion does not make the
    solution any worse).
    One way to do this is to break the analysis up into a number of cases such as the
    case x < y < sy < sx, or the case x < sy < sx < y, etc. If you choose to use this
    approach, list the cases that you would need to consider and then analyze just
    one of these cases. (This is intended to save you time, because we trust that if
    you can do one case, you could do them all!)
    ANSWER: There are six cases to consider:
    x < sy < sx < y
    x < sy < y < sx
    x < y < sy < sx
    sy < x < sx < y
    sy < sx < x < y
    sy < x < y < sx
    Let’s consider the case where x < y < sy < sx. In this case, when x is given sx
    and y is given sy, the disparity is
    |sx ? x| + |sy ? y|.
    If the skis were switched, then the disparity would be
    |sx ? y| + |sy ? x|.
    Now, since x < y < sy < sx, we know that all four quantities sx ?x, sy ?y, sx ?y,
    and sy ? x are positive. Therefore, both of the above disparities simplify to
    |sx ? x| + |sy ? y| = sx + sy ? x ? y = |sx ? y| + |sy ? x|.
    2
    Therefore swapping the skis did not increase the disparity.
    We can do this for all six cases, and so we can conclude that removing an inversion
    never leads to a worse solution. This tells us that there is an optimal solution that
    does not have an inversion. If we have an optimal solution that has inversions,
    we can remove those inversions without making the solution worse, and would
    therefore still have an optimal solution (but without inversions).
    (c) [1pt] Assume that there are n skiers and n pairs of skis. Describe (in English)
    a fast algorithm for assigning skis to skiers, briefly explain how the proof of correctness
    would work (using the result from part (b)), and give the running time
    of your algorithm.
    For part (d), you may assume that you have a function that correctly implements
    this algorithm and optimally assigns the n skis to the n skiers, returning the optimal
    disparity:
    partC(skiers[0:n], skis[0:n])
    ANSWER: From part (b), we concluded that we can always find an optimal solution
    without inversions. Note that when there are the same number of skis and
    skiers, there is only one solution without inversions: assign the smallest skis to
    the smallest skier, the second smallest skis to the second smallest skier, etc. This
    will take O(n) time.
    Note: we could also have assigned the largest ski to the largest skier, etc. This
    would have given the same assignment since there are equal numbers of skis and
    skiers.
    3
    (d) Finally, consider the general case that m ≥ n.
    i. [3pts] In simple and clear pseudo-code or English, describe a recursive algorithm
    for solving this problem. For now, assume that ‘solving’ means just
    returning the number which is the sum of the disparities in an optimal solution.
    Make sure to describe the base cases and the recursive call(s).
    ANSWER: In my recursive function, I will consider the smallest ski and the
    smallest skier. I will then decide whether to assign that ski to that skier
    (use-it), or skip that pair of skis (lose-it). Note that we cannot skip a skier.
    def assignSkis(skiers, skis, i, j):
    Returns the minimum disparity whenassigning skiers[i:n] and skis[j:m].Note: n = len(skiers) and m = len(skis).n = len(skiers)
    m = len(skis)
    No more skiers who need skis, so 0 more disparity.if i = n:
    return 0
    Same number of skis and skiers remaining, return from part (c).elif n-i == m-j:
    partC(skiers[i:n], skis[j:m])
    Go to use-it or lose-it strategy.else:
    Use-it: assign the shortest skis to the shortest skier andsee what happens.Note that we have to add the disparity from this match.useIt = |skiers[i]-skis[j]| + assignSkis(skiers, skis, i+1, j+1)
    Lose-it: don’t assign the shortest skis to the shortest skier.Note that it is never better to assign these skis to a tallerskier since that would result in an inversion.So this case is: don’t use the shortest skis at all.loseIt = assignSkis(skiers, skis, i, j+1)
    Return whichever case gave the smallest disparity.return min(useIt, loseIt)
    4
    ii. [2pts] Next, describe how you would implement this algorithm using dynamic
    programming. In particular, describe what the DP table looks like and the
    order in which the cells would be filled in. A picture may help (although the
    picture alone will not be graded). For those of you interested in practical
    implementation, it may be informative to write the actual DP pseudo-code
    for filling the table.
    Note: there are dozens of ways to setup this table. I chose this method because
    I like having the solution live in the bottom right corner.
    ANSWER: Put skis across the top and skiers down the side (in reverse
    order, since we are removing from the front rather than from the
    back - so i + 1 is up and j + 1 is left).
    Also, remember that the remaining skiers are [i:n] and the remaining skis
    are [j:m].
    ? Everything below the main diagonal from the upper-left corner does not
    have to be considered, because those correspond to cases where there are
    more skiers than skis remaining, which is not allowed.
    ? The top row is a base case where there are no skiers, so fill it with 0.
    ? The main diagonal from the upper-left corner is a base case where there
    are the same number of skiers and skis remaining. So this diagonal can
    be filled using partC(skiers[0:n], skis[0:n]), which doesn’t require
    any recursive calls. It will, however, require k work for the kth element
    in this diagonal (assigning k skis to k skiers and summing the k different
    disparities).
    ? For any given square in our table, we will either need the value directly
    left (the lose-it case with one fewer set of skis, since j + 1 is left) or the
    value diagonal to the upper-left (the use-it case with one fewer set of skis
    and one fewer skiers, since i + 1 is up and j + 1 is left).
    ? We have the top row and the main diagonal filled from base cases, so we
    can now fill in the table one row at a time, left-to-right, starting with
    second row.
    ? We could also fill in the table one column at a time, left-to-right, starting
    with second column.
    ? It is slightly better to fill in the table one diagonal at a time, left-to-right.
    This way, we can stop when we reach the bottom right element and avoid
    an extra n
    2/2 elements.
    5
    My table will look like this:
    (continued on next page)
    6
    iii. [1pt] What is the running time of your algorithm?
    ANSWER: We have two parts of the algorithm to count: filling in the base
    cases, and filling in the rest of the table.
    Note that the base cases along the first row simply take n work to fill in the
    n zeros, but the base cases along the diagonal require k work to compute the
    kth entry on this diagonal. So the total work for filling in the base cases is:
    n + (1 + 2 + · · · + n) ∈ O(n
    2
    ).
    Note that this can actually be done faster by using the use-it (no lose-it option
    for this diagonal) approach to iteratively fill in the main diagonal, taking
    O(n) time instead.
    Now consider the work to fill in the rest of the table. If we filled across rows
    or down columns, we would have to fill in mn ? n
    2/2 + n =∈ O(mn) cells,
    each taking constant time, for a total of O(mn) time.
    If we filled down a diagonal, we would have skipped an extra n
    2/2 cells. So
    now we would have to fill mn ? n
    2
    cells. Along with the time to fill the main
    diagonal (quickly), this gives a total work of mn ? n
    • n. We can now make
      one an observation: we have been guaranteed that there are always more skis
      than skiers, and so m ≥ n. Therefore mn ≥ n
      2
      , and so the overall runtime is
      O(mn). This is not always a tight bound, because if m = n + c, the runtime
      would give
      mn ? n
    • n = n
    • cn ? n
    • n = (c + 1)n ∈ O(n).
      Very technically, the tight bound we should report is:
      O(mn ? n
      2
      ).
      This trick will not work if we filled by rows or columns, because the runtime
      was mn ? n
      2/2 + n, and so the n
      2
      terms wont actually cancel.
      iv. [1pt] Briefly, describe how you could reconstruct an actual optimal solution
      matching skiers with skis using your DP table.
      ANSWER:
      ? If the value in a given cell is the same as the value in the cell immediately
      to its left, then we were in the lose-it case. Else, the use-it case.
      ? If we were in the lose-it case, then the skis for that column were not used
      at all. Skip those skis and move on to the cell directly to the left.
      ? If we were in the use-it case, then the skis for that column were assigned
      to the skier from that row. Assign those skis to that skier, and move on
      to the cell diagonally to the upper-left.

    推荐阅读