Finding similar pizzas You are given a stack of n pizza boxe

(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.

Hint: What happens if they all dier by more than that?
Give an algorithm for nding 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• Briey describe how your algorithm works in English.
1

• Give pseudocode for your algorithm.

• Prove that your algorithm is correct.

• Analyze the worst-case complexity of your algorithm as measured by the number of
opened boxes.

Solution

For 1a you could use induction:

Basically: Assume n=2 (at least two pizzas, otherwise no difference) and maximize difference. Let one of the pizzas have a diameter of 40 and the other one x Then we have 40-x < 40/(2-1) which is true.

Induction step n=>n+1 and you can try from there...