Second tutorial--CS251--Winter 2000


Question 1 Complexity. A properly implemented version of mergesort takes 16000 microseconds to sort 10000 elements. Give your prediction about the time that will be needed to sort 100000 elements.

Solution. Assuming the time grows as c n log n for some constant c, where log is base 2, we have c 10^4 log (10^4) = 16000. We are asked the value of x = c 10^5 log (10^5). Divide both equations to eliminate c, and we get x/16000 = 10 (5/4) = 12.5. Thus, x = 200000. Note: this example shows that the hidden constants in the big "Oh" notation do not matter for predictions.

Question 2 Complexity. Show that n^1000 = O( 1.001^n ).

Solution. Recall the Taylor series for e^x, and by grabbing just the 1000-th term, we have e^x > x^1000 /1000!. Thus, let us take a positive number b, and note that

    (n/b)^1000 /1000! < e^(n/b) = e^(n ln(1.001)) = 1.001^n
if we have b = 1/ln(1.001). Thus,
    n^1000 < C 1.001^n
where C = 1000! b^1000. This result is valid for n > 0. Note: in fact, for any a > 0, b > 1, we have n^a = O(b^n), so all polynomial rates are smaller than all exponential rates.
Question 3 Lower bounds. Consider a comparison-based model. Derive a lower bound for finding the median of 5 elements based upon combinatorial considerations. Show your work.

Solution. The number of soltions is 5 (for the choices for median) times (4 choose 2) (for the selection of the two smaller elements out of the four remaining elements), or 5x6=30. There are thus at least 30 leaves in the decision tree. Since we use comparisons only, the decision tree is binary, and the lower bound is ceiling ( log_2 30 ) = 5. Note: With some work, one could get 6 as a lower bound. Start with one comparison, and note that each subtree has 18 leaves, for a lower bound of ceiling( 1 + log_2 18 ) = 6.

Question 4 Induction proofs. Consider the Fibonacci sequence F(n) = F(n-1) + F(n-2), with F(1)=F(2)=1. Prove by induction that F(n) <= 2^(n-1).

Solution. The statement is clearly true for n=1 and n=2. Assume it is true up to n-1, for general n. To show that the inequality is true for n, note the following:

       F(n) = F(n-1) + F(n-2)     (given)
            <= 2^(n-2) + 2^(n-3)  (hypothesis)
	    < 2^(n-2) + 2^(n-2)
	    = 2^(n-1).
Question 5 Linked lists. The ADT maxstack requires the following operations: the five standard stack operations (push, pop, top, makenull, empty) and the additional operation report-max, in which we report the maximum without removing it. We do not know beforehand how big the stack can get. Draw a pointer-based data structure that can handle all operations in O(1) worst-case time and provide a few lines of explanation.

Solution. The cells have two pointers to other cells underneath; a pointer "next" points to the neighboring cell in the stack; a pointer "max-next" points to the maximum in the cells underneath (itself included). Let value[.] be the value stored in a cell. We need to show that push and pop can be implemented' in O(1) time. The code is as follows, if S denotes a stack, and top[S] is a pointer to the top of S:

    report-max(S):  return value[max-next[top[S]]]
    push(x,S): create a cell c
	       next[c] = top[S] 
	       value[c] = x
               if x > value[max-next[top[S]]]
                 then max-next[c] = c
		 else max-next[c] = max-next[top[S]]
	       top[S] = c
    pop(S): top[S] = next[top[S]]
Clearly, each line takes one time unit, and each operation is O(1).
Question 6 Recursion. Suppose that you are given a sorted sequence of distinct integers a_1 < ... < a_n. Give an O(log n) algorithm to determine whether there exists an index i such that a_i = i. For example, in {-7, 10, 15}, there is no such i, but in {0, 2, 4}, we have a_2 = 2.

Solution. Let match (i,j) return true if a_i = i or a_(i+1)= i+1, ..., or a_j = j. We call this function once with match (1,n).

 match (i,j)
     if i > j then return false
     if i = j then if a_i = i then return true
                              else return false 
     if i < j then set m = floor ( (i+j)/2 )
                   if a_m = m then return true
                   if a_m > m then return match (i,m-1)
                   if a_m < m then return match (m+1,j)
Note that the time T_n follows a recurrence as for binary search, T_n = T_(n/2) + 1, and thus T_n = O(log n).
Question 7 Generalities about trees. In a general binary tree used in a static situation (so, insert and delete are not performed on the tree), show how you can augment the information while still using O(n) space in all so that the query: "is node u an ancestor of node v" (where u and v are given pointers to nodes) can be answered in O(1) worst-case time. No algorithms please; just a short paragraph.

Solution. Well, compute the preorder sequence number and postorder sequence number of each node, storing them in preorder[u] and postorder[u]. Now note that u is an ancestor of v if and only if preorder[u] <= preorder[v] and postorder[u] >= postorder[v]. So, the query can be answered in O(1) time.


Copyright © 2000 Luc Devroye. Email: luc@cs.mcgill.ca.