Exam 1: Object-Oriented Design, ADTs, and Algorithms

This is a take-home examination. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date.

There are five problems on this examination. You must do your best to answer all of them. The problems are not necessarily of equal difficulty. Problems may include subproblems. If you complete five problems correctly or mostly correctly, you will earn an A. If you complete four problems correctly or mostly correctly, you will earn a B. If you complete three problems correctly or mostly correctly, you will earn a C. If you complete two problems correctly or mostly correctly, you will earn a D. If you complete fewer than two problems correctly or mostly correctly, you will earn an F. If you do not attempt the examination, you will earn a 0. Partially correct solutions may or may not earn you a partial grade, depending on the discretion of the grader.

I rarely give makeup problems because my experience in past semesters is that students spend a lot of effort on such problems but do not significantly improve their grade.

Read the entire examination before you begin.

I expect that someone who has mastered the material and works at a moderate rate should have little trouble completing the exam in a reasonable amount of time. In particular, this exam is likely to take you about six hours, depending on how well you've learned the topics and how fast you work. (When I do the problems, I will report how long each one took me.)

This examination has a required prologue that must be completed by the Sunday evening before the exam is due. (Ideally, you would complete it by Friday evening.) The prologue is intended to help you get started thinking about the examination.

This examination has an epilogue that must be completed by the evening after the exam is due. The epilogue is intended to help you reflect carefully on the examination. The epilogue is required. Failure to fill in the epilogue will incur a penalty of five points on the exam.

This examination is open book, open notes, open mind, open computer, and open Web. However, it is closed person. That means you should not talk to other people about the exam. Other than as restricted by that limitation, you should feel free to use all reasonable resources available to you.

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. If you use code that you wrote for a previous lab or homework, cite that lab or homework and the other members of your group. If you use code that you found on the course Web site, be sure to cite that code. You need not cite the code provided in the body of the examination.

Although you may use the Web for this exam, you may not post your answers to this examination on the Web. (You certainly should not post them to GitHub unless you create a private repository for your exam.) And, in case it's not clear, you may not ask others (in person, via email, via IM, via IRC, by posting a “please help” message, or in any other way) to put answers on the Web.

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 will have no chance of finishing the exam.” You may also summarize these policies. You may not tell other students which problems you've finished. You may not tell other students how long you've spent on the exam.

You must include both of the following statements on the cover sheet of the examination.

