[Pseudocode] [Algorithm] Improving Efficiency I am supposed to further improve t

Question

[Pseudocode] [Algorithm] Improving Efficiency

I am supposed to further improve the efficiency of this given algorithm. (Provided Below)

Q) So you improved your Findfake algorithm substantially by dividing the piles of coins into 3 rather than 2... Let's keep on going then...

Can you come up with a value of m>3 and a Findfakem algorithm which splits the pile of coins at every step into m equal sized piles and which has a better worst case efficiency than Findfake3? Explain your answer methodically and support it mathematically. Please provide explanation regarding why it is better?

Findfake3(coinpile, n)
   if n=1 return the first coin in coinpile
   if n=2 and weight of coin1 > weight of coin2 then return coin2
   else return coin1
  
   thirdn = n div 3
   pile1 = 1/3rd of the first coins in coinpile
   pile2 = 1/3rd of the next coins in coinpile
   pile3 = 1/3rd of the last coins in coinpile
   compareweight = Weigh(pile1,pile2,pile3);
   if compareweight = 1 return Findfake3(pile1,thirdn)
   if compareweight = 2 return Findfake3(pile2,thirdn)
   if compareweight = 3 return Findfake3(pile3,thirdn)
   return Findfake(last 2 coins of coinpile,2)
  
//Weigh(coinpile1, coinpile2, coinpile3) returns:
//0 if all 3 coinpiles have equal weight
//1 if coinpile2 and coinpile3 weigh the same
//2 if coinpile1 and coinpile3 weigh the same
//3 if coinpile1 and coinpile2 weigh the same

Explanation / Answer

Ans .

Case 1 : If we divide the coins in two stacks .Each containing same number of coins .Then we have only two cases . Big O of the decrease by factor 2 is log2n. But it is less efficient so we divide it by factor 3.

Case 2: So if we take example to divide the coins in 3.

Then, if n=1 , then there is nothing to do

If n>1 then, divide coins into equal piles A,B [ n/3 ]and C of size n-2[n/3] . First we will check weight A against B. If they are equal or balance ,then fake coin is in in the C. If not then fake coin is in the either in A or B. In every case ,we recursively check for the fake coin.

Now we prove that the number of weighings required is at most [log3 n]. Equivalently, we are to show that that if n 3 N , then we use at most N weighings. If n = 1, we use N = 0 weighings, so this case is correct. If n > 1, we use 1 + M weighings, where M is the number of weighings for the recursive call. In every case, the number of coins for the recursive call is m [n/3], since n – 2[n/3] n 2(n/3) = n/3 [n/3]. Note that [3 N /3] = 3N /3 = 3N1 , and [n/3] is an increasing function of n, so if n 3 N , then 1 [n/3] 3 N1 . It follows by induction that the recursive call takes at most M = N 1 weighings, and the original problem therefore takes at most N weighings. Finally, we prove that it is impossible to do better than this in general. There are n possibilities for which coin is counterfeit. Each weighing has one of three outcomes (pile 1 heavy, pile 2 heavy, or balance). A sequence of N weighings has 3N possible outcomes. Therefore any algorithm that can identify the counterfeit coin using at most N weighings must have 3N n, or equivalently N [log3 n].

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.