At Last! The Long-Awaited
Final Exam Study Guide!CIT 594, Spring
2005 |

Some of the following questions will be on the final exam. Some of the following
questions will be *similar to* questions on the final exam. Not every question
on the final exam will be similar to those given below.

I highly recommend forming a study group with a friend or a couple of friends.

- You are in a class
`BinaryTree`

with instance variables`BinaryTree leftSubtree`

and`BinaryTree rightSubtree`

. Write a mutative transformer method`reverse()`

which interchanges the left and right subtrees, at all levels.- What is the Big-O execution speed of your method? (As always when using
Big-O notation, be sure to specify what you are using for
**n**.) - Explain the problems involved in writing an
*applicative*transformer method

.BinaryTree reverse()

- What is the Big-O execution speed of your method? (As always when using
Big-O notation, be sure to specify what you are using for
- If you write a binary tree search that uses a stack, you get a depth-first
search. If you write the same search using a queue, you get a breadth-first
search. In what order will nodes be searched if you use a deque, putting the
left child at the front (first out) and the right child at the rear (last
out)?
- Assuming a balanced binary tree, what is the Big-O time requirement of this method?
- Assuming a balanced binary tree, what is the Big-O space requirement of this method?

- Suppose we have a comma-separated list of names, for example,
`Ace, Deuce, Trey`

.- Write the BNF to describe such lists (assume
`<name>`

has already been defined). - Write a

method, based on your BNF definition, to recognize a comma-separated list of names.boolean nameList()

- Write the BNF to describe such lists (assume

- Write a Java 5
`enum`

named`WEEKDAY`

, enumerating the seven days of the week, with boolean method`isWorkDay()`

.`isWorkDay()`

should return`true`

for all days except Saturday and Sunday. Use proper capitalization. - In Java 5, use generics to declare and define an
`ArrayList`

that can hold`String`

s and only`String`

s. - Give two advantages of generics.
- Why is the following illegal?

`if (myList instanceof ArrayList<Integer>) {...}`

- In Java, what values are put on the stack, and which go in the heap? (Be precise.)

- You have some
`Employee`

objects with instance variables

andString name

(Social Security Number).long ssn - If you want to keep these objects in a
`TreeSet`

, sorted*only*by name, what is the simplest way to do this? Write the necessary method. - If you want to keep these objects in a
`TreeSet`

, sorted by name, but*also*in a second`TreeSet`

, sorted by Social Security Number, how would you do this? Write*one*of the necessary methods. - If you store your
`Employee`

objects in a`TreeSet`

created by

, but you do not write any comparison methods, how will the objects be sorted?new TreeSet()

- If you want to keep these objects in a
- Although you should never use the
`==`

operator to compare`String`

s, it sometimes works properly. Why? - If you override the
`hashCode()`

method for your objects, you should also override`equals(Object)`

. Why?

- You have a constructor
`Fraction(int numerator, int denominator)`

which should throw an`IllegalArgumentException`

if

. Write a JUnit method to test that it throws the exception correctly.denominator == 0 - Printing from JUnit tests:
- Should tests which pass (succeed) print anything? Why or why not?
- Should tests which fail print anything? Why or why not?

- In JUnit, what is the difference between a
*failure*and an*error*? - What does the
`F3`

key do in Eclipse?

- Explain the difference between a
*deep copy*and a*shallow copy*. `java.util.Stack`

*extends*`java.util.Vector`

. Tell why this is a bad design, and suggest a better one.- For classes that implement
`hashCode()`

(such as`String`

), what range of values is returned by the`hashCode()`

method? - Given a
`Stack s`

, write the simplest possible method to reverse the order of elements in`s`

. - Explain why
`StringBuffer`

s (or the newer`StringBuilder`

s) should not be used as keys in a hash table. - Design
*(do not implement!)*a`Loop`

ADT. A "Loop" is a circular sequence of values such that (1) from any value, you can find the next value, and (2) there is no "first" or "last" value. Your design should specify:- Public instance variables, if any
- Constructors,
- Transformers, and
- Accessors

Hint #2: Remember what it is important*not*to specify in an ADT. - For the following binary tree (illustration to be provided), tell in what
order the nodes would be visited in:
- Preorder
- Inorder
- Postorder
- Depth-first search
- Breadth-first search
- Depth-first iterative-deepening search

- Of the three search techniques (DFS, BFS, DFID),
- Which two searches, if implemented properly, will find the same goal node?
- Which search or searches require space that is exponential with the depth of the search?
- How does the branching factor of the search tree affect (a) the space requirements and (b) the time requirements for the search?
- Which search or searches can be implemented without an explicit collection of unexplored nodes?

- Heapsort used an array to represent a binary tree.
- Could you represent a possibly unbalanced tree of random integers using this technique? If so, how would you need to modify the technique? If not, why not?

- Two kinds of customers arrive at a theater: Ordinary citizens, who have
to wait in line to buy tickets, and VIPs (Very Important Persons) who also
have to buy tickets, but do not have to wait in line behind ordinary citizens
(though they may have to wait behind other VIPs).
- Is a
`PriorityQueue`

a good data structure for representing this situation? Why or why not? - Instead of two kinds of customers, there are eight (kings, princes,
dukes, etc.), and preference
*must*be given to the highest ranking customers. Does this change your answer? Why or why not?

- Is a
- A robot has the task of collecting beepers from a large rectangular grid.
(Unlike your Robot, this robot has complete knowledge of where all the beepers
are, and has no obstacles to avoid.)
- Describe (do not write code!) a greedy algorithm for collecting all the beepers.
- Does your greedy algorithm result in a minimum length path for the robot? Either prove (argue convincingly) that it does, or show a counterexample.

- In the game of Nim, some number of pennies (say, 15) are put on a table,
and two players alternate turns, at each turn taking either one, two, or three
pennies. The object of the game is to force your opponent to take the last
penny.
- Describe this game as a state-space problem, specifying the states and the operators.

- Some number of coins (pennies, nickels, dimes, and quarters) are arranged
randomly in a circle. The first player takes any coin; after that, players
alternate turns, at each turn taking either the next coin clockwise or the
next coin counterclockwise from the one just taken. The object is to collect
more money than your opponent.
- Describe this game as a state-space problem, specifying the states and the operators.
- Describe a greedy algorithm for playing this game.
- Is the greedy algorithm optimal? Why or why not?
- Assume there is a large number (hundreds) of coins in the circle. Is the A* algorithm appropriate for choosing the next move? Why or why not?

- For the following two-person game (illustration to be provided), with values
as shown at the most deeply-explored nodes,
- Tell what the backed-up values would be, if all the nodes shown were explored.
- Label any alpha cutoffs or beta cutoffs, and show which two nodes are involved.

- Given the following characters and their relative frequencies (to be provided),
- Tell how many bits would be required for each character in a fixed-width encoding.
- Construct a Huffman tree for the characters.
- Show the Huffman encoding for each character.
- Compute how many bits per character would be required, on average, for a long message in which the different characters appeared with the expected relative frequency.

- How many ways could a 32-bit integer have exactly ten of its bits set to 1?
- Simplify: O(5*n
^{2}+ 3*2^{n}+ 30*n + 12). - Suppose there are 30 students in a class.
- How many permutations of 5 of those students are there?
- How many combinations of 5 of those students are there?
- If you took roll each day, how many bits would you need to store each result?

- You should know my four rules of recursive programming.
- You should know
*all*the methods in both the`Collection`

and the`Map`

interfaces. - You should understand the difference between a
*pointer*and a*reference*. - You should understand the relationships between
`equals`

,`hashCode`

,`Comparable`

, and`Comparator`

.