CIT594 Final Exam Answer Key
Spring 2004
Name_________________________________________

Please read each question carefully, and answer the question that is asked, not some related question. Keep answers brief--you have enough room for correct answers. Write legibly--if I can't read your answer, it's wrong.

  1. [2 points] Tell two differences between Java's Set and List.




  2. [2 points] Tell two differences between Java's Map and TreeMap.





  3. [2 points] What is the most important difference between a "pointer" and a "reference"?



  4. [2 points] Suppose your program is running too slowly, and you need to make it faster. What is the first thing you should do?



  5. [8 points] True or false:

    1. _____ If you need random numbers for several different purposes in your program, you should create a different random number generator for each.

    2. _____ In a JUnit class, every public void testXxx() method will be called automatically.

    3. _____ Every object has an equals method.

    4. _____ Every object has a hashCode method.

    5. _____ A beta cutoff occurs when you decide that your opponent will not explore beneath a node.

    6. _____ Genetic algorithms are a kind of state-space searching.

    7. _____ Quicksort is widely used because it is always O(n log n) time.

    8. _____ Breadth-first searching requires more memory than depth-first searching.


  6. [5 points] Briefly define each of the following:

    1. Unit test


    2. Reflection


    3. Dynamic programming


    4. Abstract data type


    5. Refactoring



  7. [10 points total] Here is the definition of a class:
       public class BooleanArray {
           public boolean[] bits = new boolean[32];
       }

    If you were to write a BooleanArrayIterator class (implementing Iterator) for this class,

    1. [2 points] What instance variable or variables would you need?



    2. [6 points] Write the complete header line of each of the three required methods:







    3. [2 points] Since a remove method for this class doesn't seem to make much sense, but Java requires that you have one, what should your remove method do?



  8. [4 points] State your instructor's four rules for doing recursion.









  9. [4 points] The following is a partial description of a BinaryTree class:

    public class BinaryTree {
       BinaryTree leftChild, rightChild;
       Object value;
       ...   }
    Write an instance method to determine whether two binary trees are equal (same shape, same values).

          public boolean equals(BinaryTree that) {







          }

  10. [2 points] Use extended BNF to define <integer>. An integer should consist of an optional plus or minus sign, followed by one or more digits. Assume that <digit> has already been defined.





  11. [2 points] A function f(n) is O(g(n)) if there exist positive constants c and N such that,
    for all n > N, _____________________ .

  12. [2 points] A function f(n) is Ω(g(n)) if there exist positive constants c and N such that,
    for all n > N, _____________________ .

  13. [2 points] A function f(n) is Θ(g(n)) if there exist positive constants c1, c2 and N such that,
    for all n > N, _____________________ .

  14. [8 points total] It is possible to implement a two-dimensional sparse array of doubles using only a map (no linked lists), that provides both fetch and store operations. To do this,

    1. [3 points] What would you use for keys?



    2. [3 points] What would you use for values?




    3. [2 points] Briefly mention one disadvantage of this implementation.


  15. [12 points total] Given a set of positive integers, for example, {19, 27, 42, ...}, suppose you want to sort these integers into three equal piles, so that the sum of the integers in each pile is the same.

    1. [1 point] Briefly describe a fast (linear time) test for whether the problem might have a solution.



    2. [4 points] Briefly describe an algorithm for finding an exact solution to this problem (just the general idea, don't tell me about details such as loops).









    3. [2 points] What is the running time of your algorithm? Why?




    4. [3 points] Briefly describe an algorithm for finding a reasonably good approximate solution to the problem (that is, the piles should be approximately equal).











    5. [2 points] What is the running time of your approximate algorithm? Why?




  16. [2 points] What two assumptions are made by the alpha-beta algorithm?








  17. [6 points] For the following binary tree:
    1. In what order would the nodes be visited by a preorder walk?

    2. In what order would the nodes be visited by an inorder walk?

    3. In what order would the nodes be visited by a postorder walk?

    4. In what order would the nodes be searched by a breadth-first search?


    5. In what order would the nodes be searched by a depth-first search?


    6. In what order would the nodes be searched by a depth-first iterative deepening search?


    (If there is more than one possible answer to any of the above, provide only one.)

  18. [4 points] A message contains only the letters G, A, T, C in the proportions 1:2:4:8. That is, A is twice as likely to occur as G; T is twice as likely as A; and C is twice as likely as T. If you use a Huffman encoding, what is the average number of bits required per letter?











  19. [5 points] The A* algorithm uses the formula  f(N) = g(N) + h(N).

    1. In A*, what are the computed f(N) values used for?


    2. What is N?


    3. What is g(N)?


    4. What is h(N)?


    5. What is f(N)?

  20. [2 points] When you create a new random number generator, you can supply a seed. Briefly, why would you ever want to do this?




  21. [12 points total] Suppose you are given a Huffman encoding (in the form of a table: A=01, B=1010, etc.) and a long message that has been encoded with it. You want to write a program as quickly and simply as possible to decode this message; you don't care how efficient the program is, so long as it isn't infeasibly slow (for example, exponential time is too slow).

    1. [4 points] Describe in English (do not write code) the algorithm you would use.









    2. [2 points] What is the running time of your algorithm? Why?




    3. [4 points] Now suppose your program is going to become part of a communications program, and needs to be made as fast as possible. Describe in English (do not write code) the algorithm you would use in this case.







    4. [2 points] What is the running time of your faster algorithm? Why?




  22. [2 points] When the statement Person p = new Person(); is executed,

    1. What is placed on the heap?


    2. What is placed on the stack?