Name: ________________________________
Section: ____________

CSE373 Winter Quarter
University of Washington
Midterm #1 with answers and notes
January 28, 2005
Closed book, closed notes, closed neighbor; no calculators
2 points per part except as noted

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

2   4   5 (top)
"Top" is the label used with stacks.  We don't normally have any reason to refer to the bottom.  You sometimes hear "front" instead of "top".
 
.
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()
5 (front and rear both)
You need two labels.  "front" or "next out" or "head" is one, and "rear" or "back" or "last in"  is the other.
 
.
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
D.
Not reflexive, e.g. (a,a) is missing
Not symmetriic, e.g. (b,c) but not (c,b)
 
. 
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):
Yes.  For each pair, the first value of the pair does not occur as the first in any other pair.
The domain could be given as S or as {a,b,c}
 
.
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
B.
R is not transitive, e.g., (x,y) and (y,x) are in the relation, but (x,x) is not.
Likewise, (z,w) and (w,z) are in the relation, but (z,z) is not.  So at least two pairs must be added to R to make it 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.
No.  An equivalence relation must be reflexive, symmetric, and transitive.  The relation is reflexive and symmetric, but not transitive.  If (A,B) is a pair in the relation because A and B both implement some interface I1, and (B,C) is a pair because of I2, it is not necessarily true that I1 and I2 are the same interface, so (A,C) is not necessarily a pair.  Java allows classes to implement multiple interfaces (but classes can only extend one class).


.
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.
Yes. 
2*n <= 2*n + 4 = 2*(n+2)
for any n >= 0.
So the definition can be satisfied with n0 = 0, c = 2.

Some people gave n0 = 2 and c = 1 because it is true that
2*2 <= 1*(2 + 2.)
However, the definition requires the inequality to hold for ALL n >= n0. If you try it for n = 3, you find that
2*3 > 1*(3 + 2).
   
.
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.
  • A. 3*n*log(n)
  • B. (3n)/2
  • C. 410
  • D. 20 + n3 -5n
  • E. log(n) + 2*n
 #2 on your ranked list is (circle):
A.
B.
C.
D.
E.
#1 C
#2 E
#3 A
#4 D
#5 B

So E for this question
  
.
Same functions as in previous question
 #4 on your ranked list is (circle):
A.
B.
C.
D.
E.
D

. (worth 4 M.C. questions)
We might say that word (string) A expands word B if A
  • is longer than B
  • contains only letters that are in B
  • contains at least as many of each letter as B contains
 So,
"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) {
Common errors:
missing the null base case
off-by-one errors on the non-null base case
passing an element rather than the array
not using the value returned from the recursive call
assuming that arrays have methods like .remove, etc.

You can do it without a helper method, but not easily.

Coming soon: a compilable sample solution


[end of test]