Problem 1. Greedy Algorithms (26 Points) You are a thief planning to steal a collection of valuable jewels on display at the museum There are n different jewels in total, each has a different size and black market value. The sizes are given in an array S[1 n] and the values are given in an array V[1 n]. Let [n] = {1, . . . ,n) denote the set of jewels. Unfortunately you cannot steal all the jewels, and instead can only take what wil fit in your robber's bag which has size b (and a big dollar sign on the front of course). Specifically, the sum of the sizes of the items you choose should be less than or equal to b. Naturally, you wish to steal a subset J C [n] of jewels which maximizes the total sum of values subject to fitting in your bag. You can assume b as well all values in S and V are positive. At first you are worried as you recall this is the well known NP-hard Knapsack problem (or rather you will recall, once we cover NP-hardness). Then you remember you have a handy dandy jewel cutter, which cuts jewels to any desired fraction. Specifically, for any e2 1, if you take a 1/c fraction of the ith Jewel then the size is S[i/c and the value is VA/c. (a) (5 points) Give a short description of the greedy algorithm for the jewel thief problem when you are allowed to take any fractional amount of each jewel (or the whole jewel) (b) (9 points) Prove that your greedy algorithm is correct Recall the class scheduling problem, where one is given starting and ending times of all the available classes on a given day, and the goal is to select the largest number of classes whose scheduled times do not overlap. In class we proved that the greedy algorithm which selects the class ending first, removes classes conflicting with this selection, and then repeats, is optimal. Instead consider the greedy strategy which selects the class which conflicts with the fewest other classes, removes classes conflicting with this selection, and then repeats. (c) (6 points) Prove this greedy strategy is NOT optimal, by giving the starting and ending times of a set of classes where this strategy fails to produce an optimal class schedule. Make sure to state clearly for your set of classes what the optimal solution is and what classes the greedy algorithm selects. You are give a text file containing only the characters fa, b, c, d, e, f). Let F(x) denote the frequency of a character x. Suppose that: F(a)-13, F(b)-4, F(c)6, F(d)17, F(e) 2, and F(f)-11 (d) (6 points) Give a Huffman code for the above set of frequencies, i.e. specify the binary encoding for each of the six characters. Problem 1. Greedy Algorithms (26 Points) You are a thief planning to steal a collection of valuable jewels on display at the museum There are n different jewels in total, each has a different size and black market value. The sizes are given in an array S[1 n] and the values are given in an array V[1 n]. Let [n] = {1, . . . ,n) denote the set of jewels. Unfortunately you cannot steal all the jewels, and instead can only take what wil fit in your robber's bag which has size b (and a big dollar sign on the front of course). Specifically, the sum of the sizes of the items you choose should be less than or equal to b. Naturally, you wish to steal a subset J C [n] of jewels which maximizes the total sum of values subject to fitting in your bag. You can assume b as well all values in S and V are positive. At first you are worried as you recall this is the well known NP-hard Knapsack problem (or rather you will recall, once we cover NP-hardness). Then you remember you have a handy dandy jewel cutter, which cuts jewels to any desired fraction. Specifically, for any e2 1, if you take a 1/c fraction of the ith Jewel then the size is S[i/c and the value is VA/c. (a) (5 points) Give a short description of the greedy algorithm for the jewel thief problem when you are allowed to take any fractional amount of each jewel (or the whole jewel) (b) (9 points) Prove that your greedy algorithm is correct Recall the class scheduling problem, where one is given starting and ending times of all the available classes on a given day, and the goal is to select the largest number of classes whose scheduled times do not overlap. In class we proved that the greedy algorithm which selects the class ending first, removes classes conflicting with this selection, and then repeats, is optimal. Instead consider the greedy strategy which selects the class which conflicts with the fewest other classes, removes classes conflicting with this selection, and then repeats. (c) (6 points) Prove this greedy strategy is NOT optimal, by giving the starting and ending times of a set of classes where this strategy fails to produce an optimal class schedule. Make sure to state clearly for your set of classes what the optimal solution is and what classes the greedy algorithm selects. You are give a text file containing only the characters fa, b, c, d, e, f). Let F(x) denote the frequency of a character x. Suppose that: F(a)-13, F(b)-4, F(c)6, F(d)17, F(e) 2, and F(f)-11 (d) (6 points) Give a Huffman code for the above set of frequencies, i.e. specify the binary encoding for each of the six characters
