How to write pseudocode for general case?

Question

I'm going to start tutoring so I decided to work on some old problems from my algorithms class. The problem is as follows:

You are selling newspapers and every day you start your route at one intersection and end your route =north-east of where you started. The city streets are on a grid, as depicted below, and you start at (0, 0) and end at (n,m).

A move north takes you from (x, y) to (x, y +1). A move east takes you from (x, y) to (x +1, y). At each intersection (x, y), you stop to sell newspapers and will make an revenue of r (x, y). Let OPT(n,m) denote the total revenue of an optimal walk from (0, 0) to (n,m).

My pseudocode using bottom-up dynamic programming for this problem is as follows:

Bottom-Up-Alg(n,m,s[][]) \\ n and m are coordinates and s holds the revenue at each coordinate (n,m) 
opt = 0      \\ holds optimal revenue
opt += s[0][0] \\value at (0,0)
i = 0
j = 0
while (i <= n and j <= m)
    if (s[i+1][j] > s[i][j+1])
        opt += s[i+1][j]    \\ Move east
        i++
    else
        opt += s[i][j+1]     \\ Move north
        j++
return r

Strictly speaking the running time of this algorithm would be O(n+m). But if n and m are proportional then the running time can be said to be O(n) or O(m).

The problem is I found that my algorithm is greedy and it won't work for every situation. I'm having trouble writing pseudocode that would work in general.

Answer 1

You can number every node, starting from the upper right node, with the maximum revenue you can get if you start from that node, and which prior node gives it that maximum. O(nm).

You do this by sweeping a diagonal from upper right to lower left.

When this numbering reaches the lower left, you have your answer. Just trace back.

22 19-17-15--9
    |
27 26 17 16 14
    |
35-32 22 22 20

ADDED: If you're wondering how to sweep a diagonal, it's easier to visualize than to code.

But here's some C:

for (j = m-1; j >= -(n-1); j--){
  for (ii = n-1; ii >= 0; ii--){
    int jj = j + (n-1) - ii;
    int rii = rjj = 0;
    if (jj >= 0 && jj < m){
      if (ii+1 < n && jj   >= 0 && jj < m)
        rii = r[ii+1][jj];
      if (jj+1 < m && jj+1 >= 0)
        rjj = r[ii][jj+1];
      r[ii][jj] = s[ii][jj] + max( rii, rjj );
    }
  }
}

Basically, ii and jj are the indices of the cell you're working on, and if either its rightward or upward neighbor is outside the rectangle you take its revenue as zero.

Answer 2

This is your TA. I couldn't help but notice that this question was posted before the due date for your homework. Seeing as it's past that date now, the answer you were looking for is the following

BOTTOM-UP-NEWSPAPER(n,m,r)
  opt = array(n,m)
  for i = 0 to n
    for j = 0 to m
      if i = 0 and j = 0      // In starting position
        opt[i][j] = r(i,j)
      else if i = 0 and j > 0 // On the south side of grid
        opt[i][j] = r(i,j) + opt[i][j-1]
      else if j = 0 and i > 0 // On the west side of grid
        opt[i][j] = r(i,j) + opt[i-1][j]
      else                    // Anywhere else
        opt[i][j] = r(i,j) + max(opt[i-1][j], opt[i][j-1])
  opt[n][m] holds the maximum revenue