Tutorial 3 – Solutions
COMP3121/9101
1. There are N robbers who have stolen N items. You would like to distribute the items among the robbers (one item per robber). You know the precise value of each item. Each robber has a particular range of values they would like their item to be worth (too cheap and they will not have made money, too expensive and they will draw a lot of attention). Devise an algorithm that either distributes the items so that each robber is happy or determines that there is no such distribution.
Solution: Order the items so that their values are increasing. Take the lowest value item v1 and consider all thieves such that v1 is in their range of acceptable values. Pick the one with the smallest upper limit and give the first item to that thief. Continue in this manner considering the item with the next smallest value v2 and so forth.
Copyright By PowCoder代写 加微信 powcoder
We now need to prove that this method is optimal. For each thief i let Li be their lowest acceptable value and let Ui be their highest acceptable value. As- sume that there is an assignment of items to thieves which satisfies all thieves, but which is different to that obtained by our greedy strategy. This means there is at least one item assignment which violates our greedy assignment pol- icy. Let item k with value vk be the least valuable such item, and suppose that this item was assigned to thief i (so vk ∈ [Li, Ui]). Since this item assignment violated our greedy policy, there must be another thief j (with range [Lj,Uj]) who would have been happy with item k, but whose highest acceptable value is lower than thief i’s, so vk ∈ [Lj,Uj] and Uj < Ui. Now suppose this thief was assigned an item m with value vm (so vm ∈ [Lj , Uj ]). Since item k is the least value item for which our greedy strategy was violated, vk < vm. Hence, vm ∈ [Li,Ui], which means that thief i would be happy with item m, and we can therefore swap the assignments for the two thieves while keeping them both happy. By repeatedly swapping assignments that violate our greedy strategy in this manner, we eventually reach an assignment that adheres to our strategy. Therefore, our method is optimal.
2. (Timing Problem in VLSI chips) Consider a complete binary tree with n = 2k leaves. Each edge has an associated positive number that we call the length of the edge (see figure below). The distance from the root to a leaf is the sum of the lengths of all edges from the root to the leaf. The root emits a clock signal and the signal propagates along all edges and reaches each leaf in time proportional to the distance from the root to that leaf. Design an algorithm which increases the lengths of some of the edges in the tree in a way that ensures that the signal reaches all the leaves at the same time while the total sum of the lengths of all edges is minimal. (For example, in the picture below if the tree A is transformed into trees B and C all leaves of B and C have a distance of 5 from the root and thus receive the clock signal at the same time, but the sum of the lengths of the edges in C is 17 while sum of the lengths of the edges in B is only 15.)
Solution: We proceed by recursion, working from the leaves towards the root. Consult the figure below.
nlnlnL kmpq MMQQMMQQ
M = max{k,m}; Q = max{p,q}; If M + n > Q + l L= M+n-Q
We start with the edges connecting two adjacent leaves. Clearly, they have to be of the same length. Thus, referring to the figure, we let M = max{k,m} and Q = max{p,q} and change the shorter length of the two to the value of the longer length. Moving one level up, we consider M + n and Q + l. If
321212 2233 21134433
M+n>Q+l,thenweincreaseltoL=M+n−Q,sothatM+n=Q+L. If Q+l>M+n,thenweincreasentoN =Q+L−M sothatM+N =Q+l.
We continue in this manner; assuming that we have made the lengths of all paths to all leaves of the subtree T1 equal to M and the lengths of all paths to all leaves of the subtree T2 equal to Q, we consider the edges connecting a vertex V to the roots of these subtrees. Assuming that the edge connecting V to the root of T1 is of length n and that the edge connecting V to the root of T2 is of length l; if M +n > Q+l we replace the edge of length l with an edge of length M +n−Q; if Q+l > M +n we replace the edge of length n with an edge of length Q + l − M. Clearly, the produced tree is of minimal total length with equal distances from the root to all leaves.
3. Assume that you are given a complete graph G with weighted edges such that all weights are distinct. We now obtain another complete weighted graph G′ by replacing all weights w(i, j) of edges e(i, j) with new weights w(i, j)2.
(a) Assume that T is the minimal spanning tree of G. Does T necessarily remain the minimal spanning tree for the new graph G′?
(b) Assume that p is the shortest path from a vertex u to a vertex v in G. Does p necessarily remain the shortest path from u to v in the new graph G′?
(a) Yes; just repeat Kruskal’s algorithm with the new weights. The ordering of the edges does not change so the same minimum spanning tree will be produced.
(b) No; consider for example a graph G with vertices A, B, C and D and edgesAB=1,BD=5,AC=3,CD=4,AD=7andBC=8. Then the shortest path from A to D in G is ABD with length 6, while the path ACD is longer, with length 7. However, after squaring all the weights, the length of ABD becomes 1 + 25 = 26, while the length of ABD becomes 9 + 16 = 25 which is shorter.
4. Assume that you are given a complete weighted graph G with n vertices v1, . . . , vn and with the weights of all edges distinct and positive. Assume that you are also given the minimum spanning tree T for G. You are now given a new vertex vn+1 and the weights w(n + 1, j) of all new edges e(n + 1, j) between the new vertex vn+1 and all old vertices vj ∈ G, 1 ≤ j ≤ n. Design an algorithm which produces a minimum spanning tree T′ for the new graph containing the additional vertex vn+1 and which runs in time O(n log n).
Solution: It should be clear that only the new edges and the edges of the old minimum spanning tree have a chance of being included in the new minimum spanning tree. Thus, to obtain a new spanning tree just run Kruskal’s algorithm on the n − 1 edges of the old spanning tree plus the n new edges. The runtime of the algorithm will be O(n log n).
5. You have n items for sale, numbered from 1 to n. Alice is willing to pay a[i] > 0 dollars for item i, and Bob is willing to pay b[i] > 0 dollars for item i. Alice is willing to buy no more than A of your items, and Bob is willing to buy no more than B of your items. Additionally, you must sell each item to either Alice or Bob, but not both, so you may assume that n ≤ A+B. Given n,A,B,a[1…n] and b[1…n], you have to determine the maximum total amount of money you can earn in O(n log n) time.
Solution: Let d[i] = |a[i] − b[i]|; sort all d[i] in a decreasing order and re-index all the items such that |a[1] − b[1]| is the largest difference and so on, the ith item being such that d[i] = |a[i] − b[i]| is the ith difference in size. We now go through the list giving the ith item to Alice if a[i] > b[i] and the total number of items given to Alice thus far is at most A and giving instead this item to Bob if b[i] > a[i] and the total number of items given to Bob thus far is at most B. If at certain stage A is reached we give all the remaining items to B and similarly if B is reached we give all the remaining items to A. If neither A nor B are reached and there are leftover items for which d[i] = 0, i.e., such that a[i] = b[i] we give them to either Alice or Bob making sure neither A nor B is exceeded.
To see that this algorithm is optimal, let m[i] = min(a[i], b[i]). Then regardless of who gets item i you get at least the amount m[i], plus you get the amount d[i] if item i is given to the higher bidder. Our algorithm tries to get as many d[i]’s as possible, preferentially taking as large d[i]’s as possible, so the algorithm is clearly optimal.
Computing all the differences d[i] = |a[i] − b[i]| takes O(n) time; sorting d[i]’s takes O(nlogn) time and going through the list takes O(n) time. Thus the whole algorithm runs in time O(n log n).
6. Assume that you have an unlimited number of $2, $1, 50c, 20c, 10c and 5c coins to pay for your lunch. Design an algorithm that, given the cost that is a multiple of 5c, makes that amount using a minimal number of coins.
Solution: Keep giving the coin with the largest denomination that is less than or equal to the amount remaining, until the desired amount is reached. To prove that this results in the smallest possible number of coins for any amount to be paid, assume the opposite – that is, suppose that for a certain amount M, there is an optimal way of payment which is more efficient than the one described by the greedy algorithm. Clearly, since the ordering in which the coins are given does not matter, we can assume that such payment proceeds from the largest to the smallest denomination. Consider the instance of the greedy policy being violated. This can happen, for example, if the remaining amount to be paid is at least $2, but a $2 dollar coin was not used. However, if this is the case, notice that at most one $1 coin could have been used, as otherwise the payment would not be efficient because two $1 coins can be replaced by a single $2 dollar coin. Thus, after the option of giving a $1 dollar coin has been exhausted we are left with at least $1 to be given without using any $1 dollar coins. For the same reason at most one 50 cent coin can be given and we are left with an amount of at least 50 cents to be given without using any 50 cent coins. Note that at most two 20 cent coins can be used because three 20 cent coins can be replaced with a 50 cent and a 10 cent coins. Also note that if two 20 cent coins are used, no 10 cent coins can be used because two 20 cent coins and a 10 cent coin can be replaced with a single 50 cent coin. Thus, if two 20 cent coins are used, only 5 cent coins can be used to give the remaining amount of at least 10 cents, which would require two 5 cent coins, but these could be replaced by a single 10 cent coin, contradicting optimality. If, on the other hand, only one 20 cent coin is used to give an amount of at least 50 cent we are left with at least 30 cents to be given using 10 cent and 5 cent coins. Note that in such a case only one 10 cent coin can be used because two 10 cent coins
can be replaced by a 20 cent coin. So we are left an amount of at least 20 cents to be given with 5 cent coins only. However only one 5 cent coin can be used because two 5 cent coins can be replaced by one ten cent coin contradicting the optimality of the solution. If the greedy strategy was violated for the first time when smaller amounts are due, the analysis is a subset of the analysis above. Thus, the greedy strategy provides an optimal solution. Note that in all countries the notes and coins denominations are chosen so that the greedy strategy is optimal.
7. Assume that the denominations of your n + 1 coins are 1,c,c2,c3,…,cn for some integer c > 1. Design a greedy algorithm which, given any amount, makes that amount using a minimal number of coins.
Solution: As in the previous problem, keep giving the coin with the largest denomination that is less than or equal to the amount remaining. To prove that this is optimal, we once again assume there is an amount for which there is a payment strategy that is more efficient than the greedy strategy, and assume that the coins are given in order of decreasing denomination. At some point during the payment, the greedy strategy will be violated, which means that the remaining amount is at least cj for some j but the strategy chooses not to give a coin of cj cents. So the next-largest denomination that can be used is cj−1. However, note that the strategy can give at most c − 1 coins of denomination cj−1, because c many coins of denomination cj−1 can be replaced with a single coin of denomination cj. Thus, after giving fewer than c many coins of denomination cj−1 we are left with at least the amount cj −(c−1)cj−1 = cj−1 to be given using only coins of denomination cj−2. Continuing in this manner, we eventually end up having to give at least c cents using only 1 cent coins which contradicts the optimality of the method.
8. Give an example of a set of denominations containing the single cent coin for which the greedy algorithm does not always produce an optimal solution.
Solution: Consider the denominations 4c, 3c and 1c and an amount to be paid of 6 cents. The greedy algorithm would first give one 4c coin and would then be forced to give 2 cents using two 1c coins. However, giving two 3c coins is more optimal.
9. Given two sequences of letters A and B, find if B is a subsequence of A in the sense that one can delete some letters from A and obtain the sequence B.
Solution: Use a simple greedy strategy. First, find and mark the earliest occurrence of the first letter of B in A. Then, for each subsequent letter of B,
find and mark the earliest occurrence of that letter in A which is after the last marked letter. If you reach the end of B before or at the same time as you reach the end of A, then B is a subsequence of A.
10. There is a line of 111 stalls, some of which lack a roof and need to be covered with boards. You can use up to 11 boards, each of which may cover any number of consecutive stalls. Cover all the necessary stalls, while covering as few total stalls as possible.
Solution: First, cover all roofless stalls with a single board that stretches from the first roofless stall to the last roofless stall. Then, repeat the following up to 10 times: Find the longest line of consecutive roofed stalls that are covered by a board, and then excise that part of the board, replacing it with two boards. Stop when there is no stall with a roof that is covered by a board.
11. Let X be a set of n intervals on the real line. A subset of intervals Y ⊆ X is called a tiling path if the intervals in Y cover the intervals in X, that is, any real value that is contained in some interval in X is also contained in some interval in Y . The size of a tiling cover is just the number of intervals. Describe and analyse an algorithm to compute the smallest tiling path of X as quickly as possible. Assume that your input consists of two arrays XL[1..n] and XR[1..n], representing the left and right endpoints of the intervals in X.
A set of intervals. The seven shaded intervals form a tiling path.
Solution: Sort the intervals in increasing order of their left endpoints. Start with the interval with the smallest left endpoint; if there are several intervals with the same such smallest left endpoint choose the one with the largest right endpoint. Then, consider all intervals whose left endpoints are in the last chosen interval, and pick the one with the largest right endpoint. Continue in this manner until an interval with the absolute largest right endpoint is chosen.
The algorithm involves sorting the intervals, and then performing by a single pass through all of the intervals. Hence, the algorithm runs in O(n log n) time.
12. Assume that you are given n white and n black dots lying in a random con- figuration on a straight line, equally spaced. Design a greedy algorithm which connects each black dot with a (different) white dot, so that the total length of wires used to form such connected pairs is minimal. The length of wire used to connect two dots is equal to the straight-line distance between them.
Solution: One should be careful about what kind of greedy strategy one uses. For example, connecting the closest pairs of equally coloured dots produces suboptimal solution as the following example shows:
Connecting the closest pairs (blue lines) uses 3 + 7 = 10 units of length while the connections in red use only 4 × 2 = 8 units of length.
The correct approach is to go from left to right and connect the leftmost dot with the leftmost dot of the opposite colour and then continue in this way. To prove that this is optimal, we assume that there is a different strategy which uses less wire for a particular configuration of dots. Such a strategy will disagree with our greedy strategy at least once, which means that at some point, it will not connect the leftmost available dot with the leftmost available dot of the opposite colour. We look at the leftmost dot for which the greedy strategy is violated. There are three types of configurations to consider (shown below) – but for each configuration, the strategy uses either the same amount or more wire than the greedy strategy. Hence, the hypothetical strategy is no better than the greedy strategy, contradicting our original assumption, and so the greedy strategy is optimal.
13. Assume you are given n sorted arrays Pi, 1 ≤ i ≤ n, of different sizes ei. You are allowed to merge any two arrays into a single new sorted array and proceed
in this manner until only one array is left. Design an algorithm that achieves this task and uses minimal total number of moves of elements of the arrays. Give an informal justification for why your algorithm is optimal.
Solution: Clearly, the elements of the arrays that are merged earlier will be moved more times than the elements of the arrays that are merged later. (Note that this problem is almost identical to the problem of Huffman encoding with the normalised numbers of elements ei/ nj=1 ej taken as frequencies.) Thus, we take the two shortest arrays and merge them, and continue with the resulting set of arrays in the same manner until there is only one array remaining.
In the figure above, the shortest arrays were P1 and P2 so they were merged first; then the shortest arrays were the merged array P1P2 and P3, then the pair P4 and P5, then P6 and P7, then P8 and P9, then P1P2P3 and P4P5, and
so on. The proof of optimality is the same as for the Huffman codes, see the textbook.
14. A photocopying service with a single large photocopying machine faces the following scheduling problem. Each morning they get a set of jobs from cus- tomers. They want to schedule the jobs on their single machine in an order that keeps their customers the happiest. Customer i’s job will take ti time to complete. Given a schedule (i.e., an ordering of the jobs), let Ci denote the fin- ishing time of job i. For example, if job i is the first to be done we would have Ci =ti,andifjobjisdonerightafterjobi,wewouldhaveCj =Ci+tj. Each customer i also has a given weight wi which represents his or her importance to the business. The happiness of customer i is expected to be dependent on the finishing time of their job. So the company decides that they want to order the jobs to minimise the weighted sum of the completion times, ni=0 wiCi. Design an efficient algorithm to solve this problem. That is, you are given a set of n jobs with a processing time ti and a weight wi for job i. You want to order the jobs so as to minimise the weighted sum of the completion times, ni=0 wiCi.
Solution: Schedule the jobs in decreasing order of wi/ti. This problem is very similar to the Tape Storage problem, which was covered in the lectures. To prove that this is optimal, we first introduce the concept of an inversion. We say that two jobs i and j form an inversion if job i is scheduled before job j, but wi/ti < wj/tj. Now consider any schedule which violates our greedy scheduling. Such a schedule will contain an inversion of at least one pair of consecutive jobs. If we repeatedly fix all such inversions between two consecutive jobs (by swapping them in the schedule) without increasing the value of S = ni=0 wiCi then, by the “bubble sort algorithm” argument, all inversions will eventually disappear and we will ha
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com