$3.$ Water Jug Problem $($Problem $8-4$: page $206$ of CLRS $3$rd edition$)$

Suppose that you are given n red and n blue water jugs, all of 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.

It is your task to find a grouping of the jugs into pairs of red and blue jugs that hold the same volume of water. To do so$,$ you may perform the following operation: pick a pair of jugs, one red, one blue, fill the red jug with water, and then pour the water into the blue jug. This operation will tell you if the two jugs hold the same amount of water, and if not, which one holds more water. Assume that such a comparison takes one unit of time. Your goal is to find an algorithm that solves this problem. Remember that you may not directly compare two red jugs or two blue jugs.$$a$.$ Find an algorithm that uses $\backslash$Theta $($n$2)$ comparisons $($in worst case$)$ to group the jugs into pairs.

b$.$ Prove a lower bound of $$log$3(!)$ for the worst case, and log$3(!)$ for the average case number

of comparisons to be performed by any algorithm that solves this problem.

c$.$ Find an algorithm for this problem that runs in $($average case$)$ time $\backslash$Theta $($ log $).($Hint: modify the algorithms Partition$()$ and Quicksort$().)$