Questions

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.

Recursion

• 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().
• 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 boolean nameList() method, based on your BNF definition, to recognize a comma-separated list of names.

Java

• 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 Strings and only Strings.
• 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.)

Comparisons

• You have some Employee objects with instance variables String name and long ssn (Social Security Number).
  • 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 new TreeSet(), but you do not write any comparison methods, how will the objects be sorted?
• Although you should never use the == operator to compare Strings, it sometimes works properly. Why?
• If you override the hashCode() method for your objects, you should also override equals(Object). Why?

Tools

• You have a constructor Fraction(int numerator, int denominator) which should throw an IllegalArgumentException if denominator == 0. Write a JUnit method to test that it throws the exception correctly.
• 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?

Data Structures and Algorithms

• 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 StringBuffers (or the newer StringBuilders) 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 #1: Review the "General requirements for an ADT" in the Trees lecture.
  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?
• 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.

Math

• How many ways could a 32-bit integer have exactly ten of its bits set to 1?
• Simplify: O(5*n² + 3*2ⁿ + 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?

Other things to know

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