Please provide clear and easy to follow explanation. For good feedback thanks Pr

Question

Please provide clear and easy to follow explanation. For good feedback thanks

Problems to be handed in 1. (Finding similar pizzas) You are given a stack of n pizza boxes of the same size, each containing 1 pizza. The pizzas in the boxes are sorted by increasing diameter; the diameters are all at most 40cm. Warm-up exercise (do not hand in): Prove that there must exist two pizzas in the stack whose diameters differ by at most 40 cm. Hint: What happens if they all differ by more than that? Give an algorithm for finding such a pair. The only way your algorithm may learn the diameter of a pizza is by opening its box and measuring it. We'll call that operation measure (i), where i is the number of the box being opened. Your algorithm should open as few pizza boxes as possible. For full credit, it should open O(log n) boxes in the worst case. Hint: Remember that the boxes are sorted by pizza size. Think binary search. If you look at the middle pizza box, what can you conclude? You might need to handle odd and even boxes separately. In your solution, as with all algorithmic problem this semester, you must

Explanation / Answer

Answer

Proving can be done thorugh induction:

Base step: take n=2 (as there should be at least two pizzas, or else there will be no difference) and maximize difference. Let say that one of the pizzas have a diameter of 40 and let the other one have a diameter of x Then we have

40-x < 40/(2-1)

which is true.

Induction step: when n=n+1, and let say the diameter of n+1 pizza is y then we get

40-y < 40/n

which is true.

So, there are two pizzas in the stack whose diameter differ by at most 40/(n-1).

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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