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 four 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 four problems correctly or mostly correctly, you will earn an A. If you complete three problems correctly or mostly correctly, you will earn a B. If you complete two problems correctly or mostly correctly, you will earn a C. If you complete one problem correctly or mostly correctly, you will earn a D. If you complete fewer than one problem 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.

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

This problem took SR 35 minutes, mostly because he wrote a strange and incorrect test.

Your classmate, Ava Ridge, was intrigued by the recent discussion of problem 2 from homework one 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 should be systematically constructed. That is, you should use loops to build an appropriate variety of arrays of different sizes.

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.

This problem took Sam fifteen minutes, including writing AverageExpt.java, which is now in the repo.

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. You may not convert the values to BigInteger or BigDecimal values.

This problem took SR 15 minutes, including adding a few more examples.

Your classmates, Slash and Becka, were a bit puzzled by the whole CSV thing. In particular, they are not sure about all of those \ characters. In response, you say

Otto Mayt, a more experienced student, wanders by and says “Of course, any decent programmer has already written a script that does the conversion by hand.”

You guessed it. Your professor, Hugh DeWitt, overheard and has decided that you get to write that script.

Write a method, stringify(infile, outfile) that reads the contents of infile and writes the corresponding C/Java string to outfile. Since you will probably read the input a line at a time, you may include a \n at the end of the string.

For example,

Hello

"Hello\n"

Hello
World

"Hello\nWorld\n"

Hello   World

"Hello\tWorld\n"

a,"a,b","\"

"a,\"a,b\",\"\\\"\n"

The only special characters you need to support are newline, tab, double-quotation mark, and backslash.

I've set up a simple test framework that you can feel free to extend.

SR took seven minutes for an inelegant solution and fifteen for a more elegant solution.

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 a stub class.

/**
 * 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 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 MutableString()
  {
    this.contents = new char[DEFAULT_CAPACITY];
    this.size = 0;
  } // MutableString()

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

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

  /**
   * Compute the first reaonable capacity larger than mincap.
   */
  public int computeCapacity(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;
  } // computeCapacity(int)

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

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

  /**
   * Convert to a string.
   */
  public String toString()
  {
    return new String(this.contents, 0, this.size);  // STUB
  } // 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(MutableString other)
  {
    return this.toString().equals(other.toString());
  } // equals(MutableString)

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

  // +----------+----------------------------------------------------------
  // | 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[computeCapacity(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[computeCapacity(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 MutableString

Finish implementing this class.

You may not use StringBuffer or StringBuilder in implementing MutableString. You must store the contents of the string as an array of characters.

What do you mean by a “test suite”?

Why did you provide a file called “AverageTest.java”?

What should we do if there's a fractional part to the average?

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?

Do we have to support all of the special characters, or just the ones you mention?

Can we treat a sequence of spaces as equivalent to the tab character?

Can I use StringBuilder?

Do we have to implement MutableString objects with an array of characters?