Please show full and clear explanation and show all parts for good feedback than

Question

Please show full and clear explanation and show all parts for good feedback thanks Algorithm problem en the question says, "Give an algorithm for finding such a pair." It means finding two pizzas in the stack whose diameters differ by at most (40/n-1 cm. 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. 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(logn) 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 Briefly describe how your algorithm works in English. 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.

Explanation / Answer

In my opinion you could use induction here with the process of induction

Firslty,Considered for p=2 (in other words there is basically two pizza must in order to calculate difference ) and maximize difference. Considered one out of the two pizzas have a diameter of 40 and the second have q Then we have 40-q < 40/(2-1) which is to be true.

Now similarly you have to process towards next step of induction nduction step n=>n+1 you can prove this with similar approach as above

As far as algorithm are considered in my opinion you can use binary search for complete algorithm please provide algorithm question seprately

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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