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 14:30, chaparro0512
Create a pseudocode design to prompt a student for their student id and the titles of the three classes they want to add. the solution should display the student’s id and a total bill. • bill a student using the following rules: o students can only add up to 3 classes at a time.
Answers: 3
image
Computers and Technology, 22.06.2019 17:00, joshualoz5414
Acase study allows a more detailed look at the life of a single subject than any other study.
Answers: 3
image
Computers and Technology, 23.06.2019 03:30, 890777
In vista and windows 7, the appearance and personalization option allows you to change the
Answers: 1
image
Computers and Technology, 23.06.2019 18:20, Blossom824
What is wi-fi infrastructure? a metropolitan area network that uses radio signals to transmit and receive data a communications technology aimed at providing high-speed wireless data over metropolitan area networks a means by which portable devices can connect wirelessly to a local area network, using access points that send and receive data via radio waves includes the inner workings of a wi-fi service or utility, including the signal transmitters, towers, or poles and additional equipment required to send out a wi-fi signal
Answers: 2
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
Biology, 08.01.2021 06:10
Konu
Mathematics, 08.01.2021 06:20