Algorithms and OOD (CSC 207 2013F) : Assignments

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

Assigned: Tuesday, 8 October 2013

Due: 10:30 p.m., Tuesday, 15 October 2013 (electronic); 10:00 a.m., Wednesday, 16 October 2013 (paper)


Exam Format

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.

Academic Honesty

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.

  1. I have neither received nor given inappropriate assistance on this examination.
  2. I am not aware of any other students who have given or received inappropriate assistance on this 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).

Presenting Your Work

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.

Getting Help

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.


Problem 1: Predicates

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


 * 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(" ");
            } // 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.print("> 5:  ");
        printMatching(pen, values, new GreaterThan(5));

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

    } // 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)));

Problem 2: The Dutch National Flag, Revisited

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

Problem 3: The Coffee Bean Problem

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.

Grab a sample of the beans and throw them in a can
While the can contains two or more beans
    Grab two beans
    If both are the same color, 
        Throw them away
        Add a new dark bean to the can
    If both are different colors, 
        Throw away the dark bean 
        Return the light bean to the can

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.


This problem is based on Jon Bentley's statement of David Gries's “Coffee Can Problem”.

Jon Bentley. 1983. Programming pearls: Writing correct programs. Commun. ACM 26, 12 (December 1983), 1040-1045. DOI=10.1145/358476.358484

David Gries. 1981. The Science of Programming. Springer-Verlag.

Problem 4: Expandable Arrays

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.

Problem 5: Sorted Arrays of Strings

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
     *, 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,
     *, this.get(i)) <= 0
     *   For all j, i < j < size()
     *, 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,
     *, val) <= 0
     *   For all j, i < j < size()
     *, 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.

Questions and Answers

Do you have any recommendations for getting started with problem 1?

I would suggest rereading the section on polymorphism and looking at the code for blocks. You might also find it easier to start with a slightly simpler problem, predicates over strings, and then generalize. For 1a, you should be able to model your code after the even predicate, since this predicate does not need to store information. For 1b, you should be able to model your code after the greater than predicate, since this predicate does need to store information. For 1c, you'll need to store information (other predicates), so thinking about the polymorphic data structures of blocks will be helpful.

Could you please give me sample code that uses predicates?


What will the class header for Both look like?

public class Both<T> implements Predicate<T>

The original code for problem 5 wouldn't compile.

Yeah. Sun screwed up the design of generics so that it's impossible to create a new array using a generic type. I've simplified the problem so that you only have to deal with sorted arrays of strings. (And just so you know, I caught this issue before any of you raised it.)

The naming conventions in this document are very strange.

Deal with it.

How can we guarantee the postconditions for VT.get if the client or subclass can mutate values.

Good question. I added another precondition to deal with it.

Can we ever match the hex colors, given that we've converted to lowercase?

No. Fixed.


Here you will find errors of spelling, grammar, and design that students have noted. Remember, each error found corresponds to a point of extra credit for everyone. I usually limit such extra credit to five points. However, if I make an astoundingly large number of errors, then I will provide more extra credit.

I will not accept corrections for credit until after I have taken the examination out of draft mode.

I will not credit corrections for text in the Q&A and errata sections, since those are often written quickly to get information out to students.

  • Missing period after “(really caffeinated)” [MD & FB, 1 point]
  • Misspelled “revisited” [MD, 1 point]
  • the know” instead of “they know” [MD & FB, 1 point]
  • But they don't like that arrays are not expandable” appears to be grammatically incorrect [AA, 1 point]

The next few problems were errors in the code that seem significant enough that they should not count toward the 5 point limit.

  • Missing postcondition in SirTedVector.get [TN, 1 point]
  • In problem 4, needed precondition for get that ensured the state of values [BW, 1 point]
  • It's impossible to match the hex colors, given that they use capital letters and we convert to lowercase [TN & JGS, 1 point]

Copyright (c) 2013 Samuel A. Rebelsky.

Creative Commons License

This work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this license, visit or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.