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!
Copyright By PowCoder代写 加微信 powcoder
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.
The clarifications may be updated further in the Assignment 4 FAQ thread on the Ed forum: https://edstem.org/au/courses/8646/discussion/937894.
General clarifications: Nil.
COMP3121/9101 22T2 — Assignment 4 (UNSW Sydney)
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.
You can arrive at a square from above or from the left. Which is better?
• Do the starting and ending squares contain any coins? No.
• What is the output format?
Only the maximum number of coins, not the optimal path.
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) = pixi.
As in 1.1, you can arrive at a square from above or from the left.
• What is expected value? What does the given formula mean?
Expected value is a calculation of the weighted average over all possible outcomes. The xi in the formula are outcomes (number of coins accumulated on a path), and the pi are the probabilities of those outcomes (probability of following that path). Note that you do not necessarily have to use this formula directly in your algorithm.
Recall the linearity of expectation: for random variables X and Y and constants a and b, we have E(aX + bY ) = aE(X) + bE(Y ).
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.
• Can a job be paused partway? No.
• Can a customer wait, in order to start later than their scheduled start time? No.
[12 marks] Design an algorithm which runs in O(n3) time and determines the maximum net earnings of the garage.
• What is the target time complexity?
We’ve increased it from O(n2) to O(n3). There is a (very difficult) quadratic time
solution, but cubic time solutions will now be eligible for full marks.
• Is the information about the customers known from the start? Yes. You know all si, ei, ai, bi, ci before any customers arrive.
COMP3121/9101 22T2 — Assignment 4 (UNSW Sydney)
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. • Does the input specify particular vertices u and v?
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 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 value m 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.
• What is the output format?
Only Yes or No, not the full list of matches.
First find a sufficient condition for an edge to not be useful, and then prove that it is also a necessary condition.
From each match, consider the player with higher skill level only. What should the total of their skill levels be?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com