1. After 15 years working as a software engineer, Alice finally has enough money
ID: 3880792 • Letter: 1
Question
1. After 15 years working as a software engineer, Alice finally has enough money and time to fulfill her dream to open a pizza shop in Santa Cruz. She has the recipes for n different flavors of pizza. She needs to put some of them on the menu. She wants to make pizza which is both popular and cheap to make. She did some research on how popular is for every flavor of pizza in Santa Cruz, and how much would it cost for making each of them. Let's say for flavor i, the popularity is denoted by pi and the cost is denoted by ci. Alice only wants to put i on the menu if for any other flavor j, i is either more popular than j or cheaper than j. In other words, suppose ci 2 cj and pi S P, we say the flavor i is dominated by j. Alice wants to filter out the flavors which are dominated by other Given an input of the information for n flavors of pizza: (pi, c), (P2, c2), , (Pn, cn)j, provide a Divide and Conquer algorithm helping Alice to find the undominated flavors in O(n log n) time.Explanation / Answer
The problem can be solved using a Merge sort with a few modifications. The modifications involve adding a “dominated” field for every input tuple. This field denotes a Boolean value whether or not a tuple value has been dominate by other tuple or not.
The algorithm goes as follows:-
Solution(low,high)
Combine(low,mid,high)
Consider the example below:
1.
(38,27)
(43,3)
(9,82)
(18,83)
(18,28)
(88,20)
(50,40)
(22,96)
2. Split the above array into 2 parts from a[0:3] and a[4:7]
38,27
43,3
9,82
18,83
18,28
88,20
50,40
22,96
3. Split further from a[0:1] , a[2:3] , a[4:5] and a[6:7]
38,27
43,3
9,82
18,83
18,28
88,20
50,40
22,96
4. Split further which will lead to individual tuples
38,27
43,3
9,82
18,83
18,28
88,20
50,40
22,96
5. Now start combining the above tuples as we check for which is dominated and which is not.
If we see (38,27) and (43,3) , Pj>Pi and Cj<Ci so (43,3) dominates (38,27) . Hence combined into single set with (43,3) as first element and * marked indicating dominated(T) = false. i.e it has remained undominated till now. Same applies to other combinations as well. For (9,82) and (18,83) , Pj>Pi but Cj>Ci hence no tuple dominates the other. So both are undominated.
43,3 *
38,27
9,82 *
18,83 *
88,20 *
18,28
50,40 *
22,96
6. Combining (43,3)*,(38,27) , (9,82)* and (18,83)* results in only (43,3) as the undominated tuple.
The other tuples get dominated by (43,3) and hence are no longer * marked. (43,3)* becomes first element in the combined set.
43,3 *
38,27
9,82
18,83
88,20 *
18,28
50,40
22,96
7. Repeating the above combination steps again results in (43,3) and (88,20) being the undominated values.
(43,3) *
(88,20) *
(38,27)
(9,82)
(18,83)
(18,28)
(50,40)
(22,96)
(38,27)
(43,3)
(9,82)
(18,83)
(18,28)
(88,20)
(50,40)
(22,96)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.