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

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

• Priority queue abstract data type
• Analysis of priority queue implementations using sorted lists, unsorted lists, binary search trees, and binary heap trees
• Binary heap and the heap operations
• Complete binary trees and their array-based representation
• The heap-order property
• Using bubble up and bubble down to restore heap-order property
• Sorting with a heap
• The conceptual overlaps and differences between trees, BST, AVL, priority queues, heaps, and graphs
• Containers of containers; that is, how data structures can contain other data structures as elements
• The Dictionary abstract data type
• Generalized indexing (i.e., [] operator)
• Collisions, mapping and compression
• Hash tables, hash functions, hash code, a hash table's load factor
• Importance of hash functions, load factors, capacity, etc in performance
• Linear chaining and linear probing
• Tradeoffs between BST and HashTable dictionary representations
• Various strategies for handling keys (e.g., allowing duplicates in priority queues vs unique keys in BST and Dictionaries)
• graph, vertex, edge
• directed, undirected graphs
• weighted, unweighted graphs
• adjacent, neighbor, outgoing edges, incoming edges, out-degree, in-degree, degree

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

• vectors and their functions, particularly those related to the List interface
• valgrind
• testing strategies
• A Pair object
• Expanding capacity in CircularyArrayLists vs BinaryHeap vs HashTable

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):

   Key	Hash code
   A	1
   B	1
   C	1
   D	0
   E	2



4. Repeat 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");
       }
     }