(8 points) Tell the running time of each of the following algorithms:
__________ Bubble sort
__________ Selection sort
__________ Insertion sort
__________ Binary search (when unsuccessful)
__________ Heapsort
__________ Quicksort (worst case)
__________ Creation of a Huffman tree
__________ Dijkstra's shortest-path algorithm
(3 points) Tell whether each of these specifies a lower bound, upper bound,
or exact bound:
Big-O specifies a(n) ____________________ bound.
Big-Θ specifies a(n) ____________________ bound.
Big-Ω specifies a(n) ____________________ bound.
(4 points) We will define a "word" to consist of one or more syllables.
Each syllable consists of one or two consonants followed by a vowel, except
that the first syllable may be a single vowel and the last syllable may end
with a single consonant. Assume that the terms <vowel>
and <consonant> have already been defined (i.e. don't write
them yourself), use BNF (or EBNF) to define a <word>. Example
words: a, at, kokomo, tokamak,
ashanti. (Hint: Use scratch paper, and copy your answer to the
exam.)
(2 points)
What advantage does Java's TreeMap have over HashMap?
What advantage does Java's HashMap have over TreeMap?
(4 points) What are your instructor's four rules for writing
a recursive method?
(2 points) Suppose in a (correct) Java program you find the line for (Pet pet : pets) {
tell everything you can deduce about the pets variable.
(3 points) In which Java package would you expect to find:
a method for sorting an array?
a method for appending two Lists?
a method for testing whether a file exists?
(1 point) When should you use Comparator rather than Comparable?
(8 points) Consider the following binary tree:
Is this a sorted binary tree?
Why do you think it's sorted (or not sorted)?
In what order will the nodes of this binary tree be visited:
In preorder?
In inorder?
In postorder?
In what order will the nodes be examined by each of the following:
A breadth-first search?
A depth-first search?
A depth-first iterative deepening search?
(1 point) If you override hashCode(), you must also override
_____________________.
(2 points) Jack has the job of assigning n tasks to n
people (one task per person). Each person has told Jack how happy he/she
would be (on a scale of -1.0 to +1.0) to do each task. Jack wants to maximize
the total happiness, so he writes a program that tries every possible assignment
of tasks to persons, and chooses the best.
What is the name for the kind of algorithm Jack is using?
How long will his program take?
(2 points) Jill has the same problem as Jack (above), but her program finds
the best (happiest) matching of some one person to a task and assigns it,
then repeats the same process with the remaining persons and tasks, until
none are left.
What is the name for the kind of algorithm Jill is using?
How long will her program take?
(14 points) Briefly define each of the following. Do not give examples.
mutative transformer
weakly connected (digraph)
factory method
heap property
blind search
collision
checked exception
(2 points) The A* search method is a kind of ____________-first search.
It uses the formulaf(n) = g(n) + h(n);
in this formula, what is the meaning of n?
(2 points) What are the two most important differences
between a Set and a List in Java?
(3 points) Messages are composed of the letters A, B,
and C. On average there are ten times as many As
as Bs, and ten times as many Bs as Cs.
(For example, a message might start out as AAAAAAABAAA...). What
is a suitable Huffman code for these messages?
A = B = C =
(1 point) Suppose a class definition begins as follows: public class Person {
String name;
GregorianCalendar
dateOfBirth;
int age;
...
What style rule does this violate?
(1 point) A heap (as in heapsort) is useful in implementing what
ADT?
(3 points) Using Java's generics,
Declare a HashMap named map whose keys are
Strings and whose values are Doubles.
Write an "enhanced for loop" to find the total of the values
in this HashMap.
double total = 0.0;
for ( ) {
total = total
+
}
(1 point) A maze can be created by finding a(n) _________________________
of a graph.
(1 point) An algorithm is considered intractable if it requires __________________
time.
(1 point) What is the relationship between an alpha cutoff and a beta cutoff?
(1 point) If an adjacency matrix is symmetric about the main diagonal,
what does this imply about the digraph that it represents?
(1 point) Which digraph representation is more generally useful, an adjacency
set representation, or an edge set representation? (Don't explain
why.)
(1 point) In class I described how to build a maze. For an NxN maze,
what is the running time of this algorithm?
(3 points) sin = ------------ , cos = ----------- ,
tan = ------------ .
(1 point) What can you do with a "pointer" that you can't do with a "reference"?
(4 points) Each of the following Collection methods corresponds
to a mathematical operation on sets. Give the names of the corresponding mathematical
operations.
containsAll(Collection c) corresponds to ______________________________
.
addAll(Collection c) corresponds to ______________________________
.
removeAll(Collection c) corresponds to ______________________________
.
retainAll(Collection c) corresponds to ______________________________
.
(3 points) An Abstract Data Type specifies these two things:
but does not specify:
(1 point) If you get a "Concurrent modification exception," what
have you probably done wrong?
(12 points) True or false:
_____ A hashCode( ) method must return different values
for different objects.
_____ The split(String) method in String takes a regular
expression as its parameter.
_____ The trig functions (sin, cos, tan)
expect their arguments to be in radians.
_____ The Stack class extends Vector.
_____ A method may have at most one vararg parameter.
_____ The java.util package defines Stack
and Queue classes.
_____ Genetic algorithms work better with sexual, rather than asexual,
reproduction.
_____ Genetic algorithms work best with a moderate to large probability
of mutation.
_____ Mutation in genetic algorithms helps combat lack of genetic diversity.
_____ State-space searches should be designed with as few operators
as possible.
_____ Backtracking is basically depth-first tree searching.
_____ Breadth-first searches usually require more memory than depth-first searches.
(1 point) How can you easily turn a nonrecursive depth-first search
into a breadth-first search?
(3 points) When you need to time a method, tell three things you can do to improve the accuracy of the timing.