CIT594 Final Exam Answer KeySpring 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.

- [2 points] Tell
**two**differences between Java's`Set`

and`List`

.

- [2 points] Tell
**two**differences between Java's`Map`

and`TreeMap`

.

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

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

- [8 points] True or false:

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

- _____ In a JUnit class, every
`public void test`

method will be called automatically.*Xxx*()

- _____ Every object has an
`equals`

method.

- _____ Every object has a
`hashCode`

method.

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

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

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

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

- _____ If you need random numbers for several different purposes in your
program, you should create a different random number generator for each.
- [5 points] Briefly define each of the following:

- Unit test

- Reflection

- Dynamic programming

- Abstract data type

- Refactoring

- Unit test
- [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,

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

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

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

- [2 points] What instance variable or variables would you need?
- [4 points] State your instructor's four rules for doing recursion.

- [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) {`

}

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

- [2 points] A function f(n) is O(g(n)) if there exist positive constants
c and N such that,

for all n > N, _____________________ .

- [2 points] A function f(n) is Ω(g(n)) if there exist positive constants
c and N such that,

for all n > N, _____________________ .

- [2 points] A function f(n) is Θ(g(n)) if there exist positive constants
c
_{1}, c_{2}and N such that,

for all n > N, _____________________ .

- [8 points total] It is possible to implement a two-dimensional sparse array
of
`double`

s using only a map (no linked lists), that provides both`fetch`

and`store`

operations. To do this,

- [3 points] What would you use for keys?

- [3 points] What would you use for values?

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

- [3 points] What would you use for keys?
- [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 point] Briefly describe a fast (linear time) test for whether the
problem might have a solution.

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

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

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

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

- [1 point] Briefly describe a fast (linear time) test for whether the
problem might have a solution.
- [2 points] What two assumptions are made by the alpha-beta algorithm?

- [6 points] For the following binary tree:

- In what order would the nodes be visited by a
**preorder walk**?

- In what order would the nodes be visited by an
**inorder walk**?

- In what order would the nodes be visited by a
**postorder walk**?

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

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

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

- In what order would the nodes be visited by a
- [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?

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

.

- In A*, what are the computed
`f(N)`

values used for?

- What is
`N`

?

- What is
`g(N)`

?

- What is
`h(N)`

?

- What is
`f(N)`

?

- In A*, what are the computed
- [2 points] When you create a new random number generator, you can supply
a seed. Briefly, why would you ever want to do this?

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

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

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

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

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

- [4 points] Describe in English (do not write code) the algorithm you
would use.
- [2 points] When the statement
`Person p = new Person();`

is executed,

- What is placed on the heap?

- What is placed on the stack?

- What is placed on the heap?