Papa Mario of Mario's Pizzeria has baked a huge pizza and cut it into n slices, but he is clumsy and the pizza wasn't evenly sliced. Then slices have size S1, S2, ... Sn. There are n hungry students who each want to eat a slice of pizza. Suppose the ith student would be happy with any slice whose size is at least t,. Give an efficient algorithm to determine whether it is possible to distribute the pizza slices so everyone is happy

(a) What algorithm paradigm is most appropriate for this problem?

A. Divide-and conquer

B. Greedy algorithm

C. Dynamic Programming

D. Linear Programming

E. Graph Algorithm

F. None of these

b) Verbally describe an efficient algorithm to solve this problem

(c) What is the asymptotic running time of your algorithm?

Suppose there are n student: 1, 2, 3, ..., i, ..., n.

Now, let's say each want slice size to be: t1, t2, ..., ti, ..., tn.

Let's pizza slices be : s1, s2, ..., si, ..., sn.

Now, it can be said that a student ' i ' will accept a slice of pizza ' si ' only if the size of slice is more then ' ti '.

Logic to distribute: what can be done is we can sort the demand i. e ti of students and also sort the size of pizza slices si. Now, Papa Mario can distribute the sorted slices to students sorted demand (smallest to heighest) one by one as they appear in sorted lists. Now, it will only be possible to distribute the slices to make everyone happy, if and only if in sorted lists of both s and t for each index k, it holds the condition: tk < = sk.

Let me explain you with example:

Lets says size of whole pizza is 100.

Now number of students n = 4.

Let there demands be : 20, 35, 15, 10.

This means 1st student atleast require the slice size of 20 and so on.

Case 1: Papa Mario divides the pizza into slices of size: 25, 20, 20, 35.

=> Now, we sort both lists.

Thus t = > 10, 15, 20, 35

and s = > 20, 20, 25, 35

Now, as we can see that for all index tk < = sk, hence pizza can be distrubeted so that everyone can be happy.

Case 2: Papa Mario divides the pizza into slices of size: 30, 20, 20, 30.

=> Now, we sort both lists.

Thus t = > 10, 15, 20, 35

and s = > 20, 20, 30, 30

Now, as we can see that, for last student with demand of 35, the pizza slice alotted is of size 30, thus he is unhappy, and pizza cannot be distributed so that everyone becomes happy.

Now, after the approach, let's discuss question.

(a) Greedy algorithm paradigm is most appropriate for this problem, as what we are doing is greedily distributing small slices to those students which have least demands first then tackling bigger demands of students, by remaining bigger slices.

(b) As we are mainly sorting thel ist of sizes of pizza slices and student demands, thus we need to use an efficient algorithm to sort the lists. Such an efficient algorithm can be QuickSort () or MergeSort ().

(c) Asymptotic running time of our algorithm would be O (n*logn).