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

    1.  0 5
      
    2.  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