Devise an algorithm that meets the lower bound

Assignment Help Mathematics
Reference no: EM131636698

Question: Concern the problem of identifying a counterfeit coin (one that is two heavy or too light) from a set of n coins. A balance scale is used to weigh a group of any number of coins from the set against a like number of coins from the set. The outcome of such a comparison is that group A weighs less than, the same as, or more than group B. A decision tree representing the sequence of comparisons done will thus be a ternary tree, where an internal node can have three children.

One of eight coins is counterfeit and is either too heavy or too light. The problem is to identify the counterfeit coin and determine whether it is heavy or light.

a. What is the number of final outcomes (the number of leaves in the decision tree)?

b. Find a lower bound on the number of comparisons required to solve this problem in the worst case.

c. Devise an algorithm that meets this lower bound (draw its decision tree).

Reference no: EM131636698

Questions Cloud

Work environment affects employee productivity and morale : Since physical work environment affects employee productivity and morale, the employees themselves should have right to decide how their workplace is designed.
Discuss rules of ethical behavior in the organization : How did this ethical culture affect your work performance and morale, Were the written rules of ethical behavior in this organization
How selected agency will hire culturally competent workforce : Recommend at least two strategies for how your selected agency will hire and develop a culturally competent workforce, especially at high levels.
Donald trumps 2016 presidential campaign : How has Donald Trump's 2016 presidential campaign been so successful? What apparently large groups does his support base consist of?
Devise an algorithm that meets the lower bound : Concern the problem of identifying a counterfeit coin (one that is two heavy or too light) from a set of n coins.
About the company stericycle : This is a question about the company "Stericycle" What are their strengths and weaknesses in a changing economic landscape.
Find a lower bound on the number of comparisons : Find a lower bound on the number of comparisons required to solve this problem in the worst case.
Discussing free movement of peoples across the continent : In Africa, various AU members have been discussing free movement of peoples across the continent, however, this is yet to be fully realised.
Correlation measures strength and direction of relationship : Correlation measures the strength and direction of relationship between two variables.

Reviews

Write a Review

Mathematics Questions & Answers

  Estimate the relative error in the calculated surface area

Estimate the relative error in the calculated surface area.

  Alex is building a ramp for a bike competition he has two

alex is building a ramp for a bike competition. he has two rectangular boards. one board is six meters and the other is

  What is the chance that not all of them are right-handed

It has been asserted that 15% of all people are left-handed. In a random group of 10 people, what is the chance that not all of them are right-handed?

  What is the cost equation

A bakery makes cakes. The bakery has daily fixed costs of $418 per day and variable costs of $7.30 per cake produced. Cakes are sold for $12.80 each.

  Standard deviation, and coefficient of variation problems

If a filled container of juice is selected at random, what is the probability that it is an acceptable container?

  Find the total distance it travels

A ball drops from a height of 21 feet. Each time it hits the ground, it bounces up 80 percents of the height it fall. Assume it goes on forever, find the total distance it travels.

  What angle of inclination docs that correspond to

What angle of inclination docs that correspond to?

  Find the rate of change of heart rate

The equation R(v) =5800 / v can be used to determine the heart rate, R, of a person. Find the rate of change of heart rate with respect to v, the output per beat.

  Probability-permautations-combinations

35% of a store's computers come from factory A and the remainder come from factory B.2% of computers from factory A are defective while 1% of computers from factory B are defective.

  Find the total distance traveled during the first six second

A particle moves according to a law of motion s = f(t) = t3 -9t2+24t, t ≥ 0. When is the particle moving in the positive direction? Find the total distance traveled during the first 6 s.

  A c drive and h drive what is h

Question 1: I have a C drive and H drive , what is H ? Question: If Anu had Rs 600 left after spending 75% of her money,how much did she have in the beginning ? Answer both mathematiics question

  Calculate the test statistic

Calculate the test statistic.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd