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.
   
   
   
   
   
2. (3 points) What is the result of (EVAL (QUOTE (CDR (QUOTE (A 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?
      
      
      
      
   2. (5 points) Briefly, how would you tell your friend to fix it?
      
      
      
      
      
      
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?
   
   
   
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;
   	}
   

6. (10 points) Write a non-recursive version of the euclid method given above.
   
   
   
   
   
   
   
   
7. "Cindy's Puzzle" consists of three black marbles and three white marbles, arranged in seven compartments, like this: The rules are as follows:
   • Black pieces may only move right.
   • White pieces may only move left.
   • A piece can either:
   • 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.)
      
      
      
   2. (7 points) What are the "operators"? For each operator, tell exactly what it does. (Hint: You probably need 6 or 7 operators.)
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
   3. (5 points) To solve this puzzle, would you need to do a tree search or a graph search? Explain your answer.
      
      
      
      
      
8. (3 points) Which sorting algorithm uses a priority queue?
   
   
9. (5 points) Can mutable objects be used as keys in a HashMap? Briefly explain your answer.
   
   
   
   
   
   
10. Briefly define:
    1. (5 points) Refactoring
       
       
       
       
    2. (5 points) Unit testing
       
       
       
       
    3. (5 points) Source code control system
       
       
       
       
    4. (5 points) The DRY principle
       
       
       
       
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.
       
       
       
       
       
       
       
       
       
       
       
       
       
       
       
    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.
       
       
       
       
       
    4. (6 points) Where in the Fraction class should you raise an exception?
       
       
       
12. (6 points) Traverse the following binary tree in:
    

    1. Preorder:
       
       
    2. Inorder:
       
       
    3. Postorder:
       
       

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