Pseudo code is fine but can it be explain thank you. Suppose that you are given

Question

Pseudo code is fine but can it be explain thank you. Suppose that you are given n red and n blue water jugs, all different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. Moreover, for every red jug, there is a blue jug that holds the same amount of water, and vice versa. Your task is to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water. To do so, you may perform the following operation: pick a pair of jugs in which one is red and one is blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or that they have the same volume. Assume that such a comparison takes one-time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping. Please remember that you may not directly compare two red jugs or two blue jugs. Design an algorithm running O (n^2) time to solve this problem. Design an algorithm running O (n log n) time to solve an average case. Design a randomized algorithm running O (n log n) time to solve the grouping water-jug problem.

Explanation / Answer

1.

Pick a red jug and compare it against all blue jugs until the matching jug is found, and then pair these two jugs.
Repeat this for all red jugs.
There are n red jugs and each needs at most n comparisons to find the matching blue jug.
Thus, the algorithm uses O(n^2) comparisons.

2.

We can use Quick sort algorithm ro solve this problem in O(nlogn)
First we choose a red jug and compare all the blue jugs with it. After comparisions we will have 3 sets of blue jugs, one with same size of red one, second set which is smaller than red one and third set which is larger than red one.
Now, repeat this with same size blue jug dividing the red jugs in 3 sets.
After this we have to repeat above with a red and blue jugs in smaller set and same with larger set.
So the time after each comparions will reduce to half if we choose approximately mid size jug in the range of jugs present.

3.

Algorithm in point 2 can be ramdomized if we choose a random jug from blue jugs as well for comparision instead of choosing same size as that of red one.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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