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

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

• Divide and conquer
• Recursion trees
• Merge sort and merge
• Quick sort, partition, randomized quick sort, and pivot
• Concepts related to sorting: runtime, comparisons, swaps, in-place sorting
• Dynamic memory management and responsibilities
• 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

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

• overloading operators
• iterators
• assert
• Command-line arguments
• basic uses of file streams
• getline

Practice problems

1. Consider the following algorithm, wackyMergeSort, similar to mergeSort:

    
       wackyMergeSort(A, n):
         if (n <= 1)
           return
         A1 = new array
         A2 = new array
         copy first two-thirds (2n/3)  of A into A1
         copy last  one-third (n-2n/3) of A into A2
         wackyMergeSort(A1, 2n/3)
         wackyMergeSort(A2, n-2n/3)
         merge(A1, 2n/3, A2, n-2n/3, A)  // merges sorted A1, A2 back into A
   

   • Is wackyMergeSort a correct sorting algorithm?
   • Draw a recursion tree for wackyMergeSort on an input of size n. For each node (recursive call) in the recursion tree, write the amount of work you expect to be done for just that recursive call to wackyMergeSort. Use Big-O notation for all parts of this problem, justifying (but not proving) your work.
   • How much total work is done per level in the recursion tree?
   • How many total levels are in the tree?
   • Overall, how much total work is done for wackyMergeSort for an input of size n?
   
   
2. 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.


3. 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)


4. 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.


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

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


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

   
   
8. 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.)


9. 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.)

Home Page