Algorithms Problem 8. The Coin Collection Problem. 25 marks In the coin collecti
ID: 3682986 • Letter: A
Question
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)Explanation / Answer
Pseudo Code:
//Applies Dynamic Programming to compute the largest number of
//coins a robot can collect an an nxm board starting at (1,1)
//and moving right and down from upper left to down right corner
//Input: Matrix C[1..n, 1..m] whose elements are equal to 1 and 0
//for cells with and without a coin respectively
//Output: Largest number of coins the robot can collect and bring to cell (n,m)
F[1,1] <– C [1,1]; for j <– 2 to m do F [1,j] <– F [1, j-1]+C[1.j]
for i <– 2to ndo
F[i,1] <– F[i -1, 1] + C[i, 1]
for j <– 2tomdo
F[i,j] <– max(F[i-1,k], F[i,j-1]) + C[i,j]
return F[n,m]
Analysis:
The Time Efficiency is theta(nm) because it takes a constant time. The Space Efficiencty is also theta(nm).
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.