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.

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 five hours, depending on how well you've learned the topics and how fast you work.

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. That is, 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, and hand me the printed 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. (If you don't know how to make a tarball, let me know.) If you fail to name and number the printed pages, you may suffer a penalty. If you fail to turn in both versions, you may suffer a much worse penalty. If you fail to turn in a legible version of the exam, you are also likely to suffer some sort of penalty.

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 Sun/Oracle Java coding standards.

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

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.

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.

Topics: Polymorphic Data Types, Generics, Predicates, Strings.

Gentle Eric and Poly Em Orphic have been thinking about the reading on searching arrays and want to set up a set of classes to help with writing predicates.

They've started by writing an interface.

/**
 * A predicate.  That is, a procedure that can be applied to values and
 * that returns true or false.
 */
public interface Predicate<T> {
    /**
     * Test to see if val meets the predicate.
     */
    public boolean test(T val);
} // interface Predicate<T>

They've even written a few simple predicates for integers.

/**
 * Determine if an integer is even.
 */
public class IsEven implements Predicate<Integer> {
    @Override
    public boolean test(Integer val) {
         return (val.intValue() % 2) == 0;
    } // test
} // class IsEven

/**
 * Determine if an integer is greater than some specified value.
 */
public class GreaterThan implements Predicate<Integer> {
    /**
     * The cutoff that we want to be greater than.
     */
    int cutoff;

    /**
     * Build a new predicate that tests if its parameter is greater
     * than cutoff.
     */
    public GreaterThan(int cutoff) {
        this.cutoff = cutoff;
    } // GreaterThan

    /**
     * Determine if val is greater than cutoff.
     */
    @Override
    public boolean test(Integer val) {
        return val.intValue() > cutoff;
    } // test(Integer)
} // class GreaterThan

And they've even come up with a quick experiment to demonstrate to others how one might use these predicates.

import java.io.PrintWriter;

/**
 * A quick experiment to demonstrate predicates over integers.
 */
public class IPExpt {
    /**
     * Print out all of the values in values for which pred holds.
     */
    public static <T> void printMatching(PrintWriter pen, T[] values, 
            Predicate<T> pred) {
        for (int i = 0; i < values.length; i++) {
            if (pred.test(values[i])) {
                pen.print(values[i]);
                pen.print(" ");
            } // if
        } // for
    } // printMatching

    /**
     * Given an array of integers, print out some matching ones.
     */
    public static void main(String[] args) {
        PrintWriter pen = new PrintWriter(System.out, true);
        Integer[] values = { 3, 1, 4, 1, 5, 9, 2, 6, 8, 3, 8 };

        pen.print("Even: ");
        printMatching(pen, values, new IsEven());
        pen.println();

        pen.print("> 5:  ");
        printMatching(pen, values, new GreaterThan(5));
        pen.println();

        pen.print("> 2:  ");
        printMatching(pen, values, new GreaterThan(2));
        pen.println();

        pen.flush();
    } // main(String[])
} // class IPExpt

a. Gen. Eric would like to be able to write some predicates that involve strings. Create a class, Lowercase, that implements the predicate interface for strings and provides a test method that takes a string as input and determines whether or not the string consists only of lowercase letters.

b. Create a class, StringContains, that allows you to construct predicates that determine whether or not a string contains a certain string. For example, one might build the following predicate if they want to look for strings that contain the word sub.

Predicate<String> peri = new StringContains("sub");

c. Ms. Morphic would like to be able to combine the various predicates in the normal ways. Design and implement three classes, Both, Either, and Negate, that allow you to build new predicates from old. For example, we might use these, along with their prior predicates, to write a predicate that can test whether a number is greater than 0 and less than or equal to 100.

Predicate<Integer> scope = new Both(new GreaterThan(0),
          new Negate(new GreaterThan(100)));

Topics: Loop invariants, Unit testing, Functional design

As you may recall, the Dutch national flag problem is a famous problem in arranging data. You have an array of three different kinds of values and your goal is to rearrange the values in the array so that you have all the values of one kind at the front, all the values of the second kind in the middle, and all the copies of the third kind at the end.

When done right, a solution to the Dutch national flag problem only requires iterating through the array once.

Let's model that problem using an array of strings and some test procedures.

public class DNF {
    /**
     * Determine if s is a string that names the color blue.
     */
    public static boolean isBlue(String s) {
        s = s.toLowerCase();
        return s.equals("blue")
                || s.equals("azul")
                || s.equals("bleu")
                || s.equals("blau")
                || s.equals("0x0000ff");
    } // isBlue(String)
    
    /**
     * Determine if s is a string that names the color red.
     */
    public static boolean isRed(String s) {
        s = s.toLowerCase();
        return s.equals("red")
                || s.equals("roja")
                || s.equals("rogue")
                || s.equals("rot")
                || s.equals("0xff0000");
    } // isRed(String)
    
    /**
     * Determine if s is a string that names the color white.
     */
    public static boolean isWhite(String s) {
        s = s.toLowerCase();
        return s.equals("white")
                || s.equals("blanca") 
                || s.equals("blanco")
                || s.equals("blanc")
                || s.equals("blanche")
                || s.equals("weiss")
                || s.equals("0xffffff");
    } // isWhite(String)
    
    /**
     * Rearrange the values in flag so that they meet the Dutch National
     * Criteria.
     *
     * @pre
     *   Suppose A is an array.
     *   A.size == flag.size
     *   For all 0 <= i < A.size
     *      A[i] == flag[i]
     *   For all 0 <= i < flag.size
     *      isRed(flag[i]) || isWhite(flag[i]) || isBlue(flag[i])
     * @post
     *   flag is a permutation of A
     *   For all 0 <= i < j < flag.size
     *       If isWhite(flag[i]) then isWhite(flag[j]) || isBlue(flag[j])
     *       If isBlue(flag[i]) then isBlue(flag[j])
     */
    public static void dnf(String[] flag)  {
        // STUB
    } // dnf(String[])
} // class DNF

Tessa Ter and June It know that I implemented dnf so that I could better help you with a recent assignment. But they have little faith in my ability to write dnf correctly. Write a set of unit tests that will identify one or more cases in which my dnf fails. (No, you don't get my code. Your goal is to write tests that are comprehensive enough that they'll catch my error. But I also won't look at your tests before writing my code. I expect that I'll write five or so not-quite correct procedures; your goal is to catch at least four of them.)

Topics: Loop invariants, problem solving.

Bea and Joe are running a coffee roasting company. One of the special things about their coffee is that they use two colors of beans, light (smooth and mild) and dark (really caffeinated). Consultants have suggested that the adopt a legendary method of assessing the quality of their beans, a method people call “greasing”. It goes something like this.

They suspect that this advice, like most consultants' advice, takes a simple decision and makes it much too complicated. They've hired you to do a bit more analysis.

a. Write a short argument that this loop terminates.

b. Write a good loop invariant for this loop. You may find it useful to express the loop invariant in terms of the original numbers of light and dark beans.

c. Using the loop invariant and the termination condition, determine what color the final bean will be as a function of the numbers of light and dark beans in the original sample.

Topics: Arrays, ADT Implementation, Vectors

Tara and Vic are a bit troubled by Java's structures that provide indexed access to values. They like that they know what the underlying implementation of arrays. However, they don't like that arrays are not expandable. On the other hand, while they like that vectors are expandable, they don't like that the underlying implementation is hidden from them.

And so, they've started to implement their own versions of expandable arrays, which they name using their initials.

/**
 * Expandable arrays of objects.
 */
public class VT {
    /**
     * All the values in our array.
     */
    Object[] values;

    /**
     * Create a new array.
     */
    public VT() {
        // We start arrays at size 16 because that seems like a
        // good default size.
        values = new Object[16];
    } // VT

    /**
     * Set the ith element of the array to val.
     *
     * @param i
     *   A nonnegative integer.
     * @param val
     *   An object
     * @pre
     *   i >= 0
     * @post
     *   get(i) == val
     * @throws Exception
     *   when i < 0
     * @throws Exception
     *   when the array has to expand and no memory is left
     */
    public void set(int i, Object val) throws Exception {
        // If values is not big enough, expand it
        //   STUB
        // Then put the value in
        values[i] = val;
    } // set(int, Object)

    /**
     * Get the ith element of the array.
     *
     * @param i
     *   A nonnegative integer
     * @return ith
     *   An element of the array.
     * @pre 
     *   i >= 0
     *   The client has not mutated values, except with set.
     * @post
     *   ith is the last value given by set(i,val).  If set(i,val)
     *   has never been called, returns null.
     * @throws Exception
     *   If i < 0.
     */
    public Object get(int i) throws Exception {
        // STUB
        return null;
    } // get(int)

} // class VT

Finish implementing this class.

Note: I hope to set up a repository into which you can place unit tests, so that the tests one student writes can easily be used by other students.

Topics: Invariants, Comparators, Strings

Theodore has recently been knighted and, as is the custom, has added a suffix to his name in honor of one of the most respected monarchs of the United Kingdom of Great Britain and Ireland. To further commemorate his knighthood, he has decided to design a data structure which he humbly names after himself. Because he has been studying loop invariants, he's decided to create an ADT invariant. He begins his code as follows.

import java.util.Comparator;

/**
 * Sorted, indexed, fixed-sized, homogeneous collections of strings.
 */
public class SirTedVictoria {

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

    /**
     * The underlying collection of values.
     */
    String[] values;

    /**
     * The comparator used to order the values.
     */
    Comparator<String> order;

    /**
     * The number of values stored in the vector.
     */
    int size;


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

    /**
     * Create a new Sorted Vector with the specified capacity.
     * 
     * @pre
     *   capacity > 0
     *   order can be applied to any two strings.
     * @invariant
     *   For all i, 0 <= i < j < size
     *     order.compare(this.get(i), this.get(j)) <= 0
     */
    public SirTedVictoria(int capacity, Comparator<String> order) {
        this.values = new String[capacity];
        this.size = 0;
        this.order = order;
    } // SirTedVictoria(int,Comparator)

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

    /**
     * Add a value.
     *
     * @pre
     *   this.size() < this.capacity()
     * @post
     *   size increases by 1
     *   Exists an i s.t., this.get(i) == val
     *   For all j, 0 < j < i,
     *     order.compare(this.get(j), this.get(i)) <= 0
     *   For all j, i < j < size()
     *     order.compare(this.get(i), this.get(j)) <= 0
     *   The number of values in the vector equal to value has
     *     increased by one.
     */
    public void add(String val) throws Exception {
        // STUB
    } // add

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

    /**
     * Get a value.
     *
     * @return val
     *   The value at index i
     * @pre
     *   i < this.size() 
     * @post
     *   For all j, 0 < j < i,
     *     order.compare(this.get(j), val) <= 0
     *   For all j, i < j < size()
     *     order.compare(val, this.get(j)) <= 0
     */
    public String get(int i) throws Exception {
        // STUB
        return null;
    } // get

    /**
     * Get the size of the vector - the number of values stored.
     */
    public int size() {
        return this.size;
    } // size()

    /**
     * Get the capacity of the vector - the number of values that
     * can be stored.
     */
    public int capacity() {
        return this.values.length;
    } // capacity()
} // class SirTedVictoria

Finish implementing this class.