7. (13 points) Greedy Algorithms The Museum of Glass is hiring guards for its ne

Question

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?

Explanation / Answer

Solution:

a)

The art pieces are at 4, 6, 12, 17

Minimum number of guards required = 2

Explanation:

For finding the minimum number of guards needed we must place our guards in such a way that they cover all the pieces of arts we must place them in such a way that they cover the maximum number of arts. this is a greedy approach.

So, one guard will be standing at 8 feet, and another at 15 feet.

b)

suppose the pieces of art are placed at 1, 6, 11 feet then Bob's algorithm will ask to put two guards from which one can be placed between 1 to 5 and another one can be between 11.

But if we place the guard at 6 then only one guard is required.

c)

Alice inference is completely wrong, the best way to place the guard to guard the first art is at 6 feet.

In this case, the guard is covering 10 feet in total.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.