Draw a decision tree for an algorithm

Assignment Help Basic Computer Science

Reference no: EM131252784

Advanced fake-coin problem There are n ≥ 3 coins identical in appearance; either all are genuine or exactly one of them is fake. It is unknown whether the fake coin is lighter or heavier than the genuine one. You have a balance scale with which you can compare any two sets of coins. That is, by tipping to the left, to the right, or staying even, the balance scale will tell whether the sets weigh the same or which of the sets is heavier than the other, but not by how much. The problem is to find whether all the coins are genuine and, if not, to find the fake coin and establish whether it is lighter or heavier than the genuine ones.

a. Prove that any algorithm for this problem must make at least [log3(2n + 1)] weighings in the worst case.

b. Draw a decision tree for an algorithm that solves the problem for n = 3 coins in two weighings.

c. Prove that there exists no algorithm that solves the problem for n = 4 coins in two weighings.

d. Draw a decision tree for an algorithm that solves the problem for n = 4 coins in two weighings by using an extra coin known to be genuine.

e. Draw a decision tree for an algorithm that solves the classic version of the problem-that for n = 12 coins in three weighings (with no extra coins being used).

Reference no: EM131252784

Questions Cloud

Find all the mixed strategy equilibria of the game : Specify this situation as a strategic game. - Use the symmetry of the game to show that the unique equilibrium payoff of each player is 0.

Identify health concerns or disease : Create a public service ad, with appropriate images, to be printed in the Sunday edition of your newspaper. Include the following points: Identify the nutritional needs for a developing embryo and fetus and how to obtain them. Identify health concer..

How many rounds are there in such a tournament : Design an efficient algorithm to determine the second-best player using the information produced by the tournament. How many extra games does your algorithm require?

How job analysis and job evaluation could be used : Determine how job analysis and job evaluation could be used at Customers First to develop an internally consistent compensation system.

Draw a decision tree for an algorithm : Draw a decision tree for an algorithm that solves the classic version of the problem-that for n = 12 coins in three weighings (with no extra coins being used).

Find a completely mixed nash equilibrium : Find a completely mixed Nash equilibrium in which each player assigns the same probability to the actions 1, 2, and 3.

Briefly explain the two types of privileged relationships : Determine the differences between an inference or conclusive presumption, a true presumption, a rebuttal presumption, and a mandatory presumption.

Determine the best way to leverage compensation surveys : Determine the best way to leverage compensation surveys to set the level of compensation for your current (or future) job position. Provide specific examples to support your response.

Write an autobiography of you in relation to your career : Write an autobiography of you in relation to your career. The purpose of this assignment is to give you an opportunity to reflect on how your career has been shaped by your life thus far and what you are looking for in future career opportunities

User Account

All Pages