Algorithms Problem

8. The Coin Collection Problem. 25 marks In the coin collection problem, coins are placed in cells of an n x m board, with no more than one coin per cell. A robot, located in the upper left cell, position (1,1), of the board, needs to collect as many of the coins as possible and bring them to the bottom right cell (position (n, m). In each step, the robot can move either one cell to the right or one cell down from its current location. When the robot visits a cell with a coin, it always picks up the coin located there (a) Give pseudocode for a dynamic programming algorithm to find the maximum number of coins the robot can collect and a path it needs to follow in solving the coin collection problem. Analyze the time and space requirements of your algorithm. [10 marks (b) Now, modify the dynamic programming algorithm in part (a) for the case where some cells on the board are inaccessible to the robot. Are there any changes to the time or space requirements of your algorithm? 5 marks (c) Apply your algorithm to the board in Figure 3, where the inaccessible cells are marked by X's 5 marks (State the maximum number of coins and a path the robot needs to follow to collect them.) (d) How many optimal paths are there for the board in Figure 3? 5 marks XXXI Figure 3: A 5 x 6 board for the coin collection problem, Question 8, parts (c) and (d)