CIT
594 Exam Questions Spring 2007, David Matuszek |

I have added some questions to groups in **bold**. The new groups are
after the horizontal line. The first topic not covered in the midterm
exam is Backtracking.

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

} - In your ExpressionEvaluator assignment, I said to add a
`'$'`

to the end of the input string. Why? - 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()`

?

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

- 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`

`singleton`

- If you implement an interface, you have to implement every method described
in that interfacc. 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?

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

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

- 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

andString name

, and you putint age `Employee`

objects into a`SortedSet`

. Will the employees be sorted by name, or by age? - Suppose you have a class
`Employee`

with a field

, and you putlong id `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?

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

- 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`String`

s as keys and`Double`

s 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"?

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

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

- Declare and define a Java variable named
`stuff`

as an`ArrayList`

containing`String`

s. - Declare and define a Java variable named
`stuff`

as an`ArrayList`

containing a`List`

of`String`

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

andnew ArrayList<Object>()

?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)`

?

- 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`double`

s. - Write a
*recursive*method named`sum`

to return sum of an array of`double`

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

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

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

- True or false: Arrays are objects.
- Define "subarray."
- If we define

, what is the type ofint myArray[][] = new int[3][8] `myArray[1]`

? - If we define

, what value is inint myArray[][] = new int[3][8] `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?

- 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`

?

- Why should the links to the left and right child be
- 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)?

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

- Simplify:
`O(3n`

.^{4}- 6n^{2}+ 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(2`

.^{n}), O(n^{2}), O(n^{2}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
`log`

, then_{2}N = x`N =`

_______.

- Given a complexity function f(n), give
*informal*definitions for:- O(f(n))
- Θ(f(n))
- Ω(f(n))

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

- If you implement
- What is wrong with the following, and how would you fix it?

`SortedSet<Object> set = new SortedSet<Object>();`

- 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

with a constructorclass MyList { int value; MyList next; ...}

: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

with a header cellclass MyList { int value; MyList left, right; ...} `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.

- In order to insert
`Book`

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

- 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

that will recognize aboolean addOp() `"+"`

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.

- Write a method
- In a recognizer, when must you report an error rather than simply returning
`false`

?

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

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

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

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

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

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

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

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

- 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

, what aref(N) = g(N) + h(N) `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?

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

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

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

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

[This lecture was primarily intended as an

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

- With your implementation, how would you:

- 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

, what is the second parameter used for?get( *key*,*xxx*) - 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?

- 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`

?

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

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

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

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

- 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

. Why?Random random = new Random() - What does the
`javap`

command do?