subject

Assume we are given 12 gold bars numbered 1 to 12 where 11 bars are pure gold and one is counterfeit: either gold-plated lead (which is heavier than gold), or gold-plated tin (lighter than gold). The problem is to find the counterfeit bar and what metal it is made of using only a balance scale. Any number of bars can be placed on each side of the scale, and each use of the scale produces one of three outcomes: either the left side is heavier, or the two sides are the same weight, or the right side is heavier. a. Give a decision tree lower bound for the (worst case) number of weighings that must be performed by any algorithm solving this problem.
b. Design an algorithm that solves this problem with (worst case) number of weighings equal to the lower bound you found in (a). Present your algorithm by drawing a decision tree, rather than pseudo-code.
c. Alter the problem slightly to allow the possibility that all 12 bars are pure gold. Thus there is one additional possible verdict: "all gold". Make a minor change to your algorithm in part (b) so that it gives a correct answer to this more general problem.

ansver
Answers: 1

Other questions on the subject: Computers and Technology

image
Computers and Technology, 22.06.2019 15:30, alexdub9649
What is a costume plot? why is it important to a film or theater production?
Answers: 2
image
Computers and Technology, 22.06.2019 18:00, Geo777
Suppose an astronomer discovers a large, spherical-shaped body orbiting the sun. the body is composed mostly of rock, and there are no other bodies sharing its orbit. what is the best way to categorize this body? a. planet b. moon c. comet d. asteroid
Answers: 1
image
Computers and Technology, 22.06.2019 20:00, ksanchez2100
Need asap assignment directions: think of an organization (business, religious institution, volunteer organization, sports team) with which you have been involved. imagine outfitting it with an it infrastructure. prepare a plan for what you would do to support outfitting it. draw a map of a network connecting all the individuals, give them pcs and printers, and lay out the design as best you can. the purpose is to begin working with these concepts, not to build a perfect network.
Answers: 2
image
Computers and Technology, 23.06.2019 09:30, rscvsdfsrysas3712
Why is an outfitting a workspace with video games in a technology development company considered a strategic use of money
Answers: 1
You know the right answer?
Assume we are given 12 gold bars numbered 1 to 12 where 11 bars are pure gold and one is counterfeit...

Questions in other subjects:

Konu
Mathematics, 10.02.2021 23:20
Konu
Social Studies, 10.02.2021 23:20
Konu
Mathematics, 10.02.2021 23:20
Konu
Mathematics, 10.02.2021 23:20