Determine the time complexity of your algorithm

Assignment Help Computer Engineering

Reference no: EM131832830

Problem

Consider the following problem:

(a) Suppose we have nine identical-looking coins numbered 1 through 9 and only one of the coins is heavier than the others. Suppose further that you have one balance scale and are allowed only two weighing. Develop a method for finding the heavier counterfeit coin given these constraints.

(b) Suppose we now have an integer n (that represents n coins) and only one of the coins is heavier than the others. Suppose further that n is a power of 3 and you are allowed log3 n weighing to determine the heavier coin. Write an algorithm that solves this problem. Determine the time complexity of your algorithm.

Reference no: EM131832830

Questions Cloud

When the given events happen : When the following events happen, does the unemployment rate rise, fall, or stay the same?

What is the probability that a student who is a cigarette : What is the probability that a student who is a cigarette smoker is a man? A woman?

How many big ideas will come along each year : If the world's population now gets cut in half from the current 6 billion, how many big ideas will come along each year?

What is the conditional probability : Consider an urn containing 12 balls, of which 8 are white. Let a sample of size 4 be drawn with replacement (without replacement).

Determine the time complexity of your algorithm : Suppose we now have an integer n (that represents n coins) and only one of the coins is heavier than the other. Determine the time complexity of your algorithm.

How many total jobs are destroyed for every net job created : Let's see how many jobs have to be destroyed for one net job to be created. As noted in the text, millions of jobs are created and destroyed every month.

What is the probability that the ball selected from urn : What is the probability that the ball selected from urn II will be white, given that the sample drawn contains exactly 2 white balls?

Write a divide-and-conquer algorithm that solves the problem : A tromping is a group of three unit squares arranged in an L-shape. Write a divide-and-conquer algorithm that solves this problem.

What is the probability that the urn will contain : What is the probability that the urn will contain exactly 3 white balls, given that the first ball placed in the urn was white?

User Account

All Pages