[Decision Tree] [Algorithm]

The question is based on the Findfake2 algorithm provided below. Your coinpile will be called C. You can refer to each of its n elements as C[1], ..., C[n] and the pile of all elements from a to b inclusive as C[a-b].

1 a. Draw a decision tree for the Findfake2 algorithm for a coinpile C of size 13.

1 b. Based on this decision tree what can you conclude about the worst case performance of this algorithm? Explain your answer.

Pseudocode for Findfake2 The algorithm above can be described in pseudocode as follows: Findfake2 (coinpile 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 Find fake2 (coinpile, n) if n-1 return the first coin in coinpile halfn n div 2 pile 1 Collection of coins consisting of the first halfn elements of coinpile pile 2 Collection of coins consisting of the next halfn elements of coinpile compareweight. Weigh (pilel,pile2 if compareweight 1 return Findfake2 (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 coinpile2 weigh the same 1 is coinpilel weighs more than coinpile2