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

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

(Note: you only have to know the big picture when it comes to Priority Queues and Heaps. We know you just handed in a lab on this and it has not been graded yet, so there will not be any deep question about them in the test)

• Induction
• Loop Invatiants
• Trees and many related terms and properties, including nodes, the root node, leaf nodes, internal nodes, parent, child, path, depth of a node, subtree, height of a tree
• Compare and contrast linear data structures with trees
• Tree traversals: pre-order, in-order, post-order, and level-order traversals
• Binary tree
• Binary search trees and the BST property
• Dictionaries (generally)
• AVL trees and the AVL tree property
• Tree rotations
• The recursive definition of binary trees, binary search trees, and AVL trees
• 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
• The Complete binary tree property
• Using bubble up and bubble down to restore heap-order property
• Sorting with a priority queue
• The conceptual overlaps and differences between trees, BST, AVL, priority queues, heaps
• Containers of containers; that is, how data structures can contain other data structures as elements
• Run time analysis of public interface for LinkedBST, AVLTree, and BinaryHeap
• Run time analysis of helper methods as well for LinkedBST, BinaryHeap

Practice problems

1. Induction Prove the following sums by induction:
   1. \(\sum\limits_{i=1}^{n} i \cdot 2^i = 2^{n+1}(n-1) + 2\)
   2. \(\sum\limits_{i=1}^{n} \frac{3}{4^i} = 1 - (\frac{1}{4})^n\)
2. Loop Invariants. For each of the following algorithms, prove the algorithm is correct by using a loop invariant. First, explicitly state the loop invariant. Then, show how the loop invariant implies the algorithm works. Finally, prove the loop invariant using induction.
   1. adding all elements of a list

              Algorithm sum(A, n):
              Input: An array of n numbers
              Output: The sum of all elements in the array
      
              toReturn = 0
              for i=0...n-1
                 toReturn = toReturn + A[i]
              return toReturn
            

   2. checking to see if an array is sorted

              Algorithm isSorted(A, n)
              Input: An array A of n elements
              Output: true if A is sorted, false otherwise
      
              for i =0...n-2:
                 if(A[i] > A[i+1]):
                    return false
              return true
            

   3. searching for an element in a sorted array.

              Algorithm binarySearch(A,n, x):
              Input: A sorted array of size n, an element of x we wish to find
              Output: Position of x, or -1 if not found
      
              low=0, high=n-1
              while(low <= high):
                 mid = (low+high)/2
                 if(A[mid] == x) :
                    return mid
                 else if (A[mid] < x):
                    low = mid+1
                 else:
                    high = mid-1
              return -1;
            

3. For each data structure covered in the course, come up with a real-world application that motivates the data structure. The data structure should be able to provide a more efficient solution to the problem then any other structure covered so far.


4. Give a binary tree with integer keys at nodes, whose traversals are:
   • PreOrder: [80 46 92 90 121 111 105]
   • InOrder: [46 80 90 92 105 111 121]
   • PostOrder: [46 90 105 111 121 92 80]
   Is the tree a BST? Is it an AVLTree? Justify your response.


5. Consider the following tree:
   
   1. What is the pre-order traversal of the tree?
   2. What is the in-order traversal of the tree?
   3. What is the post-order traversal of the tree?
   4. What is the level-order traversal of the tree?
   5. Identify if it is a tree, binary tree, BST, AVL tree
   6. Based on your previous answer, draw the tree obtained by inserting 10 into the tree.
   7. Draw the tree obtained by deleting 2 from the tree.
   8. Draw both trees that might be obtained by deleting 4 from the tree while still maintaining the properties in your answer to e)


6. Consider a boolean function LinkedBST::containsInRange that takes as arguments two keys -- min and max -- and returns true if there exists a key k in the tree such that min <= k <= max. One possible implementation of this function is to call a recursive helper function that takes an additional argument -- a node in the tree, and returns whether that subtree contains any keys in the range:

   template <typename K, typename V>
   bool LinkedBST<K,V>::containsInRange(K min, K max) {
      return subtreeContainsInRange(root, min, max);
   }
   

   Write the recursive helper function subtreeContainsInRange. You may assume that empty trees are represented by pointer to a NULL node.


7. For each of the code fragments below, draw the AVLTree that results from the code fragment:

   1. AVLTree<int,int> t;
      for (int i = 1; i <= 10; ++i) {
         t.insert(i,i);
      }
      

   2. AVLTree<int,int> t;
      for (int i = 1; i <= 5; ++i) {
         t.insert(i,i);
         t.insert(-1*i,-1*i);
      }
      

   3. AVLTree<int,int> t;
      for (int i = 1; i <= 5; ++i) {
         t.insert(i,i);
         t.insert(11-i,11-i);
      }
      

   
   
8. For each of the three code fragments above, draw the tree that would result if a LinkedBST were used instead of an AVLTree.


9. What is the worst-case running time of the following function? Use Big-O notation.

   void f(int n) {
      if (n < 0) {
         return;
      }
      AVLTree<int,int> t;
      for (int i = 0; i < n; ++i) {
         t.insert(i,i);
      }
      for (int i = 0; i < n; ++i) {
         cout << t.remove(i) << endl;
      }
   }
   

   
   
10. What is the smallest AVL tree such that removing a node requires a rotation to rebalance the tree? (There is more than one correct answer, but they're all the same size.)


11. What is the smallest AVL tree such that removing a node requires two rotations to rebalance the tree? (Again there is more than one correct answer, but they're all the same size.)

The following problems examine Binary Heaps in a deeper way that is expected for Test 3, we include them only for completeness because this studyguide will also be used for the final exam.

11. 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.removeMax();
       }
       

    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);
       }
             

12. 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.removeMax() << endl;
       }
    }
        

Home Page