MPCS 55001 Algorithms Winter 2025

Homework 3

1    Whetting your Appetite: DP Smorgasbord (20 points)

You are given an m × n array A.  Each square A[i,j] contains a positive integer which represents the cost to visit that square. You are currently standing on the top left square of the array:  A[1, 1]. You wish to find the total cost of the lowest cost path from this square to the bottom right square A[m,n]. You may only move one unit to the right or down at a time.  Your total cost is the sum of the integers in all the squares you visit on your path  (including A[1, 1] and A[m,n]).

Table 1: Example problem on a 5 × 4 grid.  Total cost is 13 = 1+1+2+1+4+1+2+1. There might exist multiple lowest cost paths.

The subproblem we will use to answer this question is:

DP[i,j] = the minimum cost of a path from square (1, 1) to square (i,j).

(a)  (1 point) Given the subproblem above, what is the value of DP[1 , 1]; that is, what is the minimum cost of a path from square (1, 1) to square (1, 1)?

(b)  (1 point) Suppose you are standing at position (4 , 4) on some input grid A, and you know that DP[4, 3] = 6 and DP[3, 4] = 9.  Furthermore, you know A[4, 4] = 1.  What is the value of DP[4, 4]?

(c)  (2 points) Considering parts (a) and (b), write a recurrence which expresses the solution to each subproblem in terms of smaller subproblems.  State any base case(s).  Justify your recurrence and state the time complexity of your recurrence.

Next we will explore modifications to the problem considered above. We will examine how these modifications impact our subproblems and recurrences.

For variations (d) and (e) below, write a new recurrence which expresses the solution of each subproblem in terms of smaller subproblems.  State any base case(s).  Justify your recurrence and state the time complexity for a single entry. You should use the same subproblem we provided above.

(d)  Suppose now that you may move either one or two positions to the right or down at a time (you may not move diagonally). However, every time you move two positions you must pay an extra fixed cost c.

•  (2 points) Recurrence:

(e) You may now move to any square that is further down or to the right (or both). However, for any move you need to pay an extra cost equal to the square of the distance you traveled. For example, moving from (x1 , y1 ) to (x2 , y2 ), where x1  ≤ x2  and y1  ≤ y2 , costs g = (x2  − x1 )2  + (y2  − y1 )2 .

•  (2 points) Recurrence:

For variations (f), (g), and (h), you must:

•  Define a new  subproblem that you will use to solve this problem precisely.   Define  any  variables you introduce. What are the dimensions of your dynamic programming table? What is the space complexity?

• Write a new recurrence which expresses the solution to each subproblem in terms of smaller subproblems.  State any base case(s). Justify your recurrence and state the time complexity of your recurrence.

(f) In addition to being able to move to any square that is further down or to the right (as defined in (e) above), you are given a single “coupon” which allows you to land on one square without paying its cost.

•  (2 points) Subproblem:

•  (2 points) Recurrence:

(g) You are given k such coupons which allow you land on a square without paying its cost.

•  (2 points) Subproblem:

•  (2 points) Recurrence:

(h) You may only move one position to the right or down at a time (as in the original problem). In addition, you may only move right k times in a row.  For example, if k = 2, then if you move right twice, your next move must be down.

•  (2 points) Subproblem:

•  (2 points) Recurrence:

2 Largest Square of Contiguous 1’s  (15 points)

You are given an n × n bitmap, represented by an n × n matrix M[1..n,1..n] of 0s and 1s. An all 1’s  block in M is a submatrix of the form M[i..i′ ,j..j′] in which all bits are equal to 1.  An all  1’s block is square  if it has the same number of rows and columns.

Give a dynamic programming algorithm to find the maximum area of an all 1’s square block in M in O(n2 ) time.  (You do not need to locate such a largest all-ones square, just determine its area.)

Example input:

Example output: 9

In this example, the area of the largest all 1’s square block is 9.  There are two 3 × 3 all  1’s square blocks.  One is indicated below by bold; the other by underlines.

(a)  (3 points) Define the subproblem that you will use to solve this problem precisely.  Define any variables you introduce.

(b)  (4 points) Give a recurrence that expresses the solution of each subproblem in terms of the solutions of smaller subproblems. State any base case(s).

(c)  (3 points) Write pseudocode for a dynamic programming algorithm to solve this problem.  Your algorithm should run in O(n2 ) time.

Now we allow rectangular blocks.  Give a dynamic programming algorithm to find the maximum area of an all 1’s rectangular block in M in O(n3 ) time.  (Note: O(n2 ) is possible.)

(d)  (2 points) Define the subproblem that you will use to solve this problem precisely.

(e)  (3 points) Give a recurrence that expresses the solution of each subproblem in terms of the solutions of smaller subproblems. State any base case(s).

3 Card Game (16 points)

A new card game is taking campus by storm!  This game is played using a specialized deck, with number cards (which can represent any integer) and wild cards.  Cards are placed face up in two rows of n cards each.  You need to remove cards to make the two rows match while achieving the maximum score possible. You are only allowed to remove cards; you are otherwise not allowed to move the cards, i.e., the order of the remaining cards in each row must be preserved. Scoring works as follows, working from left to right:

•  A pair of matching number cards adds that number to your score.  Of course, if the cards are negative, this would lower your score.

• Wild cards can match with any number card.  In this case, you multiply the current score by that number, instead of adding.

• If you match two wild cards, you must choose whether to multiply the current score by 25 or −25. Suppose the two rows are as follows. * indicates a wild card.

8     -3   -10   -9   -7   -5

2   -10      8   -7   -9     *

The best solution, for a total of 133 points, is to match the −10 cards, the −9 cards, and the wild card to the −7.

-10   -9   -7

-10 -9     *

Table 2: Explanation of solution to example.

The two rows of cards are given in arrays A[1 ... n] and B[1 ... n].

In this problem, you will develop a dynamic  programming algorithm to solve this problem,  and output the maximum possible score. Your algorithm must run in O(n2 ) time.

First, though, consider a restricted version of the problem, where all number cards have positive value.  Wild cards can still appear; if you match two wildcards, you multiply the current score by 25.

(a)  (4 points) Define the subproblem that you will use to solve the restricted problem precisely.  Define any variables you introduce.

(b)  (4 points) Give a recurrence which expresses the solution to each subproblem in terms of the solutions of smaller subproblems. Specify any base case(s).

(c)  (4 points) Write pseudocode for an algorithm to solve this problem. Your algorithm must run in O(n2 ) time.

Now consider generalizing your algorithm to the full version of the game, in which number cards can have negative values, and matching two wild cards lets you multiply the score by 25 or −25.

(d)  (4 points) Give a new recurrence which expresses the solution to each subproblem in terms of the solutions to smaller subproblems. Specify any base case(s). If necessary, you can also define new subproblems.

4 Programming: River Crossing (20 points)

Follow this GitHub Classroom link to accept the assignment.  Your code should be pushed to GitHub; you do not need to include it here.

5 Survey (1 point)

(a) What was the most challenging concept or problem this week?

(b) Which concept or problem did you enjoy the most this week?

(c)  Other comments?