1. Design an algorithm using pseudocode running O(n log n) time to solve an aver
ID: 3596466 • Letter: 1
Question
1. Design an algorithm using pseudocode running O(n log n) time to solve an average case..
2. Design a randomized algorithm using pseudocode running O(n log n) time to solve the grouping water-jug problem.
Please be as specific as possible, no mathematical notation. I've been toying around with quickSort, but I can quite pin it down.
No paragraph type answers, or the answer found in the textbook which uses mathematical notation. Just pure pseudode ready to be implemented.
Will give points for correct and detailed answer.
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: 1. pick a pair of jugs in which one is red and one is blue 2. fill the red jug with water, and 3. 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.Explanation / Answer
Part 1)
Let all red jugs be represented by an array, r[1...n] and all blue jugs be represented by an array b[1...n].
We can use partition algorithm (one used in quicksort) for this purpose. Algorithm GROUPJUGS solves our problem using the parition algorithm.
Paritition(a[],pivot)
{
n = size(a)
for j = 1 to n; do
{
if (A[j] <= pivot) {
i = i + 1
Exchange A[i] with A[j].
}
}
Exchange A[i+1] with A[r].
return i+1.
}
GROUPJUGS(r[], b[])
{
pivot=b[1];
Partition(r[],pivot).
// Partition takes O(n).
//r[] gets divided into r_small[] and r_large[] and element r_equal (equal to b[i])
pivot = r_equal
Partition (b[],pivot)
//Partition takes another O(n)
//b[] gets divided into b_small[] and b_large[] and element b[i]
//Now you have r_small[], r_large[], b_small[], b_large[] with a total of 2(n-1) elements
GROUPJUGS(r_small[], b_small[])
GROUPJUGS(r_large[], b_large[])
}
Part 2)
For using randomized algorithm we can randomly take the pivot taken in GROUPJUGS.
RANDOM_GROUPJUGS(r[], b[])
{
pivot=Random(1,n);
Partition(r[],pivot).
// Partition takes O(n).
//r[] gets divided into r_small[] and r_large[] and element r_equal (equal to b[i])
pivot = r_equal
Partition (b[],pivot)
//Partition takes another O(n)
//b[] gets divided into b_small[] and b_large[] and element b[i]
//Now you have r_small[], r_large[], b_small[], b_large[] with a total of 2(n-1) elements
RANDOM_GROUPJUGS(r_small[], b_small[])
RANDOM_GROUPJUGS(r_large[], b_large[])
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.