CS260程序代写、代写c++编程

日期：2021-10-31 11:21

CS260 Algorithms

Class Test

30 November 2020

Answer: BOTH Question 1. AND EXACTLY ONE of Questions 2. or 3.

MAKE IT CLEAR on the first page whether you have answered Question 2. or Question 3.

Only one of them will be marked so do not attempt to answer both.

Submit ONE PDF FILE to Tabula after 9am and BEFORE 9:45am.

Late submissions will receive 0 marks.

(Further instructions have been discussed on the General channel

in the CS260: Algorithms (20/21) group on Teams.)

1. [40 marks] For each of the following statements, indicate whether it is true or false.

Justifications are not required. You will be awarded +5 points for each correct answer and

?5 points for each incorrect or missing answer. Your mark for Question 1. will be the sum

of the awarded points, or it will be 0 if the sum is negative.

(a) If an algorithm runs in O(n3) time in the worst case, then it is possible that it runs in

O(n2 log n) time on all inputs.

(b) Every minimum spanning tree of a graph G is also a minimum spanning tree of the graph

obtained from G by multiplying the cost of every edge by 2020.

(c) A largest-cost edge in some cutset of a graph G cannot belong to a minimum spanning

tree of G.

(d) In graphs with n vertices and m = ?(nlog2 3) edges, a version of Dijkstra’s algorithm that

uses the unsorted array implementation of priority queues has better asymptotic running

time than if it uses the binary heap implementation.

(e) The shortest paths tree computed by Dijkstra’s algorithm in an undirected connected

graph is always a spanning tree of the graph.

(f) Suppose that algorithm A, on inputs of size n, makes five recursive calls on inputs of

size n/2, and combines the results in time Θ(n2); and algorithm B, on inputs of size n,

makes seven recursive calls on inputs of size n/3, and combines the results in time Θ(n2).

Then algorithm A is asymptotically faster than algorithm B.

(g) The Master Theorem for divide-and-conquer recurrences is applicable to the following

recurrence:

T (n) ≤

{

2020 if n ≤ 42,

2 · T (dn/4e) + 3 · T (n? b3n/4c) + 7n if n > 42.

(h) There is an O(mk) time algorithm for computing single-source shortest paths in connected

graphs with m edges, without negative cycles, and in which every simple path from the

source vertex has at most k edges.

1

2. We have to schedule n jobs, one after another, on one machine. The processing times of jobs 1,

2, . . . , n are positive numbers t[1], t[2], . . . , t[n], and their urgency factors are positive numbers

u[1], u[2], . . . , u[n], respectively.

A schedule is a permutation of all n jobs; for example, S = (1, 3, 2) is a schedule that first

completes job 1, then job 3, and finally job 2. The completion time of a job in a schedule S =

(j1, j2, . . . , jn) is the time it waits until it has been processed; in other words, the completion

time of the i-th job ji in schedule S is:

cS(ji) = t[j1] + t[j2] + · · ·+ t[ji].

The urgency-weighted lateness of job j in schedule S is defined to be:

`S(j) = u[j] · cS(j).

The total urgency-weighted lateness of schedule S is defined by:

LS = `S(1) + `S(2) + · · ·+ `S(n).

We are interested in finding a schedule that minimises total urgency-weighted lateness.

(a) [10 marks] Suppose that we have three jobs 1, 2, and 3 with the following processing

times and urgency factors:

Job j 1 2 3

Processing time t[j] 5 2 3

Urgency factor u[j] 3 1 2

What are the completion times cS(1), cS(2), and cS(3) of jobs 1, 2, and 3 in schedule S =

(1, 3, 2)?

(b) [10 marks] What is the urgency-weighted lateness `S(1), `S(2), and `S(3) of jobs 1, 2,

and 3, respectively, in schedule S from part (a)?

What is the total urgency-weighted lateness LS of schedule S?

(c) [10 marks] If there are just two jobs 1 and 2, then there are just two possible schedules:

(1, 2) and (2, 1).

Write the expression L(1,2) ? L(2,1) as a function of t[1], t[2], u[1], and u[2], and analyse

its sign to characterise when schedule (1, 2) has smaller total urgency-weighted lateness

than schedule (2, 1).

(d) [30 marks] Design a polynomial-time algorithm that—given the tables t[1..n] and u[1..n]

of processing times and urgency factors of jobs 1, 2, . . . , n—computes the schedule that

minimises total urgency-weighted lateness.

2

3. You have n video files 1, 2, . . . , n that you want to put on your storage device. For every

i = 1, 2, . . . , n, file i has size S[i] (say, it requires S[i] gigabytes of space), which is a positive

integer. The capacity of the storage device is C (gigabytes), which is a positive integer.

Unfortunately, not all of the files can fit on the device, because together they exceed the

capacity:

∑n

i=1 S[i] > C.

(a) [15 marks] Suppose that you want to maximize the number of video files stored on the

device.

Consider the greedy algorithm that looks at the files in the order of increasing sizes, and

that accepts each if and only if doing so does not exceed the capacity.

Either prove that this algorithm is correct or provide a counter-example.

(b) [15 marks] Suppose that you want to use as much of the capacity of the device as

possible.

Consider the greedy algorithm that looks at files in the order of decreasing sizes, and that

accepts each if and only if doing so does not exceed the memory capacity.

Either prove that this algorithm is correct or provide a counter-example.

(c) [15 marks] Assume that for every i = 1, 2, . . . , n, video file i has additionally a star

rating R[i], which is an integer between 0 and 5, given by your favourite film critic.

Suppose that you want to maximize the sum of the star ratings of the video files stored

on the device.

Argue that the algorithmic problem of selecting such an optimal collection of files is a

special case of the knapsack problem. State and justify the asymptotic running time of

an algorithm for solving the knapsack problem as applied to the optimal file selection

problem considered here.

(d) [15 marks] Consider a greedy algorithm for the problem in part (c) that looks at video

files in the order of decreasing ratio of their star rating per size, and accepts each if and

only if doing so does not exceed the capacity. Give an example input with 3 video files

for which this algorithm gives an incorrect output.