Assignment 2
COMP3121/9101 22T1 Released March 3, due March 17
In this assignment we apply the greedy method and related graph algorithms. There are four problems, for a total of 80 points.
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 correct- ness of your algorithm. If a time bound is specified in the question, you also must argue that your algorithm meets this time bound.
Partial credit will be awarded for progress towards a solution.
1. (20 points) You are playing the popular card game “Inscribings”. In this game, your opponent places n monster cards onto the board, the ith of which has hi health points. You in turn have m ≥ n hero cards in your hand, the jth of which deals dj damage per turn. To begin the game, you will choose n heroes from your hand and assign each of them to a different enemy monster. Each turn, your heroes will deal damage equal to their damage power to the opposing enemy. If at any point an opponent’s monster reaches 0 health or less, then it is destroyed.
You are given a limited number of turns k to destroy all enemy monsters. Design an algorithm which runs in O(m + n log n) time and determines whether it is possible to assign your heroes in such a way as to destroy all enemy monsters in k turns or fewer. If it is possible, your algorithm must also return any such assignment.
Up to 15 points will be awarded for an algorithm which runs in Θ(m log m) time.
2. (20 points) Alice writes n distinct integers on a blackboard, and picks a positive integer K. She then allows Bob to make moves, each of which consist of the following steps.
1. Identify two integers x and y on the blackboard which differ by at most K, i.e. |x − y| ≤ K.
2. Erase the smaller of the two chosen integers.
Bob’s task is to make moves in this way until he is no longer able to do so. Note that in some cases, Bob may be unable to make even a single move.
Design an algorithm which runs in O(n log n) time and finds the longest sequence of moves. If there are several sequences of maximum length, you may find any of them.
3. (20 points) You are given a weighted, undirected graph G = (V,E) which is guar- anteed to be connected. Design an algorithm which runs in O(V E + V 2 log V ) time and determines which of the edges appear in all minimum spanning trees of G.
Up to 15 points will be awarded for an algorithm which runs in Θ(V E log V ) time. Up to 10 points will be awarded for an algorithm which runs in Θ(E2 log V ) time.
4. (20 points) There is an upcoming football tournament, and the n participating teams
are labelled from 1 to n. Each pair of teams will play against each other exactly once.
Thus, a total of n(n−1) matches will be held, and each team will compete in n − 1 of 2
these matches.
There are only two possible outcomes of a match:
1. The match ends in a draw, in which case both teams will get 1 point.
2. One team wins the match, in which case the winning team gets 3 points and the losing team gets 0 points.
Design an algorithm which runs in O(n2) time and provides a list of results in all n(n−1) matches which:
(a) ensures that all n teams finish with the same points total, and (b) includes the fewest drawn matches among all lists satisfying (a).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com