Please sign and date each statement. Note that the statements must be true; if you are unable to sign either statement, please talk to me at your earliest convenience. You need not reveal the particulars of the dishonesty, simply that it happened. Note also that inappropriate assistance is assistance from (or to) anyone other than Professor Rebelsky (that's me).

You must present your exam to me in two forms, physically and electronically. If you fail to turn in both versions, you are unlikely to receive credit for the examination.

Physical copy: You must write all of your answers using the computer, print them out, number the pages; put your name on the top of every page, write, sign, and date each of the academic honesty statements (provided you are able to do so); and hand me the printed copy or put it under my office door. If you fail to name and number the printed pages, you may suffer a penalty. If you fail to turn in a legible version of the exam, you are also likely to suffer some sort of penalty.

Electronic copy: You must also submit an electronic copy of your exam. You should create the electronic version by making a tarball of any relevant code and emailing me the tarball. Here are the steps for making a tarball.

Code: In many problems, I ask you to write code. Unless I specify otherwise in a problem, you should write working code and include examples that show that you've tested the code. You should do your best to format that code to the class formatting standards.

Documentation: You should document classes, interfaces, fields, and methods using Javadoc-style comments. You should specify preconditions and postconditions for each method.

Care: Just as you should be careful and precise when you write code and documentation, so should you be careful and precise when you write prose. Please check your spelling and grammar. Since I should be equally careful, the whole class will receive one point of extra credit for each error in spelling or grammar you identify on this exam. I will limit that form of extra credit to five points.

Partial Credit: I may give partial credit for partially correct answers. I am best able to give such partial credit if you include a clear set of work that shows how you derived your answer. You ensure the best possible grade for yourself by clearly indicating what part of your answer is work and what part is your final 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 issue you have observed and attempt to reword the question in such a way that it is answerable. You should also feel free to send me electronic mail at any time of day.

I will also reserve time at the start of each class before the exam is due to discuss any general questions you have on the exam.

Your classmate, Ava Ridge, was intrigued by the recent discussion of problem 2 from homework two and has decided to write the following function so that it works for all long inputs.

/**
 * Ava's amazing math utilities.
 */
public class MathUtils
{
  /**
   * Compute the average of all the values in vals. Rounds toward
   * zero if the average is not a whole number.
   *
   * @throws Exception
   *   if the array is empty, because there is no average value
   *   in an empty set.
   */
  public static long average(long[] vals)
    throws Exception
  {
    ...;
  } // average(long[])
} // class MathUtils

Your class mentors, Tessa Ter and Jun It, think we should help Ava make sure that her code is correct. They have therefore asked you to write an appropriate test suite for average.

Write that test suite. Your test suite should certainly include tests of “corner cases” - those outliers that many folks will miss. In addition, portions of your test suite must be systematically constructed. That is, you must use loops to build an appropriate variety of arrays of different sizes that are likely to stress the system.

If at all possible, make sure that your test suite indicates the input for which average fails (assuming that it finds an input for which average fails).

I am likely to run your test suite against a variety of implementations of average, some of which are correct and some of which are incorrect. You will get no credit for this problem if you identify a correct average method as incorrect. You will get partial credit if you miss errors in erroneous implementations. You will get extra credit if you find an error in an implementation that I believe is correct.

Note that you do not need to check whether or not average correctly throws an exception when given null or an empty array as input. Your primary goal is to check that the average method correctly computes the average when given good inputs.

Unfortunately, the combined class unit tests have shown that Ava's implementation of average is far from correct. (Actually, it's probably fortunate that the tests have shown her method incorrect. She would likely hit unexpected errors in the future if she were relying on incorrect code.)

Ava can't figure out how to write average. Your professor, Hugh DeWitt, has therefore decided to make everyone in the class attempt their own implementation.

Implement average. Your method should take an array of long values as input and return a long that represents the average of those values. Note that you may not convert the values to BigInteger or BigDecimal values.

Your colleagues, Cher and Ray, feel that Java's StringBuffer class hides too many of the details. “After all,” they say, “we don't really know how efficient any of the operations are.” They suggest we design and implement our own mutable string class, which they call MutableString. They suggest the following methods, which they've put in an interface.

/**
 * Mutable strings.  
 *
 * @author Cher
 * @author Ray
 * @author Your Name Here
 */
public interface MutableString
  extends CharSequence
{
  /**
   * Append str to the end of the string.
   */
  public void append(String str);

  /**
   * Insert str immediately before the ith character of
   * the current string.
   *
   * @pre
   *   0 <= i < this.length()
   */
  public void prepend(int i, String str);

  /**
   * Remove the characters starting at start and finishing 
   * immediately before end.
   */
  public void remove(int start, int end);

  /**
   * Replace all copies of pattern with replacement.
   */
  public void replace(String pattern, String replacement);
} // class MutableString

They have also started a basic implementation.

/**
 * A basic implementation of mutable strings.  An alternative to string 
 * buffers when you want something like a string that you can change.
 *
 * @author Cher
 * @author Ray
 * @author Your Name Here
 */
