代写COMP3121、Python/Java程序设计代写

日期：2022-07-20 07:31

COMP3121/9101 22T2 — Assignment 4 (UNSW Sydney)

Due 28th July 2022 at 4pm Sydney time

In this assignment we apply dynamic programming. There are four problems each worth 20 marks,

for a total of 80 marks.

Your solutions must be typed, machine readable PDF files. All submissions will be checked for

plagiarism!

For each question requiring you to design an algorithm, you must justify the correctness of your

algorithm. If a time bound is specified in the question, you also must argue that your algorithm

meets this time bound.

To describe a dynamic programming algorithm, you must include:

the subproblem specification,

the recurrence,

any base cases,

how the overall answer is calculated, including (if necessary) the order in which the subprob-

lems are solved and

the time complexity analysis.

The recurrence, base cases and final answer calculation must each be accompanied with (often

brief) worded reasoning to justify the correctness of the algorithm.

Partial credit will be awarded for progress towards a solution.

Question 1

You are playing a video game, where you control a character in a grid with m rows and n columns.

The character starts at the square in the top left corner (1, 1), and must walk to the square in

the bottom right corner (m,n). The character can only move one square at a time downwards or

rightwards. Every square (i, j), other than the starting square and the ending square, contains a

known number of coins ai,j .

1.1 [10 marks] Design an algorithm which runs in O(mn) time and determines the maximum

number of coins that your character can accumulate by walking from (1, 1) to (m,n) using a

combination of downwards and rightwards moves.

1.2 [10 marks] After playing this game many times, you have broken the controller, and you

can no longer control your character. They now walk randomly as follows:

if there is only one possible square to move to, they move to it;

otherwise, they move right with probability p and down with probability 1 p.

Note that this guarantees that the character arrives at (m,n).

Design an algorithm which runs in O(mn) time and determines the expected number of coins that

your character will accumulate by walking from (1, 1) to (m,n) according to the random process

above.

Recall that for a discrete random variable X which attains values x1, . . . , xn with probabilities

p1, . . . , pn, the expected value of X is defined as

E(X) =n∑i=1pixi.

COMP3121/9101 22T2 — Assignment 4 (UNSW Sydney)

Question 2

You are managing a garage with two mechanics, named Alice and Bob. Each mechanic can serve

at most one customer at a time.

There will be n customers who come in during the day. The ith customer wants to be served for

the entire period of time starting at time si and ending at time ei. You may assume that the

customers are indexed by their order of arrival, i.e. s1 < s2 < . . . < sn.

For each customer i, the business will:

make ai dollars if customer i is served by Alice;

make bi dollars if customer i is served by Bob;

lose ci dollars if customer i is not served.

Your task is to maximise the net earnings of the garage, which is calculated as the total amount

made minus the total amount lost.

2.1 [8 marks] Consider the following greedy algorithm.

Process each customer i in order of arrival as follows.

If both Alice and Bob are available at time si:

– if ai ≥ bi, assign customer i to Alice;

– otherwise, assign the customer to Bob.

If only one mechanic is available at time si, assign customer i to that mechanic.

If neither mechanic is available at time si, do not serve customer i.

Design an instance of the problem which is not correctly solved by this algorithm. You must:

specify a number of customers n,

for each customer, provide values for si, ei, ai, bi and ci,

apply the greedy algorithm to this instance and calculate the net earnings achieved, and

? show that a higher net earnings figure can be achieved.

2.2 [12 marks] Design an algorithm which runs in O(n2) time and determines the maximum

net earnings of the garage.

Question 3

You are given a simple directed weighted graph with n vertices and m edges. The edge weights

may be negative, but there are no cycles whose sum of edge weights is negative.

3.1 [10 marks] An edge e is said to be useful if there is some pair of vertices u and v such that

e belongs to at least one shortest path from u to v.

Design an algorithm which runs in O(n3) and determines the set of useful edges.

3.2 [10 marks] An edge is said to be very useful if there is some pair of vertices u and v such

that e belongs to every shortest path from u to v.

Design an algorithm which runs in O(n3) and determines the set of very useful edges.

2

COMP3121/9101 22T2 — Assignment 4 (UNSW Sydney)

Question 4

There are 2n players who have signed up to a chess tournament. For all 1 ≤ i ≤ 2n, the ith player

has a known skill level of si, which is a non-negative integer. Let S =

∑2n

i=1 si, the total skill level

of all players.

In the tournament, there will be n matches. Each match is between two players, and each player

will play in exactly one match. The imbalance of a match is the absolute difference between the

skill levels of the two players. That is, if a match is played between the ith player and the jth

player, its imbalance is |si ? sj |. The total imbalance of the tournament is the sum of imbalances

of each match.

The organisers have provided you with a valuem which they consider to be the ideal total imbalance

of the tournament.

Design an algorithm which runs in O(n2S) time and determines whether or not it is possible to

arrange the matches in order to achieve a total imbalance of m, assuming:

4.1 [4 marks] all si are either 0 or 1;

4.2 [16 marks] the si are distinct non-negative integers.