[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].

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

b. Extrapolating from the tree you just built, what will be

- the number of leaves of a decision tree for Findfake2 when the coinpile has n element?

- the height of a decision tree for Findfake2 when the coinpile has n elements?

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