CIT 594 Exam Questions
Spring 2009, David Matuszek

The following is a long list of possible exam questions; my exams will be composed of these questions, or questions that are modifications of these. Questions are not divided into pre-midterm and post-midterm, because I don't cover topics in the same order every time (and I may not cover every topic). It's up to you to figure out what I've covered and what I haven't. If I add questions during the semester, they will be in a different color. Please do not post answers to these questions on the web.

Style

• When is it appropriate for a class X to extend a class Y?
• In general, should you use inheritance or composition? Why?
• What do we call it when the only thing a method does is to call another method with the same name in a different class?
• The Stack class extends the Vector class. Why does your instructor think this is a bad design?
• What is wrong with the following design for a class?
      class Line {
        private double x1, y1; // first point
        private double x2, y2; // second point
        private double length; // length of line
        // assorted constructors, methods, etc.
    }
• List three advantages of using TDD (Test Driven Design).
• What does the acronym DRY stand for?
• What does the acronym YAGNI stand for?
• How does it help you in debugging if the fields of your class are private?
• Complete this sentence: "Weeks of programming can save you ___________________________."
• Design a Subarray class, such as you might use in a Quicksort program. Tell what constructors and methods you would supply. Do not write an actual code.
• How much output should be provided by a JUnit test class? Defend your answer.
• How do you use JUnit to test a void method?
• How do you use JUnit to test a void method whose purpose is to print results?
• Why is it a good idea to override toString in almost every class you write?
• Why is Set s = new HashSet() generally preferable to HashSet s = new HashSet() ?

Stacks, queues, deques

• What does the acronym LIFO stand for?
• What does the acronym FIFO stand for?
• What data structure is best described by the term "LIFO"?
• What data structure is best described by the term "FIFO"
• "Deque" is a shortened form of what three words?
• What is the immediate superclass of the Stack class?
• In what package will you find the Stack class?
• Which one(s) of these are Sun-supplied classes, and which are Sun-supplied interfaces?
  • Stack
  • Queue
  • Deque
• What data structure is used by Java to store the parameters and local variables of a method?
• What is the difference between the Queue methods add and offer? (Be sure to tell which is which.)
• What is the difference between the Queue methods remove and poll? (Be sure to tell which is which.)
• What is the difference between the Queue methods peek and element? (Be sure to tell which is which.)
• What is the difference between the Stack methods empty and isEmpty? (Be sure to tell which is which.)
• What is the difference between the Stack methods peek and pop? (Be sure to tell which is which.)
• If you implement a stack as an array, should the top element be the one with the lowest index, or the one with the highest index? Why?
• If you implement a queue as a singly-linked list, should the first element in the list represent the front of the queue or the rear of the queue? Why?
• What are the four fundamental Stack methods (excluding stack creation)? Give complete method signatures.
• What is the difference between the two Stack methods empty() and isEmpty()?
• To implement a deque, would it be better to have your Deque class extend ArrayList, or just use an ArrayList as a field? Defend your answer.
• When a queue is implemented as an array, it can be difficult to distinguish a full queue from an empty one. Mention two solutions to this problem.

Collection

• In what package will you find the Collection interface?
• In which of these is order important? Set, List, Map
• In which of these may you have duplicate values? Set, List, Map
• What interface extends Set but keeps elements in order?
• What interface extends Map but keeps keys in order?
• The Set interface extends what other interface?
• The List interface extends what other interface?
• When does the Collection method boolean add(E o) return true?
• When does the Collection method boolean remove(E o) return true?
• Which of the following are legal?
  • List<String> list = new List<String>();
  • List<String> list = new ArrayList<String>();
  • ArrayList<String> list = new List<String>();
  • ArrayList<String> list = new ArrayList<String>();
• Which of the following are methods of the Collection interface?
  • boolean add(E o)
  • boolean addAll(Collection<? extends E> c)
  • void add(int index, E element)
  • Iterator<E> iterator()
  • Set<E> toSet(Collection<E>)
