CS35: Quiz 5 Study Guide

In addition to all concepts from Quiz 1, Quiz 2, Quiz 3, and Quiz 4.

You should be able to define or explain the following terms:

You should be familiar with the following C++-related concepts:

Practice problems

  1. For each of the code fragments below, draw the BinaryHeap that results from the code fragment, and draw its final array-based representation:
    1.   BinaryHeap<int,int> heap;
        for (int i = 1; i <= 10; ++i) {
          heap.insert(i,i);
        }
        for (int i = 1; i <= 5; ++i) {
          heap.removeMin();
        }
      
    2.   BinaryHeap<int,int> heap;
        for (int i = 10; i > 0; --i) {
          heap.insert(i,i);
        }
      
    3.   BinaryHeap<int,int> heap;
        for (int i = 1; i <= 5; ++i) {
          heap.insert(i,i);
          heap.insert(-1*i,-1*i);
        }
      
  2. What is the worst-case running time of the following function? Use Big-O notation.
      void f(int n) {
        if (n < 0) {
          return;
        }
        BinaryHeap<int,int> heap;
        for (int i = 0; i < n; ++i) {
          heap.insert(i,i);
        }
        for (int i = 0; i < n; ++i) {
          cout << heap.removeMin() << endl;
        }
      }
    
  3. Using linear chaining to resolve hash collisions, insert the following five items into a hash table of capacity 5, in the order given (from top to bottom):
    KeyHash code
    A1
    B1
    C1
    D0
    E2
  4. Repeat #3 using linear probing to resolve hash collisions, instead of chaining.
  5. Consider the following hash function, like the function in hashtable.inl:
      int hash(int key, int capacity) {
        return key % capacity;
      }
    
    Assuming that the hash table does not resize, complete the following code so that the total running time is asymptotically proportional to n^2:
      void f(int n) {
        HashTable<int,string> ht(n);  // Creates hash table with capacity n.
        for (int i = 0; i < n; ++i) {
    
          ht.insert(________________, "skittles");
        }
      }