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^nif we have b = 1/ln(1.001). Thus, n^1000 < C 1.001^nwhere 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.