• Under what circumstances does <T> T[] toArray(T[] a) return a new array?
• Write a single line of code that will copy a nonempty LinkedList<String> named list into the array String[] strings.
• Write the complete signature, including the return type and generics, for each of the following methods in the Collection interface:
  • add
  • contains
  • containsAll
  • iterator
  • remove
• If you implement an interface, you have to implement every method described in that interface. However, some methods in the Collection interface are "optional." If you were implementing a Collection and did not want to support an optional method, how would you do this?
• Which of these implement the Collection interface? Arrays, TreeSets, TreeMaps, ArrayLists, LinkedLists, Stacks.
• How can you most easily copy the values from a Stack into an array?
• How can you most easily copy the values from an array into a List?
• Which is correct: Set extends Collection, or Set implements Collection?
• In which Sun-supplied class will you find a shuffle() method?

Iterator

• Write the complete signature, including the return type, for each of the three methods in the Iterator<E> interface.
• Which element of a Collection is removed by the Iterator method void remove()?
• Under what circumstances will an Iterator method throw a ConcurrentModificationException?
• Name three classes (or interfaces) that provide an iterator() method.
• Name two methods in the ListIterator interface that are not also in the Iterator interface.
• If the statement for (Item item : items) {} is syntactically legal, what interface must the class of items implement?

Set

• Draw a line between each set-theoretic operation and the Set method that implements it.

  addAll		difference
  contains		intersection
  containsAll		member
  removeAll		subset
  retainAll		union

• What methods are in the Set interface that are not in the Collection interface?
• Suppose Set set1 contains the strings "a", "b", "c", "d", "e" and Set set2 contains the strings "a","e", "i", "o", "u". What value is returned by each of the following calls (if done separately)?
  • set1.addAll(set2)
  • set1.contains(set2)
  • set1.containsAll(set2)
  • set1.removeAll(set2)
  • set1.retainAll(set2)
• Suppose Set set1 contains the strings "a", "b", "c", "d", "e" and Set set2 contains the strings "a","e", "i", "o", "u". What are the contents of set1 and set2 after each of the following calls (if done separately)?

  Call	set1	set2
  set1.addAll(set2)
  set1.contains(set2)
  set1.containsAll(set2)
  set1.removeAll(set2)
  set1.retainAll(set2)

• You can put mutable (modifiable) objects into a Set, but you shouldn't. Why not?
• Name the two Sun-supplied implementations of the Set interface.

SortedSet

• What three interfaces are extended by SortedSet?
  Give the names of two methods that are in the SortedSet interface but not inherited from any superinterface.
• Write a code snippet to print out all the elements, one per line, in a SortedSet named mySet.
• Write a code snippet to print out the second element in a SortedSet named mySet.
• What condition must an Object satisfy in order to add it to a SortedSet?
• Suppose you have a class Employee with fields String name and int age, and you put Employee objects into a SortedSet. Will the employees be sorted by name, or by age?
• Suppose you have a class Employee with a field long id, and you put Employee objects into a SortedSet. How do you ensure that the employees are sorted by id?
• What does it mean to say that objects are sorted according to their "natural order"?
• What Sun-supplied class implements the SortedSet interface?

List

• Define "list".
• Name two classes that implement the List interface.
• The List interface extends what two other interfaces?
• What List method must you call in order to obtain a ListIterator object?
• True or false: A ListIterator lets you add, remove, and replace elements in a List object.
• Two methods in a ListIterator let you move backwards through a list. Give their complete signatures, including return types.
• Write a code snippet to print out the last element of a nonempty List named list.
• Suppose you frequently need to do a binary search on a list. Should you use a LinkedList or an ArrayList, and why?
• Suppose you need to use a List to implement a deque. Should you use a LinkedList or an ArrayList, and why?
• If numbers is an ArrayList<Double>, is the call numbers.add(3.33) syntactically valid? Why or why not?
• If list is a List<String>, and you call the method list.add("abc"), where in list is "abc" added?
• Give one advantage and one disadvantage of using an ArrayList rather than an array.

