Exam 2: Algorithms

Distributed: Friday, October 13, 2000
Due: 9 a.m., Friday, October 27, 2000
No extensions!

This page may be found online at http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2000F/Exams/exam.02.html.

Code files:

You may want to use the online version of the exam to gain access to these files.

• Array.java (Note that this class is not the same as the standard Java array class.)
• CompareComparable.java
• IncomparableException.java
• NotFoundException.java
• Searcher.java
• TestSearcher.java
• SimpleOutput.java

• Preliminaries
• Problems
  • A. Searching Arrays
    • 1. Building Your Own Comparators
    • 2. Binary Search and Subarrays
    • 3. Bugs in Binary Search
    • 4. Searching for Courses
    • 5. Testing Preconditions
  • B. Smallest and Largest Differences
    • 6. Running Time
    • 7. Improving Smallest Difference
    • 8. Improving Greatest Difference
  • C. Square Root
    • 9. Revised Algorithm
    • 10. Running time

Preliminaries

There are ten problems on the exam. Each problem is worth ten points.

For convenience, the questions are divided into sections. The point value associated with a problem does not necessarily correspond to the complexity of the problem or the time required to solve the problem. If you write down the amount of time you spend on each question, I'll give you three points of extra credit.

This examination is open book, open notes, open mind, open computer, open Web. Feel free to use all reasonable resources available to you except for other people and for exam and homework solutions. 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. Do not use exam or homework solutions you find on the Web.

This is a take-home examination. It is likely to take you about five to ten hours, depending on how well you've learned topics and how fast your work. 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.

You must include the following statement on the cover sheet of the examination. Plesae sign and date the statement. Note that the statement must be true; if you are unable to sign the statement, please talk to me at your earliest convenience.

I have neither given nor received help on this examination (other than from Sam Rebelsky). I am not aware of any other students who have given or received help on this examination (other than from Sam Rebelsky).

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 among the hardest exams I have ever taken. If you don't start it early, you'll have no chance of finishing the exam.'' You may also summarize these policies.

Answer all of your questions electronically and turn them in in hardcopy. 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. If you give an example of one of "Sam's easy to misinterpret scribbles" along with the actual meaning and the interpreted meaning, I'll give you three points of extra credit.

I will give partial credit for partially correct answers. You ensure the best possible grade for yourself by emphasizing your answer and including a clear set of work that you used to derive the answer.

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 yo u 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).

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

Problems

A. Searching Arrays

1. Building Your Own Comparators

Read the Java documentation on the Comparable and Comparator interfaces.

a. Design a simple Course class for information about a course. Minimally, this should contain number, title, and instructor. It should also have a toString method.

b. Write a Comparator that orders courses by title.

c. Write a Comparator that orders courses by instructor.

2. Binary Search and Subarrays

Your colleagues, Carla and Carl Caffeinated, have come up with the following implementation of binary search.

  public static Object binarySearch(Object value, Array stuff,
                                    Comparator order)
    throws IncomparableException, NotFoundException
  {
    // Determine the length of the array.
    int length = stuff.size();

    // If there's only one element in the array ...
    if (length == 1) {
      // See if it's what we're looking for.
      if (order.compare(value, stuff.get(0)) == 0) {
        // If so, return it.
        return stuff.get(0);
      }
      else {
        // If not, give up.
        throw new NotFoundException();
      }
    } // only one element in the array

    // If there are multiple elements in the array ...
    else {
      // Compare to the middle element.
      int comp = order.compare(value,stuff.get(length/2));
      // Equal: We're done.
      if (comp == 0) {
        return stuff.get(length/2);
      }
      // Value is smaller; Search the left half.
      else if (comp < 0) {
        return binarySearch(value, new Array(stuff, 1, length/2), order);
      }
      // Value is larger: Search the right half.
      else {
        return binarySearch(value, new Array(stuff,length/2,length-1), order);      }
    } // multiple elements in the array
  } // binarySearch(Object, Array, Comparator)