public class BasicMutableString
  implements MutableString
{
  // +-------+-------------------------------------------------------------
  // | Notes |
  // +-------+

/*
  We store strings in arrays of characters.  When we need to expand
  the array, we double the size of the array.  That suggests we never
  use more than twice as much is necessary (well, except when we then
  delete characters), but keeps running time relatively good.
 */

  // +-----------+---------------------------------------------------------
  // | Constants |
  // +-----------+

  /**
   * The default capacity of a mutable string.
   */
  static final int DEFAULT_CAPACITY = 16;

  // +--------+------------------------------------------------------------
  // | Fields |
  // +--------+

  /**
   * The contents of the string.  May include extra capacity to make
   * it simpler to expand the string.
   */
  char contents[];

  /**
   * The actual size of the string.
   */
  int size;

  // +--------------+------------------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Create an empty mutable string.
   */
  public BasicMutableString()
  {
    this.contents = new char[DEFAULT_CAPACITY];
    this.size = 0;
  } // BasicMutableString()

  /**
   * Create a mutable string, initialized to str.
   */
  public BasicMutableString(String str)
  {
    this.size = str.length();
    this.contents = new char[computeNeededCapacity(this.size)];
    for (int i = 0; i < size; i++)
      this.contents[i] = str.charAt(i);
  } // BasicMutableString(String)

  // +---------+-----------------------------------------------------------
  // | Helpers |
  // +---------+

  /**
   * Compute the first reasonable capacity larger than mincap.
   */
  int computeNeededCapacity(int mincap)
  {
    // Start at either the default or current capacity
    int capacity = DEFAULT_CAPACITY;
    if (this.contents != null)
      capacity = this.contents.length;

    // Keep increasing until we are large enoug
    while (capacity < mincap)
      {
        capacity *= 2;
      } // while
    
    // And we're done
    return capacity;
  } // computeNeededCapacity(int)

  // +-------------------------+-------------------------------------------
  // | Standard Object Methods |
  // +-------------------------+

  /**
   * Determine if we are the same as another object.
   */
  public boolean equals(Object other)
  {
    return (other instanceof BasicMutableString) && 
        equals((BasicMutableString) other);
  } // equals(Object)

  /**
   * Convert to a string.
   */
  public String toString()
  {
    return new String(this.contents, 0, this.size);
  } // toString()

  // +-----------+---------------------------------------------------------
  // | Observers |
  // +-----------+

  /**
   * Get the ith character of this string.
   *
   * @pre 0 <= i < this.length()
   */
  public char charAt(int i)
  {
    return this.contents[i];
  } // charAt(int)

  /**
   * Determine if we are the same as another mutable string.
   */
  public boolean equals(BasicMutableString other)
  {
    return this.toString().equals(other.toString());
  } // equals(MutableString)

  /**
   * Get the length of this mutable string.
   */
  public int length()
  {
    return this.size;
  } // length()

  /**
   * Get a new <code>CharSequence</code> that is a subsequence
   * of this sequence.
   */
  public CharSequence subSequence(int start, int end)
  {
    // Inefficient, but usable
    return new BasicMutableString(new String(this.contents, start, end));
  } // toString()

  // +----------+----------------------------------------------------------
  // | Mutators |
  // +----------+

  /**
   * Append str to the end of the string.
   */
  public void append(String str)
  {
    int newsize = this.size + str.length();

    // If there's insufficient capacity, make a new array
    if (newsize >= this.contents.length)
      {
        char[] oldcontents = this.contents;
        this.contents = new char[computeNeededCapacity(newsize)];
        for (int i = 0; i < this.size; i++)
          this.contents[i] = oldcontents[i];
      } // if

    // Copy the characters.
    for (int i = this.size; i < newsize; i++)
      this.contents[i] = str.charAt(i - this.size);

    // Update the size
    this.size = newsize;
  } // append(String)

  /**
   * Insert str immediately before the ith character of
   * the current string.
   *
   * @pre
   *   0 <= i < this.length()
   */
  public void prepend(int i, String str)
  {
    int len = str.length();
    int newsize = this.size + len;

    // If there's insufficient capacity, make a new array,
    // leaving space for the string to be prepended.
    if (newsize >= this.contents.length)
      {
        char[] oldcontents = this.contents;
        this.contents = new char[computeNeededCapacity(newsize)];
        for (int j = 0; j < i; j++)
          this.contents[j] = oldcontents[j];
        for (int j = i; j < this.size; j++)
          this.contents[j + len] = oldcontents[j];
      } // if there's insufficient space

    // Otherwise, there's sufficient capacity, but we need to
    // make a space in the array.
    else
      {
        for (int j = this.size-1; j >= i; j--)
          this.contents[j + len] = this.contents[j];
      } // else

    // There's space.  Put things in
    for (int j = 0; j < len; j++)
      this.contents[i+j] = str.charAt(j);

    // And that's it
    this.size = newsize;
  } // prepend(String)

  /**
   * Remove the characters starting at start and finishing 
   * immediately before end.
   */
  public void remove(int start, int end)
  {
    int offset = end - start;
    for (int i = end; i < this.size; i++)
      this.contents[i - offset] = this.contents[i];
    this.size -= offset;
  } // remove(int, int)

  /**
   * Replace all copies of pattern with replacement.
   */
  public void replace(String pattern, String replacement)
  {
    // STUB
  } // replace(String, String)
} // class BasicMutableString