Map

• Name two classes that implement the Map interface.
• Write the complete signatures, including generics and return types, of the get and put methods of the Map interface.
• Write the complete signature, including generics and return types, of the entrySet method of the Map interface.
• What is the return type of the values() method of the Map interface?
• It's best to use immutable objects as keys in a Map. Why?
• Write a code snippet to print out the contents of a Map named myMap, one entry per line, as key = value.
• Write a declaration for a HashMap that uses Strings as keys and Doubles as values.
• If hm is a HashMap and tm is a TreeMap, how can you most easily test whether they both have the same key-value pairs?
• How can a method declared in an interface be optional?
• What does it mean to say that the keySet method of a Map returns a "view"?

SortedMap

• What does a SortedMap keep in sorted order: keys, values, or both?
• What interface must be implemented by objects used as keys in a SortedMap?
• What Sun-supplied class implements the SortedMap interface?
• What methods must an object have if it is to be used as a key in a SortedMap?
• How can you iterate over all the elements in a SortedMap? (Answer in English, don't write code.)

BNF

• Define "metalanguage."
• What are the two basic ways in which a BNF grammar can be used?
• Write all BNF rules necessary to define <small integer>, where a "small integer" is a number in the range 0 to 99.
• Write all BNF rules necessary to define <identifier>, where an "identifier" consists of a letter followed by any number of letters and/or digits.
• Write a BNF rule to define a Java return statement. You can assume that any other nonterminals you need have already been defined.
• Write one BNF rule to define a Java if statement. You can assume that any other nonterminals you need have already been defined.
• Write one BNF rule to define a Java while loop. You can assume that any other nonterminals you need have already been defined.
• In "extended" BNF,
  • How do you represent an optional part of the rule?
  • How do you indicate that a part of the rule can be repeated zero or more times?
• Name one thing that is difficult, but still possible, to do in BNF.
• What kind of syntax rule is completely impossible to describe in BNF?
• Distinguish between the terms "sentential form" and "sentence."

Generics

• Declare and define a Java variable named stuff as an ArrayList containing Strings.
• Declare and define a Java variable named stuff as an ArrayList containing a List of Strings.
• Using generics, declare and define a Java variable named stuff as an ArrayList that may contain any kind of Object.
• Briefly, what is the difference between new ArrayList<Object>() and new ArrayList<?>() ?
• Using generics, write the signature for a method named least that takes a Set of values of type E and returns a value of type E.
• In words, what kind of parameter is accepted by the method boolean addAll(Collection<? extends E> c)?
• Declare and define a Stack variable that holds only String objects.
• What is the name of the feature in Java that would be more accurately named "parameterized types"?
• If list is declared as an ArrayList<List<String>>, what kind of parameter can be given to list.add(parameter)?

Recursion

• Define "recursive definition."
• How does a recursive definition differ from a circular definition?
• List Dr. Dave's four rules for doing recursion.
• Write a recursive method named min to return the smallest number in an array of doubles.
• Write a recursive method named sum to return sum of an array of doubles.
• Write a recursive method named log that returns the number of times its input int parameter must be divided by 2 in order to get 0.
• Recursion is possible because parameters and local variables are stored in a(n) ___________.
• True or false: Anything that can be done recursively can also be done iteratively.
• True or false: Anything that can be done iteratively can also be done recursively.

Threads

• You can create a thread by extending the Thread class or by implementing the __________ interface. In either case, what is the exact signature of the method you must implement?
• What happens when you call a Thread's start() method?
• What happens when you call a Thread's run() method?
• What (other than an error) causes a Thread to die?
• What does each of the following methods do?
  • sleep(int)
  • wait()
  • notify()
  • notifyAll()
  • thread.join()
• Circle the methods that may occur only within synchronized code.
  • sleep(int)
  • wait()
  • notify()
  • notifyAll()
  • thread.join()
• Briefly define "daemon thread".
• Briefly define "monitor".
• What object is used by a synchronized instance method as a monitor?
• Suppose your code needs to call doWork() after some other Thread makes the condition isReady() true and does a notifyAll(). Write the code to call doWork() at the correct time.
• When a Thread enters synchronized code, what does this prevent other Threads from doing? (Be precise.)
• Give two possible reasons for using a synchronized statement rather than a synchronized method.

Abstract Data Types

• What does the acronym ADT stand for?
• What three things characterize a data type?
• What two things characterize an abstract data type?
• Name two differences between methods and operators. (Be sure to tell which is which.)
• State the complete rules for naming setters and getters.
• If you are designing an ADT, why should you minimize the number of methods?
• What is a "convenience" method?
• Why is it a bad idea to have too many "convenience" methods?
• What is an "accessor" method?
• If you are designing an ADT, how do you decide which convenience methods to include and which to omit?
• What would you need to do to demonstrate that a particular method of an ADT is not "necessary"?
• Distinguish between an "applicative transformer" and a "mutative transformer." (Be sure to tell which is which.)
• What is a "factory method"?
• Give two reasons it might be preferable to have factory methods rather than constructors.
• When does it make sense to have a class all of whose constructors are private?

State machines

• What simplification is usually made when drawing a state machine?
• What causes a state machine to enter its error state?
• To program a state machine in Java, put a __________ statement inside a __________ statement.
• When implementing a state machine, what type of variable is the best choice for holding the "current state" information?
• Draw a state machine to decide if a string of 'A's and 'B's contains exactly two 'A' characters.
• Draw a state machine to decide if there are no 'A' characters in an input string.

Arrays

• True or false: Arrays are objects.
• Define "subarray."
• If we define int myArray[][] = new int[3][8], what is the type of myArray[1]?
• If we define int myArray[][] = new int[3][8], what value is in myArray[1]?
• Write a Java snippet to create an int[][] array named ragged, having 100 rows, where the even-numbered rows all have 10 elements and the odd-numbered rows all have five elements.
• Write a Java snippet to create an int[][] array named ragged, having 100 rows, where the number of elements in each row is the same as its row number.
• In Java, if obj is an Object, how can you test if it's an array?
• What is the difference between "row major order" and "column major order"? (Be sure to tell which is which.)
• Describe the object created by the declaration new String[10][].
• What two pieces of information does Java keep about each array?
• If you were to define a Subarray ADT, what fields would it need?
• In which two Sun-supplied classes will you find binarySearch methods?

Binary trees

• Given the following binary tree [insert picture], in what order are the nodes visited in: (a) preorder, (b) inorder, (c) postorder, (d) reverse preorder, (e) reverse inorder, (f) reverse postorder.
• What is the "depth" of a node in a binary tree?
• What is the "depth" of a binary tree?
• What is the "size" of a binary tree?
• What, precisely, does it mean to say a binary tree is "balanced"?
• What does it mean to say that a balanced binary tree is "left justified"?
• What does it mean to "traverse" a binary tree?
• Write a recursive method to compute the depth of a binary tree.
• Write a recursive method to compute the size of a binary tree.
• Write a recursive method to find the smallest value in a sorted binary tree.
• When defining a node in a binary tree,
  • Why should the links to the left and right child be private?
  • Why it is usually not necessary to make the value field in the nodes private?
• If a binary tree represents an arithmetic expression, in what order should the nodes be evaluated?
• How many leaves are there in a complete binary tree of depth N (where the root is at depth 0)?
• How many nodes are there in a complete binary tree of depth N (where the root is at depth 0)?

Trees

• What is an "ordered tree"?
• Define "branching factor of a tree."
• If you represent a Java if statement as a tree, should the parentheses be represented in the tree? Why or why not?
• Distinguish between a compiler and an interpreter.
• What type of binary tree traversal doesn't really apply to a general tree? Why?
• What data structure best represents the file system on a computer?

Analysis of Algorithms

• Simplify: O(3n4 - 6n2 + 1009).
• When analyzing an algorithm, we generally determine the worst case, not the average case. Why?
• Which of the following Java statements take constant time?
  • if (x % 2 == 1) x = x - 2;
  • while (x % 2 == 1) x = x - 2;
  • for (int i = 0; i < a.length; i++) a[i] = i * i;
  • for (int i = 0; i < 100; i++) a[i] = i * i;
  • if (x + y > 100) z = Math.max(x, y);
  • if (x * y < factorial(y)) y = x;
  • if (x < y) x = y; else x = factorial(y);
• Arrange in order, from best to worst: O(log n), O(n log n), O(n), O(1), O(2n), O(n2), O(n2 log n).
• A method, written with loops in the obvious way, takes an array of r rows and c columns, finds the minimum value in each column, and returns the maximum of those minima. How long (Big-O notation) do you expect this method to take?
• How fast (Big-O notation) is binary search? Defend your answer.
• Approximately how many times can you (integer) divide the positive number N by 2 before you get 1?
• If you multiply the common (base 10) log of a number N by 3.322, what do you get?
• If log2N = x, then N = _______.
• Given a complexity function f(n), give informal definitions for:
  • O(f(n))
  • Θ(f(n))
  • Ω(f(n))

Comparisons

• Define: (a) reflexive, (b) symmetric, and (c) transitive.
• When would you implement Comparator rather than Comparable?
• What does it mean when the Java API refers to the "natural ordering" of objects?
• What, precisely, does it mean to say that the compareTo method should be "consistent with equals"?
• What, precisely, does it mean to say that the hashCode method should be "consistent with equals"?
• If you want to put Employee objects into a HashSet, the Employee class must override both __________ and __________.
• Write a minimal (but complete) Comparator class to compare Employee objects by their public id fields.
• Suppose you want to sort Employee objects.
  • If you implement Comparable, should you implement it in the Employee class, or in a separate class? Why?
  • If you implement Comparator, should you implement it in the Employee class, or in a separate class? Why?
• What is wrong with the following, and how would you fix it?
            SortedSet<Object> set = new SortedSet<Object>();

Linked Lists

• Distinguish between a "pointer" and a "reference." (Be sure to tell which is which.)
• Name two things that you can do with a pointer that you cannot do with a reference.
• How much storage is allocated by the declaration int[] x; and what are its initial contents?
• Suppose you have a singly-linked list declared as class MyList { int value; MyList next; ...} with a constructor MyList(int value, MyList next):
  • Write a method to return the last value in a nonempty list.
  • Write a method to return the largest value in a nonempty list.
  • Write a method to test whether the list is empty.
  • Assuming that the list contains exactly two elements, write a method to reverse the order of those elements.
  • Write a code fragment to create a list containing the numbers 1 to 100, in order.
  • Write a method to insert a new value at the front of a nonempty list.
  • Write a method to insert a new value at the end of a nonempty list.
• Suppose you have a doubly-linked list declared as class MyList { int value; MyList left, right; ...} with a header cell MyList(0, first_element, lastElement).
  • Assuming that the header is always present, write a method to test whether the list is empty.
  • Write a method to insert a new value at the front of a nonempty list.
  • Write a method to insert a new value at the end of a nonempty list.

Hashing

• In order to insert Books into a HashTable, what two methods must the Book class implement? (Give complete signatures.)
• Define "collision."
• Define "bucket hash."
• What methods are defined by HashMap for inserting and looking up items? (Give complete signatures.)
• If a hash table class has a remove method, how is the hash table most likely implemented? Why?
• Give two restrictions that a hashCode() method must satisfy in order to be valid.
• Give two conditions that a valid hashCode() method should satisfy in order to be a "good" hash code.
• Would the following be a valid hashCode() method?   int hashCode() { return -1; }
• Is it necessary for a hashCode() method to return the same value for a particular object every time the program is run?
• What Java-provided class can always be used safely as keys in a HashMap?
• How does a Hashtable differ from a HashMap? (Be sure to tell which is which.)
• With a well-designed hash map, how long (Big-O notation) does it take:
  • To add an item?
  • To look up an item?
  • To find whether a given value occurs in the map?
  • To find the key associated with a given value?
• What is the "load factor" of a hash table?

Recognizers and Parsers

• Distinguish between a "recognizer" and a "parser." (Be sure to tell which is which.)
• Suppose you have a method boolean symbol(String s) as defined in the Recognizer assignment.
  • Write a method boolean addOp() that will recognize a "+" or a "-".
  • Write a method boolean notEquals() that will recognize a "!" followed by a "=".
  • Write a method boolean dots() that will recognize a "." followed by an optional second ".".
  • Write a method boolean dashes() that will recognize one or more consecutive "-" symbols.
• In a recognizer, when must you report an error rather than simply returning false?

Sorting

• How fast (Big-O notation) is each of the following?
  • Bubble sort
  • Selection sort
  • Insertion sort
  • Heapsort
  • Quicksort
• For each of the following sorting methods, what can you say about the order of elements in the array when you are partway through sorting?
  • Bubble sort
  • Selection sort
  • Insertion sort
  • Heapsort
  • Quicksort
• What is an "invariant"?
• When is Heapsort a better choice than Quicksort? When is Quicksort the better choice?
• In Heapsort,
  • Define "heap" (as the term is used in Heapsort).
  • Define "heap property."
• In order to represent a binary tree as an array, it must be both _______________ and _________________.
• When representing a binary tree as an array, the right child of the root is at index ________.
• Which nodes of the binary tree automatically have the heap property?
• During Heapsort, what is the maximum number of nodes that can fail to have the heap property?

Tree Searching

• What are the space requirements for doing a depth-first search on a balanced binary tree?
• What are the space requirements for doing a breadth-first search on a balanced binary tree?
• What is the main advantage of a breadth-first search over a depth-first search?
• The algorithm for doing an iterative breadth-first search is identical to that for an iterative depth-first search, except that it uses a ________ rather than a ________.
• Given the following tree [insert picture], in what order will the nodes be visited during a depth-first search?
• Given the following tree [insert picture], in what order will the nodes be visited during a breadth-first search?
• Given the following tree [insert picture], in what order will the nodes be visited during a depth-first iterative deepening search?
• Is a depth-first iterative deepening search more efficient on a tree with a low branching factor or a high branching factor?
• It is much easier to do a recursive depth-first search than a recursive breadth-first search. Explain why.

Priority Queues

• What is a good data structure for implementing a priority queue?
• In analyzing a priority queue implementation, what is a suitable characteristic operation?
• If you describe a queue as "first in, first out," how would you describe a priority queue?

Algorithm Types

• What algorithm type is effectively a depth-first search on a virtual tree?
• What algorithm type uses at least two recursive calls at each level?
• What type of algorithm can be described by "do what is best in the short term, and hope the long term works out"?
• Define "heuristic."
• Define "satisficing."
• You are running an online dating service. An equal number of girls and boys have signed up. Each girl has rated each boy (on a scale of 0 to 100), and each boy has rated each girl, according how much they would like to date that person. Your job is to arrange dates for everyone for next Saturday.
  [If this question is on the exam, only one algorithm type willl be requested, and it will not be dynamic programming (too hard).]
  • Describe a greedy algorithm for arranging dates.
  • Describe a genetic algorithm for arranging dates.
  • Describe a randomized (but not genetic) algorithm for arranging dates.
  • Describe a dynamic programming algorithm for arranging dates.
• Name or otherwise indicate three different problems for which a greedy algorithm works well.
• A dynamic programming algorithm can find an optimal solution to a problem if, for that problem, the "principle of optimality" holds. What is this principle?

Backtracking

• Suppose a "goal node" in a binary tree is any leaf at depth 8. Write a backtracking method to search for a goal node. (You can assume the existence of the usual binary tree methods.)
• What characteristics of a problem would suggest that backtracking is a good approach to solving that problem?
• Backtracking corresponds to what kind of tree search?
• In backtracking, what is meant by a "virtual tree"?

Huffman Encoding

• Given the following letters and their frequencies [insert table],
  • Draw the corresponding Huffman tree.
  • Tell the binary encoding for each letter.
• Given the following Huffman tree [insert picture], where the leaves represent letters,
  • What is the binary encoding for each letter (leaf node)?
  • Approximately how many bits will be required to encode a message of 1000 letters?
  • Using this Huffman tree, encode the following [insert text message].
  • Using this Huffman tree, decode the following [insert bit sequence].
• Given the following letter frequencies [insert table], and the following message encoded with a Huffman encoding, decode the message.
• A set of binary encodings has the unique prefix property if ___?
• Does the following set of binary strings [insert set] have the unique prefix property? Why or why not?
• Under what circumstances would Huffman encoding result in a longer (more bits) transmission than the uncompressed file?

Graphs

• If you have an implementation of directed graphs, how could you use this to represent undirected graphs?
• Represent the following graph [insert picture] as an adjacency matrix.
• Represent the following graph [insert picture] as an edge set.
• Represent the following graph [insert picture] as an adjacency set.
• Given the following adjacency matrix [insert data], draw the graph that it represents.
• Given the following edge set [insert data], draw the graph that it represents.
• Given the following adjacency set [insert data], draw the graph that it represents.
• When searching a graph, what are the two techniques for avoiding getting caught in a cyclic loop?
• [Dijkstra's algorithm will not be covered on the final exam.]

Quicksort

• Given the following integer array [insert array], what will be the contents of the array after a single (Quicksort) partition operation with [insert integer] as the pivot?
• Write the top-level Quicksort algorithm in pseudocode. You can assume that a partion method has already been written.
• What is the "median of three" method for choosing a pivot for Quicksort?

State spaces and heuristic search

• Define "state space."
• Define "heuristic."
• Define "best first search."
• Define "blind search."
• What does it mean to say that a heuristic is "optimistic"?
• When searching a state space, what is the single most important way to minimize the size of the state space?
• In the A* algorithm formula f(N) = g(N) + h(N), what are N, g, h, and f?
• Is the A* algorithm a best-first search technique? If so, how? If not, why not?
• Under what circumstances will A* find a best solution?
• What are the space requirements for an A* search?
• How does IDA* differ from an iterative deepening search?
• What are the space requirements for an IDA* search?

Pruning

• If a problem is classified as "intractable", what is its big-O running time?
• What is the "sum of subsets" problem?
• What is the "Boolean satisfaction" problem?
• How would you characterize the "sum of subsets" problem as a state space search?
• How would you characterize the "Boolean satisfaction" problem as a state space search?
• What approach usually helps maximize the amount of pruning that can be done?

Effective programming

• Define "refactoring."
• Define "regression testing."
• When does Antoine de Saint-Exupery feel that perfection has been achieved?
• What does your instructor say is the "highest praise you can give to a program"?
• When should you not add features to a program?

Storage

• What does it mean to say that a programming language is "strongly typed"?
• What does it mean to say that a programming language is "weakly typed"?
• If all storage is statically allocated, can you do recursion? Why or why not?
• What space is allocated, and where is it allocated, by the Java statement Dog fido = new Dog() ?
• Why is heap storage more difficult to manage than stack storage?
• Freeing (de-allocating) storage can lead to two kinds of errors.
  • Freeing storage while it is still in use results in ___________________________.
  • Failing to free storage that can no longer be accessed results in ___________________________.
• Instead of expecting the programmer to deallocate unused storage, Java uses a(n) ___________________________.
• Name two main techniques for doing garbage collection, and mention one disadvantage of each technique.
• Briefly describe the "reference counting" algorithm for garbage collection.
• Briefly describe the two passes of a mark and sweep algorithm.
• Why is it essentially impossible to implement a garbage collector for C++?

Spanning Trees

• Define "spanning tree" of an undirected graph.
• Write a pseudocode algorithm to find a spanning tree of an undirected graph.
• If an undirected graph has N nodes and E edges, how many nodes and edges are in a spanning tree of that graph?
• If an undirected graph has N nodes and N edges, how many different spanning trees are there for that graph? (Hint: give a range of values.)
• What is the basic idea of Kruskal's algorithm?
• What is the basic idea of Prim's algorithm?
• Why is Kruskal's algorithm much harder to implement efficiently than Prim's algorithm?
• [Not for the exam!] We have not defined "spanning tree" for a directed graph.Why not? Can you come up with a comparable concept for directed graphs?

Sparse Arrays

[This lecture was primarily intended as an example of using linked lists, so there's not much I want to ask.]

• How would you implement a sparse two-dimensional array using a hash map (or a small number of hash maps)?
  • With your implementation, how would you:
    • Index into the array to store and fetch values?
    • Find all the values in a given row?
    • Find all the values in a given column?

Preferences

• Define "persistent" information.
• Name the two types of preference information supported by java.util.prefs.*.
• A simple Preferences object behaves like what well-known data structure?
• In the Preferences method get(key, xxx), what is the second parameter used for?
• If you have Preferences objects for several different programs, how does Java know which one to use?
• In what format is the Preferences file stored?
• What happens if you remove a preference from a Preferences object, then later ask for the value of that preference?

Hypergraphs

• Mention three ways in which a hypergraph might extend the notion of a graph.
• What are the fields in a Plex?
• What validity rules apply to the fields of a Plex?
• If a Plex implements a node in a regular (non-hyper) graph, what are the contents of each field of that Plex?

Alpha-Beta Searching

• In the following game tree [insert image with values on the leaves], it is your turn to move. Fill in the backed-up values and indicate what moves will be made.
• Alpha-beta searching is based on what two assumptions?
• As you minimax on a game tree, the PBV at the node you start from (where it is your move) will never ____________.
• As you minimax on a game tree, the PBV at a node where it is the opponent's turn will never ____________.
• Do a preorder search of this game tree [insert image with values on the leaves] and indicate where any alpha cutoffs occur.
• To maximize the amount you can prune a game tree, in what order should you explore nodes?

Regular Expressions

• What are the three ways in which a regular expression can be applied to a string?
• Write a regular expression that will match:

  • any digit	• zero or more digits	• any letter
  • any non-digit	• one or more digits	• any lowercase letter
  • an optional digit	• two or more digits	• any non-letter
  • an optional non-digit	• any character except a newline	• either "abc" or "xyz"
  • any three-digit sequence	• the word "cat" in any mixture of uppercase and lowercase letters	• Any one character except a letter

• What two classes do you need to work with regular expressions in Java?
• In the regular expression [insert regular expression], tell what part of the expression is included in each capturing group (including group zero).
• In Java, a regular expression is usually represented as a quoted string. Why does this cause difficulties?

Platforms

• What is a JIT compiler?
• What problem does .NET try to solve?
• What is the .NET equivalent of Eclipse?
• What is the .NET equivalent of bytecode?

Images

• What image formats can Java display?
• What kind of object can load images and wait for them to finish loading?

Miscellaneous

• What is a "shallow copy" of an object?
• What methods are declared by the Cloneable interface?
• What is a "copy constructor"?
• Why is it often better to write a copy constructor than to have a class implement Cloneable?
• What is a "circular array"?
• Define "entropy."
• Define "heuristic function."
• Pseudorandom numbers are usually generated by the linear congruential method.
  • What is the formula used in this method?
  • What are the restrictions on the input numbers?
• What is another name for a Gaussian distribution?
• It's usually a good idea to put the word static in front of Random random = new Random(). Why?
• What does the javap command do?