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. 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 Θ(n 2 ) comparisons to group the jugs into pairs. (b) Give a randomized algorithm whose expected number of comparisons is O(n log n), and discuss why your is bound is correct. What is the worst-case num- ber of comparisons for your algorithm?
Permutations and Combinations
If there are 5 dishes, they can be relished in any order at a time. In permutation, it should be in a particular order. In combination, the order does not matter. Take 3 letters a, b, and c. The possible ways of pairing any two letters are ab, bc, ac, ba, cb and ca. It is in a particular order. So, this can be called the permutation of a, b, and c. But if the order does not matter then ab is the same as ba. Similarly, bc is the same as cb and ac is the same as ca. Here the list has ab, bc, and ac alone. This can be called the combination of a, b, and c.
Counting Theory
The fundamental counting principle is a rule that is used to count the total number of possible outcomes in a given situation.
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.
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 Θ(n
2
) comparisons to group the jugs into
pairs.
(b) Give a randomized algorithm whose expected number of comparisons is O(n log n), and
discuss why your is bound is correct. What is the worst-case num- ber of comparisons
for your algorithm?
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
