1. after the third iteration of insertion sort

   527

   620

   884

   909

   32

   927

   276

   411

   322

   445

2. after the third iteration of selection sort

   32

   276

   322

   620

   884

   927

   909

   411

   527

   445

3. after the third merge in a merge sort.

   884

   909

   32

   527

   620

   927

   276

   411

   322

   445

   OR

   527

   884

   909

   32

   620

   927

   276

   411

   322

   445

4. after the first iteration of radix sort.

   (SORRY! We didn't do radix sort this year!)

5. after being 3-sorted with Shell sort (i.e. gap = 3)

   276

   32

   322

   445

   411

   527

   620

   909

   927

   884

1. Circle the values would we consider for the pivot ...
   76, 80 and 37
2. Which of those values would we end up choosing as the pivot?
   76
3. What position would the pivot value end up ...
   7
4. Given the partition above, what are the bounds ...
   Lower sub-array: from index __0_ to index __6_.
   Upper sub-array: from index __8_ to index _10_.

1. O(N³)
2. O(N²)
3. O(N³)
4. O(N log N)
5. O(N²)
6. O(N⁴)

public int getFrequency(T item) {
    int count = 0;
    Node cur = first;
    while (cur != null) {
        if (cur.data.equals(item)) {
            ++count;
        }
        cur = cur.next;
    }
    return count;
}

public int Q(int n) {
    if (n < 3) {
        return n;
    } else {
        return Q(n – Q(n-1)) + Q(n – Q(n-2));
    }
}

public interface MyADT {
    public void showValues();
    public boolean hasZeroValue();
    public int getZeroLocation();
    public double solve(int location);
}

1. Move Move Move
2. Move Enqueue Move Dequeue
3. Enqueue Move Dequeue Move
4. Enqueue Move Move Dequeue
5. Enqueue Enqueue Move Dequeue Dequeu
6. Cannot be done

public static <T extends <? super T>> T maxElement(T[] arr) {
    T result = arr[0];
    for (int i = 1; i <= arr.length; ++i) {
        if (result.compareTo(arr[i]) > 0) {
            result = arr[i];
        }
    }
    return result;
}

• d) ... throws MyException
• e) ... m instanceof Circle
• b) ... extends Box
• d) Yellow
• e) 42, 21, 27, 22.
• c) ... deletions/insertions in the middle of the list.
• e) shared by all objects of the class it’s declared in.
• e) int compareTo(T other)
• b) O(log N)
• b) void actionPerformed(ActionEvent e)
• b) print an error message.
• d) 1,000,000,000,000 and 20,000,000.