CSC-152 2000S : Notes on Exam 2: Algorithms

Some of you clearly are unable to write or evaluate recurrence relations. I tended to go easy on you in such cases, not counting the second and third parts involving recurrence relations if you totally screwed up the first. If this applies to you, you need to come talk to me soon.

Relying on Code

A few of you wrote things like ``I implemented the code and it always worked right'' (particularly for the dropping of the val=1 base case). I expect that the problem has to do with how you coded things. Nonetheless, I tended to discount these problems (counting them as neither positive nor negative).

Big O

Many of you seem confused about the use of big-O notation. For example, I saw some of you write ``O(n) = n²'' or something similar.

Big O is a set of functions. O(n) is the set of functions that are bounded above by the function g(n) = n. O(n) cannot equal anything else.

For some reason, many of you came up with 99 as the answer on the minimum stamps problem. While that's correct, I found it odd that so many of you ended up with the same number.

Misunderstanding of MinStamps

A few of you read the incorrect solution to the MinStamps and decided that it did something on the order of:

However, it does not. It is really a hybrid algorithm. Each step, it decides whether to use a greedy or divide-and-conquer solution. For example, given 90 cents, it would try

Counting Paths Combinatorially

Evaluating Recurrence Relations Bottom-Up

Some of you found that it's easier to evaluate recurrence relations bottom-up instead of top-down. Consider

f(1) = 1
f(n) = n + f(n/2)

f(2) = 2 + f(1) = 3
f(4) = 4 + f(2) = 7
f(8) = 8 + f(4) = 15

Problems

A. A Divide and Conquer Stamp Solution

Recall that in the minimum stamps problem from assignment 3, our goal is to find the minimum number of stamps required to make a particular value.

We observed that a greedy approach does not work. For example, if a package costs 40 cents to mail and stamps cost 50, 33, 20, 5, or 1 cents, we don't want to start with a 33-cent stamp, since that will require four stamps (33 + 5 + 1 + 1) and we can do better with two twenty-cent stamps.

Herman and Hermione Hacker have decided that they ``divide and conquer'' strategy is the best way to approach the minimum stamps problem. However, they know a pure divide and conquer solution is inappropriate since, for example, if the package costs 33 cents, we might as well just use a 33 cent stamp. Hence, they decide that a hybrid approach is appropriate. Here's their sketch of the code:

  /**
   * Compute the minimum number of stamps that exactly totals
   * val cents.
   * Pre: (1) val >= 0
   *      (2) All stamp values are positive.
   *      (3) For each value, there is some combination that
   *          exactly totals that value.
   * Post: Returns N such that (1) it is possible to buy N stamps for
   *       exactly val cents it is not possible to buy M < N stamps
   *       for exactly val cents.
   */
  public static int minimumStamps(int val, int[] stamps)
  {
    // Special case: You need no stamps for 0 cents.
    if (val == 0) {
      return 0;
    }
    // Special case: You need 1 stamp for 1 cents.
    if (val == 1) {
      return 1;
    }

    // Greedy strategy: find the largest possible stamp you can
    // buy and see what that gives you.
    int largestStamp = 0;
    for (int i = 0; i < stamps.length; i++) {
      // If the stamp is cheap enough but larger than
      // our previous guess, update our previous guess.
      if ((stamps[i] <= val) && (stamps[i] > largestStamp))
        largestStamp = stamps[i];
    } // for
    // Here's the value we get from the greedy algorithm
    int greedy = 1 + minimumStamps(val-largestStamp, stamps);

    // Divide-and-conquer strategy: divide in half, find the best
    // for each half, and add.  Note that we need to do things
    // slightly differently for odd and even values.
    int divideAndConquer;
    if (val % 2 == 0) {   // Even
      divideAndConquer = 2*minStamps(val/2, stamps);
    } // even value
    else {                // Odd
      divideAndConquer = minStamps((val+1)/2, stamps) +
                         minStamps((val-1)/2, stamps);
    } // odd value
    
    // Okay, what's our best solution?
    if (greedy < divideAndConquer)
      return greedy;
    else
      return divideAndConquer;
  } // minStamps(int, int[])

A.1. Running time analysis

The Hackers have decided to analyze the running time of their algorithm. Since it's a recursive algorithm, they've decided to rely on a recurrence relation. Here's what they've come up with

