Sample Problems: Greedy Algorithms Chapter 4

COMP 482 Sample Problems: Greedy Algorithms Problem 1. (10 points) For each of the following statements determine whether it is true of false. (+1 for a correct answer, -0.5 for an incorrect answer, 0 for a blank). If a problem can be optimally solved using a greedy algorithm then all greedy algorithms solve it optimally. IntervalScheduling has a polynomial time algorithm. There is no greedy algorithm for ChannelAllocation which always finds the optimal solution. There is more than one greedy algorithm to solve MinimumSpanningTree. The Cashier’s Algorithm finds the minimum number of coins necessary to make change for every instance of CoinChanging. The idea behind greedy algorithms is to make decisions without considering sophisticated future consequences. One of the advantaages of greedy algorithms is that they always find two optimal solutions. Everything is awesome! Everything is cool when you’re part of a team! F T F T F T F F? Problem 2. (10 points) Using the optimal greedy algorithm described in class, solve the following instance of IntervalScheduling. Show enough work to convince me that you are using the algorithm and that your answer isn’t just a guess or arrived at via brute force. {(4, 6), (15, 19), (22, 24), (12, 17), (1, 5), (19, 23), (6, 10), (13, 16), (7, 9), (27, 30), (25, 29), (2, 10)} Problem 3. (10 points) Imagine that there is a new computer game called DownRightMonsterous. The playing area is shaped like an NxN checkerboard and some of the squares contain monsters (that you need to kill). You begin in the top left corner and take steps either down or to the right until you reach the bottom right corner. If you step onto a square with a monster, you kill the monster. If you reach the bottom right square and all monsters have been killed then you win. If you reach the bottom right square and there are monsters still alive you are moved back to the top left corner and need to kill the remaining monsters. Your goal is to kill all of the monsters in the minimum number of transits of the board. For example, this 5x5 board will require 2 transits of the board. M M But this 5x5 board only requires 1 transit of the board. M M M M M M Describe a greedy algorithm to minimize the number of transits necessary to kill all the monsters. Prove that your algorithm is optimal. Problem 4. (10 points) Using the optimal greedy algorithm taught in class, solve the following problem instance of ChannelAllocation: I = {(1, 2), (1, 4), (2, 5), (3, 11), (5, 9), (6, 8), (10, 14), (12, 19), (14, 22), (15, 20), (16, 18), (17, 18), (19, 21)}. Problem 5. (10 points) Assume that you have a set of jobs where each has a processing time and a deadline (pi , di ). Explain how you could schedule the jobs on a single machine to minimize the maximum lateness. Execute your procedure on the instance {(1, 11), (2, 8), (3, 6), (5, 9), (6, 4), (8, 12)}. Problem 6. (10 points) Assume that you have a set of jobs where each has only a processing time that you need to schedule on a single machine. Explain how you should schedule the jobs to minimize the sum of completion (finish) times. Prove that your schedule is optimal. Problem 7. (10 points) Solve the following instance of HuffmanCode. letter prob u v w x y z .22 .15 .08 .2 .1 .25 Problem 8. (10 points) Assume that a student was attempted to construct a HuffmanCode for a given set of letter frequencies. You have noticed that the letter X is encoded with fewer symbols than the letter Y , but that the letter X has a lower probability of occurance. Prove that the student has not minimized the expected number of characters needed to encode a message. Problem 9. (10 points) Imagine that you have a pile of sand and that many people want some of your sand (di↵erent people usually want di↵erent amounts). You want to distribute your sand to these people, but may not have enough sand to meet everyone’s desire. Describe a greedy algorithm to decide how much sand to give to each person which maximizes the number of people who have their desire met and show that your algorithm is correct. Problem 10. (10 points) Assume that there are 2k+1 people living along a road at locations: L0 < L1 < L2 , < · · · < L2k . These people want to meet at one of the homes and minimize the total travel distance. For example, if L = 1 2 3 5 100 then the best location to meet would be 3 with total travel distance 2+1+0+2+97 = 102. Give an O(1) time algorithm to find the best location and prove your algorithm is correct (probably using an exchange argument). Problem 11. (10 points) A student made the following argument. For ChannelAllocation we want to minimize the number of channels. This means we need to put as many intervals in each set as possible. So we can repeatedly run the optimal algorithm for IntervalScheduling (Earliest Finish Time) to decide what to put on channel 1, 2, . . . and get the optimal solution for ChannelAllocation. If you believe the student is correct then fill in the gaps in the proof. If you think the student is incorrect then find a counter example. ............ Interval Scheduling (1 5) (4 , , > - Finish Earliest time 6) (7 , 9) (2 10) (6 10) (13, 16) (12, 17) (15, 19) (19 , 23) (22, 24 , (1 , 5) (7 9) , , Channel Allocation 1 : 3 : n S : : - EST is (1 , 2) (2 , 5) (5 9) (10 14) (14 , 22) : 2 , (13, 16) (19 , 23) (25, 29) ........... Channel (25 29)(27 30) , , (1 4) (6 , , 8) (12, 19) (19 21) , (3, 11) (15 , 20) (16 , 18) (17 18) , 16, 4) (3 6) (2 , 8) (5, 9) (1 , 11) , (8 , 12) Earliest deadling first · in is in ↳ 2 E is is E 13 , ferliest finish time JobsProcessing = 53 13 , ii =3- Since with go we have - 1 + the d maximize to the number , + order ascending 112/3/5/100 3 T + 23-23-33-53-100 10297 , = 102 least so 2K+ yz all the of people demand we choose middle routes. , we will needed. the distance for