Question

In: Computer Science

Suppose there are n (>=3) gold bullions, where one of them is fake. However, we do...

Suppose there are n (>=3) gold bullions, where one of them is fake. However, we do not know whether the fake one is heavier or lighter than the genuine ones. All the genuine ones weigh the same. In this problem, you are asked to use a balance scale to find the fake one in o(n) steps (little-o). NO pseudo-code is needed, only describe your answers to the following questions: (25pts)(1) What are your bases cases? How do you solve your base case(s)?(2) For non-base cases, how do you divide and weigh to reduce the given problem into subproblem(s)?(3) Derive your recurrence relation and justify that the number of steps of using the scale is o(n).

Solutions

Expert Solution

Base Case :

If n = 3 , We have 3 gold bullions and we need to check the weight of any 2 bullions.

Suppose Bullions are A,B,C , If A is equal to B , fake bullion is C otherwise genuine bullion is C and we have to make another comparison.

Non Base Case :

The first part is to solve the puzzle in k weighings given 3^k , (3^k+1)/2 of which could only contain a heavier gold bullions and (3^k-1)/2 of which could only contain a lighter gold bullions (or vice versa):

  • For 3^0=1 gold bullions (split 0 and 1), we require no weighings.
  • For 3^(k+1) (split 3^(k+1)+1/2 and 3^(k+1)-1/2), we weigh (3^k+1)/2 from group A and (3^k-1)/2 from group B against another (3^k+1)/2 from group A and (3^k-1)/2 from group B (leaving unweighed (3^k-1)/2 from group A and (3^k+1)/2 from group B). If the weighed are equal, we recursively solve the problem for the unweighed group. Otherwise, we've whittled down the suspects to the group A on one side and the group B on the other, so we instead recursively solve the puzzle for those.

Second Part

  • For (3^(k+1)+1)/2 and an additional 'normal' gold bullions, we weigh (3^k+1)/2 against (3^k-1)/2 plus the 'normal' one, leaving (3^k+1)/2 unweighed. If the weighed are equal, we recursively solve the problem for the unweighed group. Otherwise, we use the solution from the first part for the (3^k) weighed .
  • For (3^(k+1)-1)/2 with no additional 'normal' gold bullions, we weigh (3^k-1)/2 against another (3^k-1)/2 . If the weighed are equal we use the solution above on the remaining (3^k+1)/2 ; otherwise we add an unweighed gold bullions (now known to be 'normal') to the 3^k-1 weighed and again use the solution from the first part .

Related Solutions

What is wheezing where do we hear them?
What is wheezing where do we hear them?
Suppose we live in a monocentric city where streetcars have replaced horse carts. However, the streetcars...
Suppose we live in a monocentric city where streetcars have replaced horse carts. However, the streetcars have begun to break down and slowed in their reliability and speed. Compared to fully functioning streetcars, we expect that Select one: a. residents will outbid agricultural users further from the city center b. residential areas will grow c. city wages will increase d. land rent at the city center will increase
What are the ledgers, why do we use them? And then HOW do we use them,...
What are the ledgers, why do we use them? And then HOW do we use them, how does information get into them how do balances get extracted. And then what should the balances for various accounts be, i.e. assets, liabilities, expenses, revenues, equity, dividends. Why SHOULD they have a particular balance as either debit or credit.
Suppose we have an economy where the population is the same every period, Nt = N...
Suppose we have an economy where the population is the same every period, Nt = N and the money supply is increasing by z each period, i.e., Mt = zMt−1. The government uses the money it creates each period to finance a lump-sum subsidy of a ∗ goods to each old person. (a) (10 points) Find the equation for the budget set of an individual in the monetary equilibrium. Graph it. Show an arbitrary indifference curve tangent to the set...
Suppose we have the following vectorial equation c = na x b where n is a...
Suppose we have the following vectorial equation c = na x b where n is a constant, and c, a, b are vectors Givens n = -1 a = 2i – j a) Determine the direction and size of the vector c if b = 2i b) Determine the direction and size of the vector c if b = 2k c) Determine the direction and size of the vector c if b = 2i – k I really need the...
What are chi distributions, how do we use them, when do we use them, and why...
What are chi distributions, how do we use them, when do we use them, and why are they important?
Where in the Universe do we observe the ordinary matter? Select one: a. as galaxies and...
Where in the Universe do we observe the ordinary matter? Select one: a. as galaxies and intergalactic gas b. throughout the galaxies and in the extended halos around them c. throughout the observable universe
2. Consider an n-cube, where n = 3. Is it possible to draw this on a...
2. Consider an n-cube, where n = 3. Is it possible to draw this on a two dimensional plane where the lines do not cross? If it is possible, draw it. If not, prove that it isn't possible.
Usually, the sample size is small (n<30), we would use the t-distribution value. However, if we...
Usually, the sample size is small (n<30), we would use the t-distribution value. However, if we know the population standard deviation, we still use the z-distribution value even though the sample size is small. Describe what the reason that we use z-distribution if we know the population standard deviation.
You are encouraged to research outside sources and, of course, cite them. Do not, however, quote...
You are encouraged to research outside sources and, of course, cite them. Do not, however, quote sources word-for-word, but rather, respond to the Discussion Forum Question in your own words. 1.     What three factors would influence your evaluation as to whether a company’s current ratio is good or bad, why? 2.     Suggest several reasons why a 2:1 current ratio might not be adequate for a particular company. 3.     Why is working capital given special attention in the process of analyzing...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT