"A feast for gluttons" Your computer science friend is learning about dynamic programming, and has challenged you to a sashimi-eating game of her design. At the start of the game, there are two plates of sashimi, containing n and m pieces respectively. At every turn, a player may eat all the n (or m) pieces of sashimi on one plate, and redistribute the m (or n) pieces from the other plate so that the two plates now contain and m-piece (or similarly if redistributing n pieces). The player who starts the turn with two plates each containing one sashimi piece pays the bil. Your friend is confident that she can win with her secret dynamic programming strategy Luckily, you have also studied dynamic programming in CPSC 320, and so you can always pick a winning move if there is one. Assume that you wil both be playing according to the same strategy. a. Design a dynamic programming algorithm which avoids paying the bill for a game instance with starting plates containing n and m pieces (if there is a winning move for n and m), Pay special attention to the order in which the elements of your table should be led b. Determine an asymptotic running time for your solution and justify your result. "A feast for gluttons" Your computer science friend is learning about dynamic programming, and has challenged you to a sashimi-eating game of her design. At the start of the game, there are two plates of sashimi, containing n and m pieces respectively. At every turn, a player may eat all the n (or m) pieces of sashimi on one plate, and redistribute the m (or n) pieces from the other plate so that the two plates now contain and m-piece (or similarly if redistributing n pieces). The player who starts the turn with two plates each containing one sashimi piece pays the bil. Your friend is confident that she can win with her secret dynamic programming strategy Luckily, you have also studied dynamic programming in CPSC 320, and so you can always pick a winning move if there is one. Assume that you wil both be playing according to the same strategy. a. Design a dynamic programming algorithm which avoids paying the bill for a game instance with starting plates containing n and m pieces (if there is a winning move for n and m), Pay special attention to the order in which the elements of your table should be led b. Determine an asymptotic running time for your solution and justify your result