Math 560代写、代写Python，c/c++程序

日期：2021-11-26 09:26

Math 560 Homework 7 Fall 2020

Due: Tuesday, November 3

1. 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 when

# assigning 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 and

# see 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 taller

# skier 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

2 + 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

2 + n = n

2 + cn ? n

2 + 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.

7