Implement the replace method.

Your algorithm should be in O((p+r)*n), where n is the length of the string before replacement, p is the length of the pattern string, and r is the length of the replacement string. (Yes, this is really O(n), particularly if we assume that p and r are fixed.)

Since remove may require O(n) steps, you cannot implement replace using remove.

You may not use StringBuffer, StringBuilder, or anything similar in implementing your replace method. You certainly may not use any of the string methods for replacing characters and such because you don't know their efficiency.

Sorting is a relatively complex and expensive process. Your classmates Sue and Doug (whose name is pronounced as if it had a terminal h, because he bakes so much) suggest a somewhat simpler task. Given a value, val, an array of values, values, and a comparator, rearrange the array so that all the values less than val come first, followed by all of the values equal to val, followed by all of the values greater than val.

Here's the signature that they have developed for that method.

/**
 * Rearrange values into three parts: less than val, equal to val, and
 * greater than val.
 *
 * @return boundaries
 *   an array of two integers. boundaries[0] contains the index of the
 *   first value greater than or equal to val, if such a value exists,
 *   or values.length, if there is no such value.  boundaries[1] contains
 *   the index of the first value strictly greater than val, if such a
 *   value exists, or values.length, if there is no such value.
 * @post
 *   No values have been added to values or removed from values.
 * @post
 *   All elements with index less than boundaries[0] are smaller than
 *   val.  All elements with index greater than or equal to boundaries[0] 
 *   and less than boundaries[1] are equal to val.  All elements with
 *   index greater than or equal to boundaries[1] are larger than val.
 */
public static <T> int[] pseudoSort(T val, T[] values,
     Comparator<? super T> order)

Of course, they are better at writing signatures than at implementing their designs. And, to your chagrin, your professor, Hugh DeWitt, overhears their design and thinks that you'd be just the person to finish their work.

Implement pseudoSort. Your algorithm should be O(n). You may only use a constant amount of additional space. (For example, you may not make additional arrays of the same size.)

Your classmate, Lupe N Varian, notes that to achieve the desired running time, it will be necessary to write a carefully constructed loop. Lupe proposes the following two loop invariants. You may choose which you think is more helpful.

Invariant 1

+-------+-------+-------+-------+
| < val | = val | > val | ????? |
+-------+-------+-------+-------+
|       |       |       |       |
0       s       e       b       length

For all i, 0 <= i < s, order.compare(val, values[i]) > 0.
For all i, s <= i < e, order.compare(val, values[i]) == 0.
For all i, e <= i < b, order.compare(val, values[i]) <  0.

Invariant 2
+-------+-------+-------+-------+
| < val | = val | ????? | > val |
+-------+-------+-------+-------+
|       |       |       |       |
0       s       e       b       length

For all i, 0 <= i < s, order.compare(val, values[i]) > 0.
For all i, s <= i < e, order.compare(val, values[i]) == 0.
For all i, b <= i < values.length, order.compare(val, values[i]) < 0.

Hint: Look at the first value in the unknown section, swap it as appropriate, and update the bounds of the invariant.

Your colleagues, Conrad (Con, for short) and Joy N. enjoy working with predicates and think it would be useful to build some new procedures that create predicates. They've come up with the following interface as a starting point.

