Go Back

Sweepy the Robot

  1. Define the subproblems for your solution.
    1. Let MDC(i,j) denote the maximum number of dirty cells visited by Sweepy up to cell (i,j) on the carpet.
  1. Give a recursive formulation to solve the subproblems. Include the base cases.
    MDC(i, j) = carpet[i, j] + max(MDC(i, j-1), MDC(i-1, j))
    1. The base cases will be:
      F(i, 0) = carpet[i, 0] + F(i-1, 0) for all i > 0
F(0, j) = carpet[0, j] + F(0, j-1) for all j > 0
F(0, 0) = carpet[0, 0]
  1. Give pseudocode for a memoized, top-down algorithm that outputs this maximum.
    Initialize a 2D array memo of size n*m with -1
Define function MDC(i, j):
  if i < 0 or j < 0:
    return 0
  if memo[i][j] is not -1:
    return memo[i][j]
  memo[i][j] = carpet[i, j] + max(MDC(i, j-1), MDC(i-1, j))
  return memo[i][j]
  1. Give pseudocode for an efficient, bottom-up algorithm that outputs this maximum.
    Initialize a 2D array dp of size n*m with 0
dp[0][0] = carpet[0][0]
for i from 0 to n-1:
  for j from 0 to m-1:
    if i > 0:
      dp[i][j] = max(dp[i][j], dp[i-1][j] + carpet[i][j])
    if j > 0:
      dp[i][j] = max(dp[i][j], dp[i][j-1] + carpet[i][j])
return dp[n-1][m-1]
  1. What is the runtime of your solution? Justify your answer.
    1. The runtime for both the memoized top-down and bottom-up dynamic programming solutions is O(n*m) where n and m are the dimensions of the carpet. This is because each cell (i, j) is computed exactly once, and each computation takes O(1) time.
  1. Explain how to modify your algorithm to output the path taken by .
    1. To output the path taken by Sweepy, we would modify the bottom-up dynamic programming approach to store not only the maximum number of dirty cells but also the direction from which the maximum was reached (either from the left or above). Then, we would start from cell (n-1, m-1) and trace back the path to (0, 0) using these directions.
    1. Add a 2D array parent of size n*m to store the direction of the move. Update the algorithm to fill parent[i][j] with either 'L' or 'U' depending on the move. After filling the dp array, start from dp[n-1][m-1] and trace back the path using the parent array. Store the path in a list or array and return it