CIT 594 Final Exam
Spring 2003, Dave Matuszek
Name _______________________________________

135 points total. Please keep all answers brief and to the point; try to stay within the space provided.

  1. (5 points) The Lisp user thinks in terms of manipulating lists, but what is the fundamental data structure used by the implementation? Briefly explain your answer.

    Binary trees. The CAR is the left child, and the CDR is the right child.

  2. (3 points) What is the result of (EVAL (QUOTE (CDR (QUOTE (A B C))))) ?

    (B C)

  3. A friend of yours complains that the following Java statement "doesn't work."
        if (myHashSet.contains(new Position(i, j))
            System.out.println("Been there, done that.");
    1. (5 points) Why doesn't it work?

      If Position uses the default equals(Object) and hashCode(), a newly created Position cannot possibly already be in the HashSet.

    2. (5 points) Briefly, how would you tell your friend to fix it?

      The simplest way is probably to override equals(Object) and hashCode() within the Position class.

  4. (5 points) If a connected undirected graph contains 12 nodes and 34 edges, how many edges are in a spanning tree of the graph?
           11

  5. (10 points) What is the Big-O running time of the following algorithm? (You must specify what you are using for n, the size of the problem.)
    	static int euclid(int x, int y) {
    	    assert x > 0 && y > 0;
    	    if (x > y) return euclid(x - y, y);
    	    if (x < y) return euclid(x, y - x);
    	    return y;
    	}
    

    On average, and in the worst case, it will be O(n).

    There are various ways to choose n. The simplest (though not the most accurate) is just to choose n as the larger of x and y.

  6. (10 points) Write a non-recursive version of the euclid method given above.
    	static int euclid(int x, int y) {
    	    assert x > 0 && y > 0;
            while (x != y) {
    	        if (x > y) x = x - y;
    	        else y = y - x;
            }
    	    return y;
    	}
  7. "Cindy's Puzzle" consists of three black marbles and three white marbles, arranged in seven compartments, like this:
     
    The rules are as follows:
      • Move one square, into an unoccupied space, or
      • Jump one piece of the opposite color, landing in an unoccupied space. (Jumped pieces are not removed.)

    Represent this puzzle as a state space. For this puzzle, tell:

    1. (5 points) How would you represent a "state" in Java? (Be specific.)
      The simplest way is as a 7-element array; any distinguishable values can be used for black, white, and blank.

    2. (7 points) What are the "operators"? For each operator, tell exactly what it does. (Hint: You probably need 6 or 7 operators.)

      If you clearly didn't understand the basic idea that an operator transforms one state into another, you got zero points on this part. An operator that is represented by a method must have a state as its argument and a state as its result.

      There are two simple approaches:
      1. Move marble n (six marbles, therefore six operators).
      2. Move the marble in location n (seven locations, therefore seven operators).
      With either approach, the operator should check whether (a) a simple move is possible, (c) a jump is possible, or (c) no move is possible. Since exactly one of these conditions can hold, the operator is well-defined.

    3. (5 points) To solve this puzzle, would you need to do a tree search or a graph search? Explain your answer.

      A tree search, since (by the nature of the puzzle) states cannot be repeated.


  8. (3 points) Which sorting algorithm uses a priority queue?
    The correct answer is Heapsort, but a very good case can also be made for Selection Sort.

  9. (5 points) Can mutable objects be used as keys in a HashMap? Briefly explain your answer.

    Yes. However, if you define your own hashCode() and equals(Object) methods for your keys, and those keys are changed in any way that changes the results of these two methods, the behavior of the HashMap will be undefined. (Note that this is not a problem for classes that you define, if you do not override one or both of these methods.)

  10. Briefly define:
    1. (5 points) Refactoring

      Rewriting and rearchitecting a program, typically as it is being written.

    2. (5 points) Unit testing

      Testing a module in isolation.

    3. (5 points) Source code control system
      A tool for keeping track of all current and old versions of code, along with modification dates and who is or has been working on that code.

    4. (5 points) The DRY principle

      Don't Repeat Yourself.

  11. A fraction is a number such as 3/4.

    1. (10 points) Define an ADT for the class Fraction by specifying Java method (or constructor) headers for each operation. Be sure to include any essential constructors or methods.

      Here's my version.

      (C) public Fraction(int numerator, int denominator)

      (AT) public Fraction add(Fraction f)
      (AT) public Fraction subtract(Fraction f)
      (AT) public Fraction multiply(Fraction f)
      (AT) public Fraction divide(Fraction f)

      (A) public boolean equals(Fraction f)
      (A) public int hashCode()

      (A) public boolean isNegative()
      (A) public boolean isZero()
      (A) public int compareTo(Fraction f)
      (A) public String toString()
      (A) public double toDouble()

      And maybe these less useful methods:
      (A) public int getNumerator()
      (A) public int getDenominator()


      Notes:
      • Fractions are numbers. The whole point of having numbers is to do arithmetic on them.
      • Apparently, nobody but me thought about comparing fractions.
      • Fractions should be kept in the lowest terms. This can be done automatically, in the constructor and the arithmetic routines. There is no reason to expect the user to do this.

    2. (5 points) Label each of your above methods as a constructor (C), accessor (A), applicative transformer (AT), or mutative transformer (MT).

    3. (5 points) Tell whether you made your Fraction objects mutable or immutable, and why you did it that way.

      Immutable. This is safer, consistent with Strings and other types of numbers, and allows easy use as keys in hash tables. Immutable objects are Thread-safe and never need to be cloned. There seems to be no reason to make Fractions mutable.
      Note: Several students list mutative transformers (MT) yet claim their class is immutable. I find it difficult to understand this error.

    4. (6 points) Where in the Fraction class should you raise an exception?

      In the constructor, and in divide(Fraction), to ensure the denominator is not zero.

  12. (6 points) Traverse the following binary tree in:
    1. Preorder:  A B C D E

    2. Inorder:  B D E C A

    3. Postorder:   E D C B A


  13. (5 points) Suppose I tried to find a solution to the "Missionaries and Cannibals" problem using an iterative deepening tree search (not a graph search). Would this approach work? Why or why not?

    Yes. Although there are cycles in the graph, the problem is small enough that a solution will be found quickly. Iterative deepening ensures that we won't get caught in a cycle forever.

  14. (5 points) You want to plan a route from Acetown to Zedville that passes over as few bridges as possible. (You have a road map that also shows bridges.) How can you use Dijkstra's algorithm to solve this problem?

    Assign to each road a "cost" equal to the number of bridges on that road. Use Dijkstra's algorithm to determine the least-cost paths.
    Please note that I did not ask you to explain Dijkstra's algorithm!

  15. (5 points) You are given a binary tree, with String data in each node of the binary tree, and you need to make an exact copy of the binary tree with all its data. Describe (in English, do not write code) the simplest way to do this.

    Create a new binary tree whose data is the String in the given binary tree. (Strings are immutable, so there's no need to make a copy of the string.) Recursively copy the left subtree and the right subtree, and use these copies in the new binary tree.
    Incidentally, a good way to implement this is to write a copy constructor (a constructor that takes an object and produces a new, identical object).
    I spent considerable time in lecture explaining why implementing Cloneable will not work.