(3 points) Tell whether each of these specifies a lower bound, upper bound,
or exact bound:
Big-O specifies a(n) upper bound.
Big-Θ specifies a(n) exact bound.
Big-Ω specifies a(n) lower
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.)
What advantage does Java's TreeMap have over HashMap? Keeps keys in order
What advantage does Java's HashMap have over TreeMap?
Faster
(4 points) What are your instructor's four rules for writing
a recursive method? Do the base case(s) first.
Recur only with a simpler case.
Don't both modify and examine a global variable.
Don't look down.
(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.
It's either an array OR a genericized type that defines
the Iterable interface.
It contains Pet objects.
(3 points) In which Java package would you expect to find:
a method for sorting an array? java.util
a method for appending two Lists? java.util
a method for testing whether a file exists? java.io
(1 point) When should you use Comparator rather than Comparable? When you may want to compare (or sort) along different
dimensions.
(8 points) Consider the following binary tree:
Is this a sorted binary tree? No
Why do you think it's sorted (or not sorted)?
N > A
In what order will the nodes of this binary tree be visited:
In preorder? D A N
E R
In inorder? N A D
E R
In postorder? N A
R E D
In what order will the nodes be examined by each of the following:
A breadth-first search? D
A E N R or D E A R N or D
A E R N or D
E A N R
A depth-first search? D
A N E R or D E R A N
A depth-first iterative deepening search? D
D A E D A N E R or D
D E A D E R A N
(1 point) If you override hashCode(), you must also override
equals(Object).
(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?
Brute force
How long will his program take? O(n!) (equivalently,
O(2^{n}))
(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? Greedy
How long will her program take? O(n^{2})
(14 points) Briefly define each of the following. Do not give examples.
mutative transformer A
method that changes the object to which it is applied
weakly connected (digraph) The
underlying undirected graph is connected
factory method A method
that returns (or may return) a new object
heap property The
value in a node is not less than (or not greater than) the values in either
child
blind search A search
with no information as to where a goal may be
collision Two or more
objects hash to the same location
checked exception An
Exception that must be caught or declared as thrown
(2 points) The A* search method is a kind of best -first
search. It uses the formulaf(n) = g(n) + h(n);
in this formula, what is the meaning of n? A node on the path from the root to a possible goal
(2 points) What are the two most important differences
between a Set and a List in Java? A set is unordered and has no duplicate elements
(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 = 0 B = 10 C = 11 [ or A = 1 B = 01 C = 00
]
(1 point) Suppose a class definition begins as follows: public class Person {
String name;
GregorianCalendar
dateOfBirth;
int age;
...
What style rule does this violate? DRY
(Don't Repeat Yourself) (I forgot to make these private, so that's another acceptable
answer...)
(1 point) A heap (as in heapsort) is useful in implementing what
ADT? A priority queue
(3 points) Using Java's generics,
Declare a HashMap named map whose keys are
Strings and whose values are Doubles. HashMap<String, Double> map;(ok
if includes assignment, = new HashMap<String, Double>() )
Write an "enhanced for loop" to find the total of the values
in this HashMap.
double total = 0.0;
for ( String
key : map.keySet( ) ) {
total = total
+ map.get(key);
}
(1 point) A maze can be created by finding a(n) spanning
tree of a graph.
(1 point) An algorithm is considered intractable if it requires exponential time.
(1 point) What is the relationship between an alpha cutoff and a beta cutoff? A beta cutoff is an alpha cutoff as seen from the opponent's
point of view.
(1 point) If an adjacency matrix is symmetric about the main diagonal,
what does this imply about the digraph that it represents? Every edge has a parallel edge in the opposite direction.
(1 point) Which digraph representation is more generally useful, an adjacency
set representation, or an edge set representation? (Don't explain
why.) An adjacency set representation.
(1 point) In class I described how to build a maze. For an NxN maze,
what is the running time of this algorithm? O(N^{2})
(3 points) sin = opp/hyp, cos
= adj/hyp , tan =
opp/adj.
(1 point) What can you do with a "pointer" that you can't do with
a "reference"? Pointer arithmetic
(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 subset
.
addAll(Collection c) corresponds to union
.
removeAll(Collection c) corresponds to set
difference .
retainAll(Collection c) corresponds to intersection
.
(3 points) An Abstract Data Type specifies these two things:
The set of possible values
The set of available operations
but does not specify:
The implementation
(1 point) If you get a "Concurrent modification exception," what
have you probably done wrong?
You modified a collection while it was being iterated
over.
(12 points) True or false:
False A hashCode(
) method must return different values for different objects.
True The split(String)
method in String takes a regular expression as its parameter.
True The trig functions
(sin, cos, tan) expect their arguments
to be in radians.
True The Stack
class extends Vector.
True A method may have
at most one vararg parameter.
False The java.util
package defines Stack and Queue classes.
True Genetic algorithms
work better with sexual, rather than asexual, reproduction.
False Genetic algorithms
work best with a moderate to large probability of mutation.
True Mutation in genetic
algorithms helps combat lack of genetic diversity.
True State-space searches
should be designed with as few operators as possible.
True Backtracking is basically
depth-first tree searching.
True 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? Replace the stack with a queue
(3 points) When you need to time a method, tell three things
you can do to improve the accuracy of the timing. Close as many other applications as possible.
Request garbage collection before doing the timing.
Repeat the test many times and take the average.
[Acceptable: Use nanoTime() rather than currentTimeMillis())