8. The Coin Collection Problem. 25 marks In the coin collection problem, coins a
ID: 3682542 • Letter: 8
Question
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)Explanation / Answer
Coin Collection Algorithm
Step 1: Start
Step 2 : declare the variables like change ,coinValueList,knownResults
Step 3: Create Procedure/function name as recDC with paramaeters
coinValueList,change,knownResult
Step 4: Assign change to minCoins
Step 5: if change in coinValueList then
knownResults[change] = 1
return 1
Step 6: Otherwise
knownResults[change] > 0:
return knownResults[change]
Step 7: Otherwise
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recDC(coinValueList, change-i,knownResults)
if numCoins < minCoins:
minCoins = numCoins
knownResults[change] = minCoins
Step 8: Stop
PsuedoCode
def recDC(coinValueList,change,knownResults):
minCoins = change
if change in coinValueList:
knownResults[change] = 1
return 1
elif knownResults[change] > 0:
return knownResults[change]
else:
for i in [c for c in coinValueList if c <= change]:
numCoins = 1 + recDC(coinValueList, change-i,
knownResults)
if numCoins < minCoins:
minCoins = numCoins
knownResults[change] = minCoins
return minCoins
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.