NAME:



Midterm Exam		 COS 226 Solutions, Spring 2011
  1. Partitioning 
    A. E E A E Y R Q U E L K V Y S T O P S I T
        4 exchanges

B. c. To avoid quadratic running time.

C. A E E E E Q U Y L K R Y S T O P S I T V
        16 exchanges
  2. Estimating order of growth 
    A. N²

B. log ( y / x)  - Note: this is log base 10.
  3. Sorting algorithms
    sorted order reverse order
    Quicksort linearithmic linearithmic
    Heapsort linearithmic linearithmic
    Insertion sort linear quadratic
    Selection sort quadratic quadratic
    Shellsort linearithmic
    ?
  4. Tree height
    best case worst case
    BST log N N
    Heap-ordered complete tree log N log N
    Left-leaning red-black tree log N log N
    quick-union with path compression 1 N
    weighted quick-union 1 log N
  5. LLRB insertions 

    2.  0 5

    3.  3 7 2 8 6 1 5
  6. Heap operations


  7. Linear probing 

    1.  N C T I O   B A D F U
 0 1 2 3 4 5 6 7 8 9 10
      1. linear
      2. linear
      3. quadratic
      4. quadratic (need to check for duplicates)

  8. 7 sorting algorithms 
    D E A G B C F

  9. Maximum difference 
    1. if (a[k] - min > max) max = a[k] - min 
if (a[k] < min) min = a[k]

    2. quadratic
linear