As you can tell, they need a new constructor for the Array class that builds a subarray of an existing array in constant time. Here's the sketch of that constructor.

  /**
   * Build a new subarray which holds the elements in positions
   * start .. finish of stuff.  Modifications to the subarray should
   * affect the original array and vice versa.
   */
  public Array(Array stuff, int start, int finish) {
    // STUB.  Write this.
  } // Array(stuff, start, finish)

Implement that constructor.

3. Bugs in Binary Search

Unfortunately, even if you implement that constructor correctly, binary search will not work correctly because Carl and Carl have failed to follow proper design for the procedure. For example, they haven't worried about special cases and they haven't ensured that every recursive call is on a smaller array (or have they?).

Repair their code.

You may find TestSearcher.java helpful for this portion of the exam.

4. Searching for Courses

Test binarySearch using courses, rather than integers. Preferably, you'll be able to take just the name of a class and search for the full class record.

5. Testing Preconditions

Now that you've done all the hard work, Carl and Carla decide to ``improve'' your code by adding a test for the precondition of binarySearch. The first lines of binarySearch are now

    // Test the precondition.
    if (!Searcher.inorder(stuff)) {
      throw new IncomparableException("Can't binary search unordered lists");
    }

When I look at their code, I scream. Why?

B. Smallest and Largest Differences

Carl and Carla have decided to try their hands at algorithm design. They've been thinking about things that might help a professor with grading. They decide that two useful algorithms will be to find the largest and smallest differences between grades in the class.

Here are their initial formulations.

To find the smallest difference between any two 
  different numbers in a collection ...
Set estimate to ``infinity''
For each value, v, in the collection
  For each value, u, not equal to v
    If |u-v| < estimate then
      Set estimate to |u-v|
Return estimate

To find the greatest difference between any two 
  different numbers in a collection ...
Set estimate to -1
For each value, v, in the collection
  For each value, u, not equal to v
    If |u-v| > estimate then
      Set estimate to |u-v|
Return estimate

6. Running Time

What is the running time of their algorithms? Use Big O notation.

7. Improving Smallest Difference

Theodore and Thelma Theoretician suggest that there should be an O(n*log₂n) algorithm for smallest difference. Come up with that algorithm.

8. Improving Greatest Difference

Theodore and Thelma Theoretician suggest that there should be an O(n) algorithm for greatest difference. Come up with that algorithm.

C. Square Root

Here's an iterative algorithm that finds the square root of a value to a specified accuracy.

/**
 * Compute the square root of val to accuracy 1/n.
 * Pre: (1) val >= 0
 *      (2) n > 0
 *      (3) The square root of val can be represented.
 * Post: (1) Returns a value v such that |v-sqrt(val)| < 1/n.
  */
public static double sqrt(double val, long n) {
  // Compute 1/nth of the range of possible values
  double accuracy = 1.0/((double) n);
  // Start with an initial guess
  double guess = 0;
  // Determine the difference between the square of the guess
  // and the actual square root.
  double diffsquared = val;

  // Step through all the possible values between 0 and val.
  for (double nextguess = 0.0;
       nextguess <= val;
       nextguess = nextguess + accuracy) {
    // Compute the difference between the square of the guess
    // and the actual value.
    double nextdiff = Math.abs(nextguess*nextguess-val);
    // If it's better, use it.
    if (nextdiff < diffsquared) {
      guess = nextguess;
      diffsquared = nextdiff;
    }
  } // for
} // sqrt(double,double)

As you might be able to tell, what this algorithm basically does is divide the interval between 0 and val into potential guesses that occur every 1/n units. It then tries each of these guesses and uses the best. Why 0 and val? Because we know that the square root of val is at least 0 and no more than val.

The running time of this algorithm is somewhat strange. It's based on both n and val. More or less, this algorithm is O(n*val).

9. Revised Algorithm

Make the algorithm more efficient by using a divide-and-conquer strategy. You need not write working Java code, although you will receive a modicum of extra credit for writing working code.

10. Running time

Determine the running time of the revised algorithm.