Draw a decision tree for an algorithm that solves problem

Assignment Help Basic Computer Science

Reference no: EM131263700

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: EM131263700

Questions Cloud

Describe at least one example of humor in your own career : Describe at least one example of humor in your own career or another part of your life, and analyze what theory or theories are seen in that example.

Lingering unemployment in the economy : "Unemployment insurance, and other government welfare programs, may have played a significant role in the lingering unemployment in the economy since the Great Recession of 2007-2009." Why would this be the case?

How many extra games does your algorithm require : 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?

What are some of the decisions managers use it for : Break-even analysis is a useful tool for decision making. What are some of the decisions managers use it for.

Draw a decision tree for an algorithm that solves problem : 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).

Describe different forms of alternative dispute resolution : Explain the purpose of business law and how the judicial system fits into society -- including business. Differentiate the federal court structure from your state's court structure. Describe the different forms of Alternative Dispute Resolution (ADR)..

What decision making model would you use to make decision : What decision making model would you use to make this decision (Page 244 in the Org. Beh. text)? Would any of the techniques for making better decisions assist us in this decision (Page 255 in the Org. Beh. text)?

Write a research paper about fletc : Write a research paper about FLETC. The total length of the paper must be at least 2,000 words (approximately 8 pages) in APA format - Describe the mission and scope of the organization.

Write a paper on given topic : Write a four page paper. - Taking into consideration each of the three perspectives on inclusive education- educational, social, and legal - How do they impact your responsibility as an educator in terms of student outcomes.

User Account

All Pages