NOTE: As you may have noticed, we use a lot of examples and diagrams in the lectures. So email is not an effective method to answer questions related to course material. Please DO NOT ask how to solve the following problems via email. Come to the office hours instead.

  1. Order the following running time θ bounds by asymptotic growth rate in nondescending order. Indicate equality, if any.
    N2, 2N, 25, Nlg(lgN), Nlg(N2), N2lgN, N3, NlgN, and N!.

  2. Solve the following recurrences by obtaining a θ bound for T(N) given that T(1) = θ(1):
    1. T(N) = 2N - 1 + T(N-1)
    2. T(N) = N + T(N-3)
    3. T(N) = N2 + T(N-1)

  3. Perform a worst-case analysis of each of the following fragments and give a θ bound for the running time: 
      a.   sum = 0;
       for (int i = 0; i < N; i++)
          for (int j = 0; j < i * i; j++)
             for (int k = 0; k < j; k++)
                sum++;

  b.   sum = 0;
       for (int i = 0; i < N; i++)
          for (int j = 0; j < i * i; j++)
             if (j % i == 0)
             {
                for (int k = 0; k < j; k++)
                   sum++;
             }

  4. Mergesort does have a worst-case time of θ(NlgN) but its overhead (hidden in the constant factors) is high and this is manifested near the bottom of the recursion tree where many merges are made. Someone proposed that we stop the recursion once the size reaches K and switch to insertion sort at that point. Analyze this proposal (by modifying the recurrence analysis of standard mergesort) and prove that its running time is θ(NK + Nlg(N/K)). How would you choose K?

  5. Answer the following questions about the basic quicksort algorithm; i.e. the pivot is the leftmost element of the list (rather than the median-of-3):
    1. What is its running time if all elements in the list are equal?
    2. Give two (non-trivially different) examples of lists that induce the quadratic behavior; i.e. produce bad splits at every level of the recursion.
    3. Your Visa statement is sorted by recording date whereas you prefer to see it sorted by transaction date. Argue that insertion sort is better suited for such a re-sort than quicksort.

  6. Given a sorted array A of N distinct integers, we seek an algorithm to determine if there exists an index i such that A[i] = i.
    1. Give an exhaustive algorithm and obtain its θ running time in the worst case.
    2. Give a divide-and-conquer algorithm and obtain its θ running time in the worst case.


  7. Answer the following questions about a non-empty binary tree of N nodes and height H:
    1. Prove that the number of null links in the tree is N+1.
    2. Prove that the number of nodes with two children is one less than the number of leaves.
    3. Prove that N ≤ 2H+1 - 1.
    4. Assuming that each node holds a single character and that the inorder and preorder traversals yield ambmcpdse and smmabpcde respectively, draw the tree and list its nodes in postorder.

  8. Given the keys 1, 2, ... N, i.e. the integers 1 to N sorted, describe a linear algorithm to store them in an N-node BST so that the BST will be perfectly balanced with height H. Assume N = 2H+1 - 1.

  9. Draw the following BSTs:
    1. Show the result of inserting 3, 1, 4, 6, 9, 2, 5, 7 into an initially empty BST.
    2. Show the result of deleting the root.