CSC-152 2000S : Exam 2: Algorithms

Distributed: Wednesday, March 8, 2000
Due: 11 a.m., Friday, March 17, 2000
No extensions!

There are 3 problems on the exam. They are not all worth the same number of points. The point value of a question does not necessarily reflect its complexity or length.

This examination is open book, open notes, open mind, open computer, open Web. You may use all reasonable resources. You may not use other people as resources. As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately.

This is a take-home examination. It is likely to take you about ten hours. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date. No late exams will be accepted. I may make a solution key available after the exam.

Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say ``This is definitely the hardest exam I have ever taken.'' You may also summarize these policies.

Answer all of your questions electronically. That is, you must write all of your answers on the computer and print them out. You should also email me a copy of your exam (a plain text file, please). Put your answers in the same order that the problems appear in.

I will give partial credit for partially correct answers. You ensure the best possible grade for yourself by highlighting your answer and including a clear set of work that you used to derive the answer. In any case, if you include a note about the amount of time spent on each problem or subproblem, I will give you five points of extra credit.

I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the problem you have observed and attempt to reword the question in such a way that it is answerable. If it's a reasonable hour (before 10 p.m. and after 8 a.m.), feel free to try to call me in the office (269-4410) or at home (236-7445).

Some of the questions use or require Java code. You are not required to write working code for this exam (although I'd recommend that you try).

I will also reserve time at the start of classes next week to discuss any general questions you have on the exam.

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.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.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.4. Checking the Algorithm

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

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.

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.

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.

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.

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.

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.

C.2. Running Time

[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/exam.02.html

Source text last modified Tue Mar 7 16:30:27 2000.

This page generated on Tue Mar 7 16:27:34 2000 by Siteweaver. Validate this page's HTML.

Contact our webmaster at rebelsky@grinnell.edu

Exam 2: Algorithms

Policies