代写CS260语言程序、代写Java，Python编程

日期：2021-11-22 10:20

CS260: Algorithms

Class Test sample solutions

December 2020

1. (a) True; (b) True; (c) False; (d) False; (e) True; (f) False; (g) True; (h) True. br>2. (a) cS(1) = 5

cS(2) = 5 + 3 + 2 = 10

cS(3) = 5 + 3 = 8

(b) `S(1) = 3 · 5 = 15

`S(2) = 1 · 10 = 10

`S(3) = 2 · 8 = 16

LS = 15 + 10 + 16 = 41

(c) We have:

LS ? LS′ = (`S(1) + `S(2))? (`S′(1) + `S′(2))

= (u[1]t[1] + u[2](t[1] + t[2]))? (u[2]t[2] + u[1](t[2] + t[1]))

= u[2]t[1]? u[1]t[2],

and hence schedule S = (1, 2) has smaller total urgency-weighted lateness than sched-

ule S′ = (2, 1) if and only if u[2]t[1]? u[1]t[2] < 0, which is equivalent to:

u[1]

t[1]

>

u[2]

t[2]

.

(d) An algorithm. Output the schedule in which jobs are ordered by non-increasing ratios

u[j]/t[j].

Algorithm correctness. Firstly, we slightly generalize the analysis from part (c) to

the result of swapping a pair of consecutive jobs in any schedule.

Fact 1. If S = (j1, j2, . . . , jn) is a schedule and S

′ is the schedule obtained from S by

swapping the order of the two jobs ji and ji+1 that are consecutive in S, then LS ?LS′ =

u[ji+1]t[ji]? u[ji]t[ji+1].

Proof. Note that the completion time of all jobs other than ji or ji+1 is the same in

schedules S and S′. It follows that also the urgency-weighted lateness of jobs other

than ji or ji+1 is the same in schedules S and S

′. Let T be the completion time of the

job immediately preceding job ji in S, which is the same as the completion time of the

job immediately preceding job ji+1 in S

′ (or 0 if i = 1). We then have:

LS ? LS′ = (`S (ji) + `S (ji+1))? (`S′ (ji+1) + `S′ (ji))

= u[ji] (T + t [ji]) + u[ji+1] (T + t[ji] + t[ji+1])

? u[ji+1] (T + t[ji+1])? u[ji] (T + t[ji+1] + t[ji])

= u[ji+1]t[ji]? u[ji]t[ji+1] .

1

Without loss of generality, rename all the jobs 1, 2, . . . , n so that the output of our

algorithm is the schedule (1, 2, . . . , n). Note that we then have:

u[1]

t[1]

≥ u[2]

t[2]

≥ · · · ≥ u[n]

t[n]

.

We say that a schedule is optimal if it is a schedule that minimizes the total urgency-

weighted lateness.

Fact 2. Schedule (1, 2, . . . , n) is optimal.

Proof. We say that (i, k) is an inversion in schedule (j1, j2, . . . , jn) if i < k and ji > jk.

Note that (1, 2, . . . , n) is the only schedule with 0 inversions.

Let S? = (j1, j2, . . . , jn) be an optimal schedule with the smallest number of inversions.

We argue that the number of inversions in S? is 0, and hence S? = (1, 2, . . . , n).

For the sake of contradiction, suppose that there is at least one inversion in S?. Then

there is at least one adjacent inversion (i, i + 1). Note that the schedule S? obtained

from S? by swapping the order of jobs i and i+1 has one less inversion than S?. We show

that the total urgency-weighted lateness of S? is no larger than that of S?, and hence S?

is also optimal, which contradicts S? being an optimal schedule with the smallest number

of inversions.

Since (i, i + 1) is an inversion, we have ji > ji+1, which implies that:

u[ji+1]

t[ji+1]

≥ u[ji]

t[ji]

,

and hence u[ji+1]t[ji] ≥ u[ji]t[ji+1]. It then follows from Fact 1 that:

LS? ? LS? = u[ji+1]t[ji]? u[ji]t[ji+1] ≥ 0 ,

and hence schedule S is also optimal because LS? ≤ LS? .

Asymptotic running time. If Merge Sort or Heap Sort are used to sort the jobs by

non-increasing ratios u[j]/t[j] then the algorithm runs in O(n log n) time.

2

3. (a) This greedy algorithm is correct.

Without loss of generality, renumber files in such a way that the algorithm considers them

by increasing file number; note that then we have S[1] ≤ S[2] ≤ · · · ≤ S[n].

Suppose that S = { i1, i2, . . . , ik } is an optimal solution, that is k is the maximum number

of files that can be stored on the device. Without loss of generality, assume that i1 <

i2 < · · · < ik, and note that

∑k

j=1 S[ij ] ≤ C.

Observe that for every j = 1, 2, . . . , k we have j ≤ ij , and hence S[j] ≤ S[ij ]. This implies

that the greedy algorithm will select at least k files because

∑k

j=1 S[j] ≤

∑k

j=1 S[ij ] ≤ C.

(b) This greedy algorithm is not correct.

Consider three files of sizes 2, 2, and 3, respectively, and a device with capacity 4. The

algorithm will select one file of size 3, while the optimal solution selects the two files of

sizes 2 and 2.

(c) Given an instance I of this problem:

device capacity C;

file sizes S[1], S[2], . . . , S[n];

star ratings R[1], R[2], . . . , R[n];

consider the following instance I ′ of the knapsack problem:

knapsack capacity C;

item weights S[1], S[2], . . . , S[n];

item values R[1], R[2], . . . , R[n].

It is routine to argue that a set S ? { 1, 2, . . . , n } is an optimal solution of instance I if

and only if it is an optimal solution of instance I ′ of the knapsack problem.

Each such instance I ′ of the knapsack problem can be solved in time O(nC), because the

running time of the standard dynamic programming algorithm for the knapsack problem

is O(nW ) where W is the capacity of the knapsack.

(d) For capacity C = 2 and arrays S = [2, 1, 2] and R = [3, 2, 0], the star-rating-per-size

ratios are 3/2, 2, and 0, and hence the algorithm will select only file 2, achieving total

star rating 2.

Instead, the optimal solution is to select only file 1, achieving total star rating 3.