1. (10 points) Use divide and conquer approach to write an algorithm that solves
ID: 3601113 • Letter: 1
Question
1. (10 points) Use divide and conquer approach to write an algorithm that solves the following problem. Suppose we have n identical-looking coins numbered 1 through n and only one of the coins is lighter tha the others. Suppose th at n is a power of 3. Suppose further that you have one balance scale and are allowed logan weighings to determine the lighter coin. Determine the time complexity of your algorithn Use the given problem instance: n-81, and the #73 coin is the lighter coin, to illustrate how your algorith works. Analyze your algorithm, show the results in Big-O notations, using the lowest upper bound.Explanation / Answer
To find out the lighter coin in this case we must divide the given set of coins into three groups A,B and C, each containing the equal number of coins. Now put the set A on one pan of the weighing scale and set B on the other scale. If the pan with A raises up that means that the set A contains the lighter coin and if the pan with the set B raises up that means set B contains lighter coin. If both the pans are balanced that means the set C contains lighter coin.
Suppose that the set A contains the lighter coin. Now again divide the set A into three different sets. Follow this approach and at the end we will be left with the lighter coin.
As we are dividing the given problem by 3 everytime, hence we will be requiring only Log3N number of weighings.
coins(Arr,p,q,r,s)
{
A=Arr[p..q]
B=Arr[q..r]
C=Arr[r..s]
if (A.length==1 and B.length==1 and C.length==1)
{
if(A heavier than B)
{
return B
}
else if(B heavier than A)
{
return A
}
else
{
return C
}
}
else
{
if(A heavier than B)
{
return coins(Arr,q,(q+r)/3,2*((q+r)/3),r)
}
else if(B heavier than A)
{
return coins(Arr,p,(p+q)/3,2*((p+q)/3),q)
}
else
{
return coins(Arr,r,(r+s)/3,2*((r+s)/3),s)
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.