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 premidterm and postmidterm, 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 Sunsupplied classes, and which are
Sunsupplied interfaces?
 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 singlylinked 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 Sunsupplied 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 settheoretic 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 Sunsupplied 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 Sunsupplied 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
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 keyvalue 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 Sunsupplied 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 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
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 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.
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 evennumbered rows all have
10 elements and the oddnumbered 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 Sunsupplied 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(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 (BigO
notation) do you expect this method to take?
 How fast (BigO 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_{2}N = x
, then N =
_______.
 Given a complexity function f(n), give informal definitions for:
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 singlylinked 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 doublylinked 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
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 Javaprovided 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 welldesigned hash map, how long (BigO 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 (BigO 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 depthfirst search on a
balanced binary tree?
 What are the space requirements for doing a breadthfirst search on a
balanced binary tree?
 What is the main advantage of a breadthfirst search over a depthfirst
search?
 The algorithm for doing an iterative breadthfirst search is identical
to that for an iterative depthfirst 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 depthfirst search?
 Given the following tree [insert picture], in what order will the nodes
be visited during a breadthfirst search?
 Given the following tree [insert picture], in what order will the nodes
be visited during a depthfirst iterative deepening search?
 Is a depthfirst 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 depthfirst search than a recursive
breadthfirst 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 depthfirst 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 toplevel 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 bestfirst 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 bigO 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 SaintExupery 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 (deallocating) 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 twodimensional 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 wellknown
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 (nonhyper)
graph, what are the contents of each field of that Plex
?
AlphaBeta Searching
 In the following game tree [insert image with values on the leaves], it
is your turn to move. Fill in the backedup values and indicate what moves
will be made.
 Alphabeta 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 nondigit 
• one or more digits 
• any lowercase letter 
• an optional digit 
• two or more digits 
• any nonletter 
• an optional nondigit 
• any character except a newline 
• either "abc" or "xyz" 
• any threedigit 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?