Algorithm Analysis: There are n stacks of n identical-look coins. All of the coi

Question

Algorithm Analysis:

There are n stacks of n identical-look coins. All of the coins in one of these stacks are counterfeit, while all the coins in the other stacks are genuine. Every genuine coin weighs 10 grams; every fake weighs 11 grams. You have an analytical scale that can determine the exact weight of any number of coins.

a. Devise a brute-force algorithm to identify the stack with the fake coins and determine its worst-case efficiency class.

b. What is the minimum number of weighings needed to identify the stack with the fake coins?

Explanation / Answer

1.store max=0 and index=-1

2. loop across each stack and find the weight of each stack with n coins

3. then if weight > max then max = weight, index=stack position else nothing

4. now after the loop, the index will contain the stack with all fake coins as fake coins weight more

worst case is when the fake coins are in last stack and we have to calculate through all the stacks.

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

b. minimum number of weighings is when we divide and conquer the problem. we divide the n stacks into two n/2 stacks,

then the one n/2 stacks with max weight will contain the fake coins, again we divide those n/2 to two more n/4 stacks and we continue till we find the stack

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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