7. (13 points) Greedy Algorithms The Museum of Glass is hiring guards for its new exhibit. The exhibit will show pieces of art at various locations along a long hallway. The position of each piece of art is stated as the number of feet it is from the beginning of the hallway. For example one exhibit had pieces of art placed 4 feet, 6 feet, 12 feet and 17 feet from the beginning of the hallway. Museum rules state that there must be a guard at most 5 feet away from every piece of art. The museum also wants to hire the fewest number of guards. They ask you and your friends Alice and Bob to develop an algorithm to determine the minimum number of guards needed given the positions of the pieces of art. a) (1 point) For the example input state the minimum number of guards needed and what positions you would place them (a guard's position is the number of feet the guard is from the beginning of the hallway) P 14,6,12,17] b) (2 points) Bob claims to have solved the problem. He claims that if you place each guard so that they will cover the most pieces of art this will minimize the number of guards. Give an example of an exhibit in which Bob's algorithm fails. That is, show positions of pieces of art for which Bob's algorithm will not find the minimunm number of guards. c) (2 points) Alice agrees that Bob's algorithm is incorrect. She suggests that there has to be some guard guarding the first item and suggests placing the guard at the same location. You disagree. Where is the best place to place a guard that guards the first item, but also as many other items as possible? 7. (13 points) Greedy Algorithms The Museum of Glass is hiring guards for its new exhibit. The exhibit will show pieces of art at various locations along a long hallway. The position of each piece of art is stated as the number of feet it is from the beginning of the hallway. For example one exhibit had pieces of art placed 4 feet, 6 feet, 12 feet and 17 feet from the beginning of the hallway. Museum rules state that there must be a guard at most 5 feet away from every piece of art. The museum also wants to hire the fewest number of guards. They ask you and your friends Alice and Bob to develop an algorithm to determine the minimum number of guards needed given the positions of the pieces of art. a) (1 point) For the example input state the minimum number of guards needed and what positions you would place them (a guard's position is the number of feet the guard is from the beginning of the hallway) P 14,6,12,17] b) (2 points) Bob claims to have solved the problem. He claims that if you place each guard so that they will cover the most pieces of art this will minimize the number of guards. Give an example of an exhibit in which Bob's algorithm fails. That is, show positions of pieces of art for which Bob's algorithm will not find the minimunm number of guards. c) (2 points) Alice agrees that Bob's algorithm is incorrect. She suggests that there has to be some guard guarding the first item and suggests placing the guard at the same location. You disagree. Where is the best place to place a guard that guards the first item, but also as many other items as possible