Exam 1

  1. Find the closed form of the following recurrence relation.  What is the asymptotic behavior of T in Big Oh notation?
    T(0) = 1
    T(1) = 2
    T(k) = 2T(k-1) + 3T(k-2) + 1
  2. For the following algorithm, find a recurrence relation which describes the best-case runtime.  What is the runtime complexity in Big Oh notation?
    function foo(arr)
      for i = 1 -> len(list) do      (2 s)
        for j = 1 -> len(list) do    (2 s)
            if arr[i] < arr[j] then  (1 s)
              swap(arr[i], arr[j])   (4 s)
  3. Explain why the algorithm in question 2 above could be considered a "selection sort".
  4. Assume a single-linked list is composed of nodes with "next" pointers.  Write C/C++ code to remove node "p":
    void remove(node *p) {
  5. What is the runtime complexity of remove(pos) for a dynamic array (e.g. std::vector)?  Explain why.
  6. What data structure would you use to implement a queue?  Why?
  7. What data structure would you use to implement a stack?  Why?
  8. Say you are writing a program to keep track of attendance in a class.  What data structure would you use to keep track of the students who attended for a given day?  How much memory does your data structure need?  What operations do you need and what are their runtime complexities?
  9. Use Bubble Sort on the following list of integers.  Show each swap.  How many swaps are required?
    1 4 5 3 2 7
  10. Imagine a magic black box (an "oracle") which somehow computes the optimal quicksort pivot in constant time.  Explain why this is impossible for muggle machines.