Answer Happy

a Problem: The Perfect Game There is a gangster near you that owns a game. He attracts children to play it for $1 per trial. If the child wins, he gives him a free gift. The rules are as below: • There is a box filled with a balls • The child along with the game owner switch turns such that in each turn a player could draw k balls at once at two conditions: VREZ1 <ksn • The child draws first. • The player who draws the last ball, wins As a game owner, the gangster controls everything maintaining profit, cheating the children. You decided to help the students teaching the gangster a lesson. You want to train the students to know when the situation is hopeless, and when they could win. Therefore you want to build an algorithm that given, n, can tell us if the starting play can win or not-this is assuming all the parties play optimally. With the help of your program, you will make the student practice with your algorithm to know which values are good, and which are not. a) Design a recursive algorithm that takes as input the value n outputs True if the child could win or False otherwise. 5.5 Points) b) Design a Top-Down DP solution with the help of your recursive algorithm (1.5 Points c) Design a Bottom-Up DP solution of the same algorithm (4 Points) d) Empirically, show the performance curve of the algorithms 4 Points) e) Theoretically, show the complexity of the 3 algorithms 15 Points Input Output True Examples Explanation The child draws the only ball and wins The child can only draw 1 ball, as 1 is the only number 2 and Vī e Z. 12¢Z, so we cannot use it Hence, the game owner draws the last ball The child could draw 4 balls at once because V=2 €ZA454 2 False 4 True