Exam 1 Sample Questions
  1. log_2 8 = ?
    Answer: 3

  2. log_b a * log_a b = ?
    Answer: 1

  3. What does it mean to say that f(n) dominates g(n)?
    Answer: f(n) > cg(n) for all n >n_0 c,n_0 > 0

  4. f(n) = 3n^2 + 2n + 13
    f(n) is in O(?)
    Answer: n^2

  5. Is f(n) = sqrt(n^5) in O(n^2)?
    Answer: No because 2.5 > 2

  6. How does Big-Theta differ from Big-O?
    One possible answer: Big-Theta is a tight bound, while Big-O is an upper bound.

  7. If f(n) is in O(n) and g(n) is in O(n),
    then (f(n) - g(n) ) in O(?)? Answer: Also O(n)

  8. Give a running time (T_n) for the following code fragment : 
    	for (int i = 0; i < n ; i ++){
	   for (int j=0; j < n; j++){
		loop body
	   }
	}
    Answer: T_n = cn^2

  9. T_n = 4T(n/3) + n^2. Solve for the asymptotic running time using the "Master Method".
    Answer:
    a = 4, b = 3, e = 2, so T(n) is in O(n^2).

  10. Write the pop() method for the contiguous-memory implementation of a stack.
    One possible answer:
    Assume instance variables
int length;
int maxSize;
someType thisStack[] = new thisStack[maxSize];


retType pop(){
  if (length() == 0)
	underflow_error()
  else{
   return thisStack[length--];
  }
}