Please keep all answers short and to the point.

1. (8 points) Tell the running time of each of the following algorithms:
   
   
   1.   O(n²)  Bubble sort
      
      
   2.   O(n²)   Selection sort
      
      
   3.   O(n²)   Insertion sort
      
      
   4.   O(log n)   Binary search (when unsuccessful)
      
      
   5. O(n log n)   Heapsort
      
      
   6.   O(n²)   Quicksort (worst case)
      
      
   7.   O(n log n)   Creation of a Huffman tree (using a priority queue)
      
      
   8.   O(v²)   Dijkstra's shortest-path algorithm   (or O(v log v), depending on implementation)
      
      
2. (3 points) Tell whether each of these specifies a lower bound, upper bound, or exact bound:
   
   
   1. Big-O specifies a(n)    upper    bound.
      
      
   2. Big-Θ specifies a(n)    exact   bound.
      
      
   3. Big-Ω specifies a(n)    lower    bound.
      
      
3. (4 points) We will define a "word" to consist of one or more syllables. Each syllable consists of one or two consonants followed by a vowel, except that the first syllable may be a single vowel and the last syllable may end with a single consonant. Assume that the terms <vowel> and <consonant> have already been defined (i.e. don't write them yourself), use BNF (or EBNF) to define a <word>. Example words: a, at, kokomo, tokamak, ashanti. (Hint: Use scratch paper, and copy your answer to the exam.)
   
   <word> ::= <syllable> { <syllable> }
             | <vowel> { <syllable> }
             | <syllable> { <syllable> } <consonant>
             | <vowel> { <syllable> } <consonant>
   
   
4. (2 points)
   1. What advantage does Java's TreeMap have over HashMap?
      Keeps keys in order
      
   2. What advantage does Java's HashMap have over TreeMap?
      Faster
      
      
      
5. (4 points) What are your instructor's four rules for writing a recursive method?
   Do the base case(s) first.
   Recur only with a simpler case.
   Don't both modify and examine a global variable.
   Don't look down.
   
6. (2 points) Suppose in a (correct) Java program you find the line
        for (Pet pet : pets) {
   tell everything you can deduce about the pets variable.
   
   It's either an array OR a genericized type that defines the Iterable interface.
   It contains Pet objects.
   
   
   
7. (3 points) In which Java package would you expect to find:
   
   
   1. a method for sorting an array?
      java.util
      
   2. a method for appending two Lists?
      java.util
      
   3. a method for testing whether a file exists?
      java.io
      
8. (1 point) When should you use Comparator rather than Comparable?
   When you may want to compare (or sort) along different dimensions.
   
   
9. (8 points) Consider the following binary tree:

   Is this a sorted binary tree? No Why do you think it's sorted (or not sorted)?   N > A

   In what order will the nodes of this binary tree be visited:
   
   
   3. In preorder?     D A N E R
      
      
   4. In inorder?     N A D E R
      
      
   5. In postorder?      N A R E D
      
      
   In what order will the nodes be examined by each of the following:
   
   
   6. A breadth-first search?     D A E N R   or     D E A R N     or     D A E R N     or     D E A N R
      
      
   7. A depth-first search?     D A N E R    or     D E R A N
      
      
   8. A depth-first iterative deepening search?      D D A E D A N E R     or     D D E A D E R A N
      
      
10. (1 point) If you override hashCode(), you must also override   equals(Object).
    
    
11. (2 points) Jack has the job of assigning n tasks to n people (one task per person). Each person has told Jack how happy he/she would be (on a scale of -1.0 to +1.0) to do each task. Jack wants to maximize the total happiness, so he writes a program that tries every possible assignment of tasks to persons, and chooses the best.
    
    
    1. What is the name for the kind of algorithm Jack is using?      Brute force
       
       
    2. How long will his program take?     O(n!)     (equivalently, O(2ⁿ))
       
       
12. (2 points) Jill has the same problem as Jack (above), but her program finds the best (happiest) matching of some one person to a task and assigns it, then repeats the same process with the remaining persons and tasks, until none are left.
    
    
    1. What is the name for the kind of algorithm Jill is using?     Greedy
       
       
    2. How long will her program take?     O(n²)
       
       
13. (14 points) Briefly define each of the following. Do not give examples.
    
    
    1. mutative transformer     A method that changes the object to which it is applied
       
       
       
    2. weakly connected (digraph)     The underlying undirected graph is connected
       
       
       
    3. factory method     A method that returns (or may return) a new object
       
       
       
    4. heap property      The value in a node is not less than (or not greater than) the values in either child
       
       
       
    5. blind search     A search with no information as to where a goal may be
       
       
       
    6. collision     Two or more objects hash to the same location
       
       
       
    7. checked exception     An Exception that must be caught or declared as thrown
       
       
       
14. (2 points) The A* search method is a kind of   best -first search. It uses the formula f(n) = g(n) + h(n); in this formula, what is the meaning of n?
    A node on the path from the root to a possible goal
    
    
    
15. (2 points) What are the two most important differences between a Set and a List in Java?
    A set is unordered and has no duplicate elements
    
    
    
16. (3 points) Messages are composed of the letters A, B, and C. On average there are ten times as many As as Bs, and ten times as many Bs as Cs. (For example, a message might start out as AAAAAAABAAA...). What is a suitable Huffman code for these messages?
    
             A = 0              B =  10               C =  11         [ or         A = 1              B =  01               C =  00 ]
    
    
17. (1 point) Suppose a class definition begins as follows:
         public class Person {
              String name;
              GregorianCalendar dateOfBirth;
              int age;
              ...
    What style rule does this violate?    DRY (Don't Repeat Yourself)
    (I forgot to make these private, so that's another acceptable answer...)
    
18. (1 point) A heap (as in heapsort) is useful in implementing what ADT?     A priority queue
    
    
    
19. (3 points) Using Java's generics,
    1. Declare a HashMap named map whose keys are Strings and whose values are Doubles.
       HashMap<String, Double> map;    (ok if includes assignment, = new HashMap<String, Double>() )
       
    2. Write an "enhanced for loop" to find the total of the values in this HashMap.
       
            double total = 0.0;
            for (  String key : map.keySet( )   ) {
                 total = total + map.get(key);
            }
       
       
20. (1 point) A maze can be created by finding a(n)   spanning tree   of a graph.
    
    
21. (1 point) An algorithm is considered intractable if it requires    exponential    time.
    
    
22. (1 point) What is the relationship between an alpha cutoff and a beta cutoff?
    A beta cutoff is an alpha cutoff as seen from the opponent's point of view.
    
    
    
23. (1 point) If an adjacency matrix is symmetric about the main diagonal, what does this imply about the digraph that it represents?
    Every edge has a parallel edge in the opposite direction.
    
    
24. (1 point) Which digraph representation is more generally useful, an adjacency set representation, or an edge set representation? (Don't explain why.)
    An adjacency set representation.
    
    
25. (1 point) In class I described how to build a maze. For an NxN maze, what is the running time of this algorithm?
    O(N²)
    
    
26. (3 points) sin = opp/hyp, cos = adj/hyp , tan = opp/adj .
    
    
27. (1 point) What can you do with a "pointer" that you can't do with a "reference"?    Pointer arithmetic
    
    
28. (4 points) Each of the following Collection methods corresponds to a mathematical operation on sets. Give the names of the corresponding mathematical operations.
    
    
    1. containsAll(Collection c) corresponds to     subset .
       
       
    2. addAll(Collection c) corresponds to   union .
       
       
    3. removeAll(Collection c) corresponds to   set difference .
       
       
    4. retainAll(Collection c) corresponds to   intersection .
       
       
29. (3 points) An Abstract Data Type specifies these two things:
    
    The set of possible values
    The set of available operations
    
    but does not specify:
    
    The implementation
    
30. (1 point) If you get a "Concurrent modification exception," what have you probably done wrong?
    
    You modified a collection while it was being iterated over.
    
    
31. (12 points) True or false:
    1.  False  A hashCode( ) method must return different values for different objects.
       
       
    2.  True  The split(String) method in String takes a regular expression as its parameter.
       
       
    3.  True  The trig functions (sin, cos, tan) expect their arguments to be in radians.
       
       
    4.  True  The Stack class extends Vector.
       
       
    5.  True  A method may have at most one vararg parameter.
       
       
    6.  False  The java.util package defines Stack and Queue classes.
       
       
    7.  True  Genetic algorithms work better with sexual, rather than asexual, reproduction.
       
       
    8.  False  Genetic algorithms work best with a moderate to large probability of mutation.
       
       
    9.  True  Mutation in genetic algorithms helps combat lack of genetic diversity.
       
       
    10.  True  State-space searches should be designed with as few operators as possible.
        
        
    11.  True  Backtracking is basically depth-first tree searching.
        
        
    12.  True  Breadth-first searches usually require more memory than depth-first searches.
        
        
32. (1 point) How can you easily turn a nonrecursive depth-first search into a breadth-first search?
    Replace the stack with a queue
    
    
33. (3 points) When you need to time a method, tell three things you can do to improve the accuracy of the timing.
    Close as many other applications as possible.
    Request garbage collection before doing the timing.
    Repeat the test many times and take the average.
    [Acceptable: Use nanoTime() rather than currentTimeMillis())