| . | |
| What
is the result (the contents of the stack) after this sequence of
operations has executed (starting from an empty stack)? When
giving your result, be sure to label the stack to indicate which end is
which. |
push(2) push(2) pop() top() push(3) pop() push(4) push(5) |
|
|
|
| . | |
| What is the result (the contents of the queue) after this sequence of operations has executed (starting from an empty queue)? When giving your result, be sure to label the queue to indicate which end is which. | enqueue(2) enqueue(2) enqueue(3) dequeue() dequeue() enqueue(4) enqueue(5) dequeue() dequeue() |
|
|
|
| . | |
| Let
S={a,b,c} and R={(b,c), (c,c), (a,c)}. Is R reflexive or
symmetric? |
A.
is reflexive only B. is symmetric only C. is both reflexive and symmetric D. is neither reflexive nor symmetric |
|
|
|
| . | |
| Same
set and relation as above. Is R a function? If your answer is yes, give the domain of the function. |
A.
yes B. no Domain (if yes): |
|
|
|
| . | |
| Let S={x,y,z,w} and R={(x,y),
(y,x), (z,w), (w,z), (y,y), (w,w)}. Determine whether R is
transitive, then choose a true statement |
A.
R is not transitive, but can be made transitive by adding a single pair
to the relation B. R is not transitive, but can be made transitive by adding at least two pairs to it. C. R is not transitive, and cannot be made transitive no matter how many pairs are added. D. R is already transitive |
|
|
|
| . | |
| Let us say that two Java classes A
and B are related (A,B) if there is an interface I that both A and B
implement. Is this an equivalence relation? Explain. |
|
|
|
|
| . | |
| Is
it true that 2*n is O(n+2)? Either show why it is by giving an n0 and c which satisfy the Big-O definition, or explain why it is not. |
|
|
|
|
| . | |
Rank
these functions in order of their asymptotic (Big-O) complexity, with
#1 being the best. Then read and answer the question on the right.
|
#2
on your ranked list is (circle): A. B. C. D. E. |
|
|
|
| . | |
| Same functions as in previous
question |
#4
on your ranked list is (circle): A. B. C. D. E. |
|
|
|
| . (worth 4 M.C. questions) | |
We might say that word (string) A
expands
word B if A
"pitt" expands "tip", "ease" expands "sea", but "sea" does not expand "as" (contains a letter not in "as") "tippi" does not expand "pitt" (needs to have at least 2 t's) "lima" does not expand "mail" (not longer) |
Give
an algorithm to determine whether A expands B. Try to make it
efficient in the Big-O sense. Give your algorithm in pseudo-code
or in something close to real Java. (You can have an extra sheet
of paper if you need it). You may assume that all the characters in any word are lower-case letters. |
|
|
|
| . (worth 2 M.C. questions) | |
| Regarding
your algorithm for determining if a word A expands a word B: |
What
would be an appropriate parameter for the complexity function? What is the asymptotic complexity? Justify or explain why you think so. |
|
|
|
| . (worth 3 M.C. questions) | |
| Complete
the Java method hasDupPair using only recursion (no for or while).
You may create a helper method if desired. |
/**
Determine whether an array of numbers has two consecutive values that
are the same. @param nums an array, which might be empty or null. @return true iff the array has two consecutive identical values. */ static boolean hasDupPair(int[] nums) { |
|
|
|