Problem Set - Greedy Algorithms 1. The 0-1 Knapsack problem can be phrased as follows: Input: A collection of n items where item i has value vi and weight wi. As well, there is a weight limit W. Output: A subset of the n items with largest total values such that the sum of the weights remains under W. Give an example of this problem for which the greedy algorithm we saw in class does not give the optimal solution. 2. Many universities use algorithms to assign classes to requested course timeslots. The goal is to use the fewest number of rooms to house the maximal number of classes. More formally, the problem may be stated as: INPUT: A set S={(si,fi)1in} of classes. Each class is represented by its start time and finish time stored as 24-hour times. Think of the values (si,fi) as being a request for a room for a class that meets from start time sj to finish time fi, OUTPUT: Find an assignment of classes to rooms that uses the fewest number of rooms. You may assume that there are enough rooms for each class to have their own room (but that wouldn't be optimal!). Write a greedy algorithm to solve this problem. Your solution doesn't have to be optimal, but it should give an indication of making the "best" choice at each round of the algorithm. Sample Input: {(11,13),(12,2),(10,11)} Sample Output: 1, 2,1 Explanation: The above input represents three classes that meet from 11-13 o'clock, 12-2 o'clock, and 10-11 o'clock. The output suggests placing these classes in room 1 , room 2 , and room 1 , respectively