import java.util.function.Predicate;

/**
 * Things that make new predicates.
 *
 * @author Con
 * @author Joy N.
 */
public interface PredicateMaker<T>
{
  /**
   * Create a new predicate that holds only when all of the values
   * in preds hold.
   */
  public Predicate<T> and(Predicate<T>[] preds);
} // interface PredicateMaker<T>

Your colleagues Ann, Nina, and Mustafa (Mus, for short) suggest two possible approaches: You can use anonymous inner classes and you can use lambda expressions. They provide the following stub classes.

import java.util.function.Predicate;

/**
 * Things that make new predicates using anonymous inner classes.
 *
 * @author Ann
 * @author Nina
 * @author Mus
 */
public class PredicateMakerAIC<T>
  implements PredicateMaker<T>
{
  /**
   * Create a new predicate that holds only when all of the values
   * in preds hold.
   */
  public Predicate<T> and(Predicate<T>[] preds)
  {
    return new Predicate<T>() {
      public boolean test(T val)
      {
        // STUB
        return true;
      } // test(T)
    }; // new Predicate<T>
  } // and(Predicate<T>[])
} // class PredicateMakerAIC<T>

import java.util.function.Predicate;

/**
 * Things that make new predicates using lambda expressions.
 *
 * @author Ann
 * @author Nina
 * @author Mus
 */
public class PredicateMakerLambda<T>
  implements PredicateMaker<T>
{
  /**
   * Create a new predicate that holds only when all of the values
   * in preds hold.
   */
  public Predicate<T> and(Predicate<T>[] preds)
  {
    // STUB!
    return (val) -> { return true; };
  } // and(Predicate<T>[])
} // class PredicateMakerLambda<T>

Your other colleagues, Mike, Rosa, and Phit, find anonymous classes and functions too confusing and want to see a solution that uses neither of those techniques. They've provided you with even less than Ann, Nina, and Mus.

import java.util.function.Predicate;

/**
 * Things that make new predicates without using confusing things
 * like lambdas and anonymous inner classes.
 *
 * @author Mike
 * @author Rosa
 * @author Phit
 */
public class PredicateMakerAlt<T>
  implements PredicateMaker<T>
{
  /**
   * Create a new predicate that holds only when all of the values
   * in preds hold.
   */
  public Predicate<T> and(Predicate<T>[] preds)
  {
    // STUB
    return null;
  } // and(Predicate<T>[])
} // class PredicateMakerAlt<T>

Finish all three classes.

The accompanying unit tests provide some example predicates as well as an example of how to use predicates.

What should the procedure do if the average is not a whole number?

What do you mean by this sentence? “I am likely to run your test suite against a variety of implementations of average, some of which are correct and some of which are incorrect. ”

In what instance would I identify a correct average method as incorrect?

In what instance where I would miss errors in an erroneous implementation?

Should I be able to compute the average of an empty array?

Should I be able to compute the average of a singleton array?

Why does my average method not work?

Are we assured that all of the values in the array are less than or equal to Long.MAX_VALUE and greater than or equal to Long.MIN_VALUE?

What should I do if the input array is empty?

Can I use BigInteger or BigDecimals in my solution?

The problem statement should answer this question definitively. (And no, I have not updated the problem statement to address this question.)

Can I use StringBuilder?

Can I use any string methods?

How much space can I use?

Suppose k is the length of the pattern and n is the length of the original string. Can my algorithm be O(n*k)?

Didn't this problem used to say something like “in O(n+m), where n is the length of the original mutable string and m is the length of the result”?

Can I assume that the pattern and replacement are the same size?

It appears that this problem involves loop invariants. If I wasn't in class when you covered loop invarants, should I do the reading and lab on loop invariants?

Can you give us a picture of the postconditions?

How about the special cases mentioned in the postconditions?

Can we put a loop in the body of a lambda expression?

Can you explain again what and is supposed to return?

In the example of pm.and(newPredicate[ ] { isEven, isMultipleOf3 }), how do isEven and isMultipleOf3 access the individual values in the array of integers?