[Pseudocode] [Algorithm] [code] Improving Efficiency

Below you can find the algorithm and additional information that might help solve the following question.

a) The Findfake algorithm is missing some important implementation details which might impact the real cost of the whole algorithm. In particular there are no details on the implementation of the function Weigh which is chosen as the basic operation in the analysis of the efficiency of the Findfake algorithm. This choice of the basic operation makes 2 assumptions about the costs of doing some of the work in the Findfake algorithm. State what these two assumptions are and explain whether you think they are reasonable and why. Support your opinion in a convincing way.

b) Design a pseudocode algorithm Findfake3 to solve the fake coin problem more efficiently than Findfake by splitting each pile of coins into 3 piles of the same size and then making some smart decisions about how to weight these piles and reach conclusions about the location of the fake coin. Your algorithm cannot change the functionality of the Weigh function. Make sure that your algorithm handles properly all the values of n, not just those that are multiples of 3.

Pseudocode for Findfa The algorithm above can be described in pseudocode as follows: Findfake2 ile n) returns coin. Coin is a data structure representing coins coinpile is a Collection of Coins n is the size of coinpile It is known that there is one fake coin in coinpile Findfake2 (coinpile, n) if n 1 return the first coin in coinpile halfn n div 2 pilel Collection of coins consisting of the first halfn elements of coinpile pile2 Collection of coins consisting of the next halfn elements of coinpile compareweight Weigh (pile 1, pile2) if compareweight 1 return Find fake2 (pilel halfn) if compareweight 1 return Findfake2 (pile2, halfn return nth coin in coinpile Weigh (coinpilel, coinpile2 returns -1 is coinpilel weighs less than coinpile2 0 if coinpilel and coinpile 2 weigh the same 1 is coinpilel weighs more than coinpile2 Additional Information 1. The size of the problem is n of coins in coinpile 2. The basic operation is a function call to the Weigh function 3. The best case scenario is when n s odd and the fake coin is the last coin of the coinpile collection. In that case Weigh will only be called once and therefore Findfake2 is O n the best case. 4. The worst case scenario is when the decision is only made when weighing two coins against each other after all the other c have been discarded (except possibly for a third one if 3 in the last function call) In this case, since Findfake2 is recursive, we need to set up a recurrence relation for its cost, as follows: Let C(n) Hof times the function Weigh is called when coinpile had n elements C (1) 0: C(n) 1+C(floor (n/2)) if n 1 This recurrence relation is more or less the same as the one we saw in the algorithm to find the binary representation of an integer, and also in the binary search algorithm. The difference is in the starting condition As in these two algorithms, the recurrence relation is solved by first assuming that floor (n/2) n/2 at each step. In other words that n 2k from some k. i.e. k log2n This changes the recurrence relation to C (20) 0, C(2 C(2 if k>0 k-2 k-3 k-k Substituting back into the recurrence relation, you get C(n C (2 C(2 C(2 +1+1+C(2 k+C (2 k C(2