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. Remember that you may not directly compare two red jugs or two blue jugs.
a. Describe a deterministic algorithm that uses $\theta(n^2)$ comparisons to group the jugs into pairs.
b. Prove a lower bound of $ \Omega(n lg n)$ for the number of comparisons that an algorithm solving this problem must make.
c. Give a randomized algorithm whose expected number of comparisons is $O(n lg n)$, and prove that this bound is correct. What is the worst-case number of comparisons for your algorithm?
a. If we compare each red jug with each blue jug since there are n red jugs and n blue jugs we get $\theta(n^2)$.
b. The algorithms has to make a series of comparisons to group the jugs in to groups. We can view the comparisons as a decision tree. Every internal node will have a Red jug and a blue jug and three children less than red jug, greater than red jug and equal to red jug. The height of the decision tree is the worst case of comparisons the algorithm has to make to determine matching.To bound the height lets compute the total number possible matchings of n red and n blue jugs.
If we label n red jugs from 1..n and n blue jugs from 1..n then
${i,\pi(i)}$ for i = 1..n $\pi$ is a permutation on {1..n}
since every permutation of $\pi$ corresponds to a different outcome we have n! outcomes.(if we draw a decision tree it will have to for groupings of jugs). Now since every node has a branching factor of 3.let h be the height of the tree, The tree should have at most $3^h$ leaves. $$ n! \leq 3^h$$ $$ log_3 n! \leq h$$ $$ n log n \leq h$$(Stirling app.) $$h = \Omega(n log n)$$ c. Assuming R jugs are labeled from 1..n and red jugs from 1..n. The output of the algorithm will contain distinct pairs of (i,j) where i corresponds to red and j corresponds blue jug with equal quantity. The procedure Matchjugs needs one condition to be satisfied $|R|=|B|$ Match-Jugs(R,B)
If |R| = 0
then return
If |R| = 1
then return R(1),B(1)
else
$$r \leftarrow a randomly chosen jug in R$$ compare r to every jug of B
$$B_< \leftarrow all elements of B jug less than r$$ $$B_> \leftarrow all elements of B jug greater than r$$ $$b the one jug in b with same size as r$$ $$R_< \leftarrow all elements of B jug less than b$$ $$R_> \leftarrow all elements of B jug greater than b$$ output("r","b")
Match-Jugs($R_<,B_<$)
Match-Jugs($R_>,B_>$)
What about the running time? The analysis of the expected number of comparisons is similar to that of the quicksort algorithm in Section 7.4.2. Let us order the jugs as r1, . . . , rn and b1, . . . , bn where ri < ri+1 and bi < bi+1 for i = 1, . . . , n, and ri = bi . Our analysis uses indicator random variables Xi j = I {red jug $r_i$ is compared to blue jug $b_j$ } .
As in quicksort, a given pair ri and bj is compared at most once. When we compare $r_i$ to every jug in B, jug $r_i$ will not be put in either R< or R>. When we compare bi to every jug in R −{$r_i$ }, jug bi is not put into either B< or B>. The total number of comparisons is $$X = \sum_{i=1}^n−1 \sum_{j=i+1}^n Xij $$.
To calculate the expected value of X, we follow the quicksort analysis to arrive at $$E [X] = \sum_{i=1}^n−1 \sum_{j=i+1}^n Pr {r_i is compared to b_j } .$$ As in the quicksort analysis, once we choose a jug $r_k$ such that $r_i < r_k < b_j$, we will put $r_i$ in $R_<$ and $b_j$ in $B_>$, and so $r_i$ and $b_j$ will never be compared again. Let us denote $R_ij = {r_i , . . . , r_j }$. Then jugs $r_i$ and $b_j$ will be compared if and only if the Þrst jug in Ri j to be chosen is either ri or r j . Still following the quicksort analysis, until a jug from $R_ij$ is chosen, the entire set Ri j is together. Any jug in $R_ij$ is equally likely to be Þrst one chosen. Since $|R_ij |$ = j − i + 1, the probability of any given jug being the Þrst one chosen in $R_ij$ is 1/( j−i+1). The remainder of the analysis is the same as the quicksort analysis, and we arrive at the solution of $O(n lg n)$ comparisons.
Just like in quicksort, in the worst case we always choose the largest (or smallest) jug to partition the sets, which reduces the set sizes by only 1. The running time then obeys the recurrence T (n) = T (n − 1) + (n), and the number of comparisons we make in the worst case is $T (n) = \theta(n2).$
No comments:
Post a Comment