Problem 2. (10 points) Using the optimal greedy algorithm described in elm, solve the following instance of INTERVALSCHEDULING. Show enough work to convince me that you are using the algorithm and that your new lan'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 DownRIGHT MONTEROUS. 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 stepe either down or to the right until you reach the bottom right corner. I 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 monsten. 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 MMM 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 CHANNEL ALLOCATION: 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 S. (10 points) Assume that you have a set of jobs where each has a processing time and a deadline Prid). 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 2. (10 points) Using the optimal greedy algorithm described in elm, solve the following instance of INTERVALSCHEDULING. Show enough work to convince me that you are using the algorithm and that your new lan'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 DownRIGHT MONTEROUS. 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 stepe either down or to the right until you reach the bottom right corner. I 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 monsten. 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 MMM 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 CHANNEL ALLOCATION: 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 S. (10 points) Assume that you have a set of jobs where each has a processing time and a deadline Prid). 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