Problem 1: A day at a crowded beach. You are back at the beach, but now it is too crowded. You have only k umbrellas. You run your optimal greedy algorithm from the previous homework, and you realize that the minimum number of umbrellas needed to cover everyone is larger than k. You decide to try to cover as many people as possible with the k umbrellas you have available. Formal description: You are given X1, ... , Xn E Z, and some k, L E N. You want to find a collection of intervals I1, ..., Ik CR, each of length L, such that the number of points in X1, ..., In that fall inside 11 U... U Ik is maximized. Describe a polynomial-time algorithm for this problem. That is, the running time of your algorithm should be at most polynomial in n. Prove that your algorithm is correct and that it runs in polynomial time. For example, if the input is xi = 1, X2 = 3, x3 = 4, x4 = 6, X5 = 9, x6 = 10, x7 = 11, 28 = 12, X9 = 15, X10 = 17, k = 3, and L = 3, then an optimum solution is [1,4], [9, 12), [14, 17]. HHHHHHHHHHHHHH 1 ? 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Hint: Use dynamic programming. Problem 1: A day at a crowded beach. You are back at the beach, but now it is too crowded. You have only k umbrellas. You run your optimal greedy algorithm from the previous homework, and you realize that the minimum number of umbrellas needed to cover everyone is larger than k. You decide to try to cover as many people as possible with the k umbrellas you have available. Formal description: You are given X1, ... , Xn E Z, and some k, L E N. You want to find a collection of intervals I1, ..., Ik CR, each of length L, such that the number of points in X1, ..., In that fall inside 11 U... U Ik is maximized. Describe a polynomial-time algorithm for this problem. That is, the running time of your algorithm should be at most polynomial in n. Prove that your algorithm is correct and that it runs in polynomial time. For example, if the input is xi = 1, X2 = 3, x3 = 4, x4 = 6, X5 = 9, x6 = 10, x7 = 11, 28 = 12, X9 = 15, X10 = 17, k = 3, and L = 3, then an optimum solution is [1,4], [9, 12), [14, 17]. HHHHHHHHHHHHHH 1 ? 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Hint: Use dynamic programming