f(1) = 1
f(n) = 1        // for the tests
     + n-1      // for the greedy case
     + f(n/2)   // for the recursive case

Assume that their recurrence relation is correct. What does their analysis suggest that the running time of the algorithm is?

A Solution

f(n) = n + f(n/2)                    
     = n + n/2 + f(n/4)
     = n + n/2 + n/4 + f(n/8)
     = n + n/2 + n/4 + n/8 + f(n/16)

f(n) = n + n/2 + n/4 + ... + n/2^(k-1) + f(n/2^k)
     = (2^k-1)/2^(k-1)

f(n) = n + n/2 + n/4 + ... + 2 + 1

n + n/2 = 3n/2
  + n/4 = 7n/4
  + n/8 = 15n/8
  + n/16 = 31n/16

Grading

A.2. Improving the recurrence relation

The Hackers show their solution to their CS professor, who says ``I thought you'd learned algorithm analysis better than that. Go back and check your recurrence relation.'' Yes, their recurrence relation is incorrect.

A Solution

There are two problems with their recurrence relation. One is that they've ignored the case in which val is odd. In that case, there are two recursive calls in the divide-and-conquer section. The other is that they've misstated the cost of the recursive call in the greedy case. That should be f(n-1).

A third problem is that this should be expressed as an inequality, rather than a definite equality. (For example, it's likely that we choose a stamp that costs more than 1 cent in the greedy case.)

A fourth problem is that the running time of the algorithm depends on the number of stamps, which we'll call s.

f(1) <= 1
f(n) <= 1        // for the tests
      + s        // for the loop in the greedy case
      + f(n-1)   // for recursion in the greedy case
      + 2*f(n/2) // for the recursive case

Grading

A.3. An improvement

The Hackers have decided to simplify their code by removing the case when val is 1 because they assume it will be covered in the other cases. However, when they do so, their program seems to run forever, even when val is 1.

A Solution

      divideAndConquer = minStamps((val+1)/2, stamps) +
                         minStamps((val-1)/2, stamps);

When val is 1, (val+1/2) is 1, so it recurses on the same value again and again and again.

Grading

A.4. Checking the Algorithm

Of course, all of this work is for naught if the algorithm is incorrect. And, unfortunately, their algorithm is incorrect.

A Solution

We want a solution in which the greedy solution is unhelpful (typically because it requires us to buy too large a stamp) and the divide-and-conquer solution is also unhelpful (because it doesn't leave enough in either half for the best solution).

Suppose we have stamps that are worth 1, 2, 20, and 33. Consider the case in which val is 42. The best case is to buy three stamps: two 20-cent stamps and one 2-cent stamp.

The greedy part says to buy a 33-cent stamp, leaving 9 cents. The best solution for 9 cents is 5 stamps (4 2-cent stamps and a 1-cent stamp). Hence, the greedy part comes up with at least 6 stamps. (I say ``at least'' because there's no guarantee that the algorithm will work correctly for 9 cents, given that it doesn't work correctly in other places.)

The divide-and-conquer section says to split into two 21-cent problems. The best solution to 21-cents is 2 stamps (a 20-cent stamp and a 1-cent stamp). Hence, this section says that the optimal solution requires at least 4 stamps.

Grading

Since I just said ``find a value'' and didn't ask you to explain that value, I didnt't take off for no explanation unless I couldn't figure out why the answer was wrong.

B. Counting Paths

This problem is worth 40 points. Parts 1-4 are each worth ten points. Part 5 is optional, and is worth 2 points.

The fictional game of Nivlac is played on an N-by-M board, with the squares numbered from (0,0) to (N-1,M-1), as shown in the following diagram

Pieces begin on square (0,0) and progress to (M-1,N-1). The only legal moves are right one square and up one. The rest of the rules are irrelevant to this problem.

Our colleagues, Carla and Carl Caffeinated, have decided to write a program that automatically plays Nivlac. They've decided that it will be helpful to know the number of paths from (0,0) to (M-1,N-1).

They then begin to turn their observation into code. Here's what they came up with.

  /**
   * Compute the number of paths from (0,0) to (X,Y).
   */
  public static int numPaths(int X, int Y)
  {
    // Base case: There is one path from (0,0) to (0,0).
    if ((X == 0) && (Y == 0))
      return 1;
    // Recursive case: See notes
    else
      return numPaths(X-1,Y) + numPaths(X,Y-1);
  } // numPaths(int, int)

B.1. Computation by Hand

In my experience, it's best to work some problems by hand before considering various algorithms. Using whatever correct technique you can come up with, determine how many paths there are from (0,0) to (2,3). Recall that the only valid moves are one space right and one space up.

A Solution

B.2. Base Cases

While the Caffeinateds are correct in their analysis so far, they've missed some of the base cases for this recursive function.

A Solution

      return numPaths(X-1,Y) + numPaths(X,Y-1);

This assumes that both the recursive calls are computable. But what if X or Y is 0 (and not both)? For example, what if X is 5 and Y is 0? Then we need to compute numPaths(4,0), which is presumably okay, and also numPaths(5,-1), which is confusing at the best and infinitely recursive at worst.

The base cases should be when X or Y is 0, in which case there is only 1 path. You can see this in the computations labeled A,B,C,D,E, and I in B1.

B.3. Big-O Analysis

As you might expect, the Caffeinateds are having trouble analyzing the running time of their function. They ask their friendly CS prof for help, and to their surprise, he says

Of course, that doesn't tell them much, so they come to you for help. Determine the running time of the function, given those recurrence relations.

A Solution

f(n) = 2*f(n-1)
     = 2*2*f(n-2)
     = 2*2*2*f(n-3)
     = 2*2*2*2*f(n-4)

B.4. Dynamic Programming

After hearing your answer to B.3., the Caffeinateds have decided to rewrite their code. By reflecting on past algorithm design techniques, they've come to the conclusion that they can improve their solution through dynamic programming. In this case, they want to set up an array, pathCount, so that pathCount[A,B] has the number of paths from (0,0) to (A,B). Here's what they've done so far:

public static int numPaths(int X, int Y) {
  int[][] pathCount = new int[X+1][Y+1];
  // Base case, there is 1 path from (0,0) to (0,0)
  pathCount[0][0] = 1;
  // Other base cases
  ...
  // Fill in the rest of the array:
  ...
  // Done
  return pathCount[X][Y];
} // numPaths(int, int)

The Caffeinateds know that it's possible to fill in the array iteratively, but they're not sure how. They think they can fill in each row and from that compute the next row. Write the missing code. Note that you must fill in the array iteratively (using while and for loops) rather than recursively.

A Solution

public static int numPaths(int N, int M) {
  int[][] pathCount = new int[N+1][M+1];
  // Base case: There is 1 path from (0,0) to (0,0)
  pathCount[0][0] = 1;
  // Base case: There is 1 path from (0,0) to (c,0)
  for (int c = 1; c <= N; c++) {
    pathCount[c][0] = 1;
  }
  // Base case: There is 1 path from (0,0) to (0,r)
  for (int r = 1, r <= M; r++) {
    pathCount[0][r] = 1;
  }
  // Fill in the rest of the array:
  // Fill in each row
  for (int r = 1; r <= M; r++) {
    // Fill in each cell in that row
    for (int c = 1; c <= N; c++) {
      pathCount[c][r] = pathCount[c-1][r] + pathCount[c][r-1];
    } // for each cell in that row
  } // for each row
  // Done
  return pathCount[N][M];
} // numPaths(int, int)

B.5. Revised Big O Analysis

Our friends now worry whether it was worth your time to rewrite their code. Using Big-O notation bound the running time of the revised numPaths.

A Solution

This code is iterative, so we don't need recurrence relations to bound the running time.

An Alternate Counting Solution

Some of you noted that you can count paths more easily using combinatorics. A path to (N,M) requires N Right moves and M Up moves. How many unique ordering of those moves are there?

Let's start with a simplifying assumption. Each move is uniquely identifiable. We might call the different values U₁, U₂, ..., U_M, R₁, R₂, ..., R_N

If we have K different values, there are K! orderings of those values. How do we know this? You can choose any of K things for the first value, any of K-1 for the second, and so on. Hence there are K*(K-1)*(K-2)*...*1 different orderings.

Now we need to eliminate the simplification. First, let's note that all the U's are equivalent. Hence, the ordering

How do we get rid of this overcounting? We note that each ordering is equivalent to any other ordering with U's in the same places. Given an arbitrary ordering with M U's and N R's, how many U-equivalent orderings are there? Consider only the positions of the U in the ordering. An equivalent pattern has one of the M U's in the first U position, one of the M-1 remaining U's in the second U position, and so on and so forth. Hence, M! orderings are equivalent to the ordering (including the original ordering). We've overcounted by M!.

At this point, we have computed that there are (M+N)!/M! different orderings, assuming that all the U's are equivalent and all the R's are different.

But the R's are not different. They're also all the same. Hence, we've still overcounted by N! (using a similar analysis to above).

How long does this take to compute? If we compute factorials the ``natural'' way (doing all the multiplications) it takes O(M+N) steps to compute (M+N)!, O(M) steps to compute M!, O(N) steps to compute N!, and O(1) steps to do the extra multiplication and division. Hence, this is an O(M+N) algorithm, which is significantly better than O(M*N).

Why would I prefer the original algorithm? It's more adaptable to variations in the problem (e.g., if you can only go right or up from certain squares).

C. Binary Search in Unsorted Lists

Carl and Carla have become so enamored of divide-and-conquer that they use it for almost every algorithm they write. Last week, they needed to write a search method for unsorted lists, and decided to use divide-and-conquer. Of course, since they don't know which half to look in if the object is not in the middle, they search in both halves. Here's their code (yes, they still need to work on their commenting).

import Comparator;

/**
 * Utilities for searching in arrays.
 *
 * @author Carl Caffeinated
 * @author Carla Caffeinated
 */
public class Searcher {
  /** 
   * Determine if a value is in the array.
   */
  public static boolean search(Object lookForMe, 
                               Object[] lookHere, 
                               Comparator compare)
    throws IncomparableException
  {
    return search(lookForMe, lookHere, 0, lookHere.length-1, compare);
  } // search(Object, Object[])
  
  /**
   * Determine if a value is in a subarray.
   */
  protected boolean search(Object lookForMe, 
                           Object[] lookHere, 
                           int lb, int ub,
                           Comparator compare) 
    throws IncomparableException
  {
    // Is the subarray empty?  If so, the object can't be there.
    if (ub < lb) return false;
    // Otherwise, it must be in the middle, left half, or right half.
    int mid = (lb + ub) / 2;
    return ( compare.equals(lookForMe, lookHere[mid]) ||
             search(lookForMe, lookHere, lb, mid-1, compare) ||
             search(lookForMe, lookHere, mid+1, ub, compare) );
  } // search(Object, Object[], int, int)
} // class Searcher

Unfortunately, Carla and Carl have realized that they just don't understand running time analysis and ask for your help.

C.1. Recurrence Relation

Write the recurrence relation for f(n), where f(n) gives the running time for their method on input of length n.

A Solution

f(1) = 1
f(n) = c      // For the various constant-time stuff
     + f(n/2) // For searching the first half
     + f(n/2) // For searching the second half

C.2. Running Time

A Solution

f(n) = c + 2*f(n/2)            // Original rule
     = c + 2*(c + 2*f(n/4))    // Expanded f(n/2)
     = c + 2*c + 2*2*f(n/4)    // Distributed
     = 3*c + 4*f(n/4)          // Simplified
     = 3*c + 4*(c + 2*f(n/8))  // Expanded f(n/4)
     = 3*c + 4*c + 4*2*f(n/8)  // Distributed
     = 7*c + 8*f(n/8)          // Simplified
     = 7*c + 8*(c + 2*f(n/16)) // Expanded f(n/8)
     = 7*c + 8*c + 8*2*f(n/16) // Distributed
     = 15*c + 16*f(n/16)       // Simplified

f(n) = c*(2^k-1) + 2^k*f(n/2^k)

f(n) = c*(n-1) + n*f(1)

[Instructions] [Search] [Current] [News] [Syllabus] [Glance] [Links] [Handouts] [Project] [Outlines] [Labs] [Assignments] [Quizzes] [Exams] [Examples] [EIJ] [JPDS] [Tutorial] [API]

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.

This page may be found at http://www.math.grin.edu/~rebelsky/Courses/CS152/2000S/Exams/examsoln.02.html

Source text last modified Mon Apr 3 09:30:53 2000.

This page generated on Mon Apr 3 09:30:57 2000 by Siteweaver. Validate this page's HTML.

Contact our webmaster at rebelsky@grinnell.edu