Midterm 2 Review

Skip Lists

  • Draw a skip list containing values 1, 2, 3, 4, 5, 6 where the heights of the nodes are containing the values are 1, 3, 1, 3, 4, 1 (respectively).
  • Show what nodes are accessed (and at what heights) to find(3).
  • Show the result of insert(3.5).
  • Show the result of remove(3).

Binary Trees

  • Draw a binary tree with 8 elements that is not a binary search tree.
  • What is the maximum height of a binary tree with n nodes?
  • What is the minimum height of a binary tree with n nodes?
  • Draw a full binary search tree with at least seven nodes.
  • List the nodes of your tree given a preorder traversal.
  • List the nodes of your tree given an inorder traversal.
  • List the nodes of your tree given a postorder traversal.
  • List the nodes of your tree given a breadth-first traversal.

AVL Trees

  • Add four numbers to an AVL tree, showing all insertions (including rotations). Note: You should probably do this with at least four different examples, one for each type of rotation (left-left, left-right, right-left, right-right. To make sure you understand how rotations work.

Recursion & Recurrences

With respect to the following function:

void foo(int n, int a, int b) 
{
    if (n <= 1) {
        printf("Foo %d %d\n", a, b);
    } else {
        printf("Bar %d %d\n", a, b);
        for (int i = 0; i < 4; i++) 
            foo(n/2, i, a + b);
    }
}
  • Draw the recursion tree for the following call: foo(4, 0, 0).
  • What is the output of the print statements from foo(4, 0, 0)?
  • Write a recurrence describing the running time of foo. Your recurrence should be in the form T(basecase) = ?, T(n) = ?. Use T as your function. You may assume n is a power of 2.
  • Give a closed form of the following recurrence T(1) = 1, T(n) = 4T(n/2) + 1. You may assume n is a power of 2.

Sorting

  • T/F There may exist an O(n) time comparison based sorting algorithm, but nobody has discovered one yet.
  • T/F If you have nearly sorted input then merge sort will be the best sort algorithm to use since it works in near O(n) time on nearly sorted input.
  • What sorting algorithms are stable? Why does stable matter? Describe a situation in which you would need a stable sorting algorithm.
  • Draw how merge sort operates on the list (1, 3, 9, 2, 4, 7, 0)
  • Draw how quick sort operates on the list (4, 3, 1, 2, 9, 7, 0). You may do this in-place but do not have to. Show all steps of the algorithm. Assume that the pivot selection policy is to choose the first element in the list.
  • How could you implement a priority queue ADT using a dynamic array (give a description of how to implement each priority queue operation)? What is the running time of each operation?
  • How could you implement a priority queue ADT using a heap (give a description of how to implement each priority queue operation)? What is the running time of each operation?
  • Add the following items to an empty heap (1, 5, 2, 3, 9, 11, 15) in the order in which they appear in the list. Show the state of the heap after each swap (you may either draw it as a tree or draw it as an array, whichever you prefer).
  • Show all steps for heap-sort sorting the following list (1, 5, 2, 3, 9, 11, 15).