CSC363: Sample questions for Midterm
==============================================

1. Show how can AVL tree data structure supports the query findMax(A) 
which returns the maximal element in the tree, in O(log n) time, wherer n is 
the number of elements in the tree.

2. Show that a search of a random key in an AVL tree that holds n elements is 
Theta(log n). You should assume that (i) all the keys in the tree are distinct
(no two are the same), and (ii) the key you are searching for exists in the tree.

3. Recall that in heapsort algorithm, the first phase inserts n keys into
a heap. Assume that the input sequence is increasing. How long does it take to 
insert such a sequence into the heap? (so first insert smallest key, 
then second smallest, and the last insertion is the largest key)? What about
a decreasing sequence?

4. Consider sorting a sequence with only two values, say 0 and 1. So, for 
example, given input 0,1,1,1,0,1,0 the output would be 0,0,0,1,1,1,1.
How long will it take quicksort in the worst case for such sequences? In 
the best case? Can you suggest a simple linear time algorithm?

5. Consider the problem of finding the r biggest element of a sequence
of n different integers, and compare two algorithms.
Alg I: Find the maximum, Find the second element, Find the third element and so
on, until you get to the r'th element. Output it.
Alg II: sort the sequence by heapsort and output the r'th element of the 
sorted sequence.

(a) What is the running time, measured by number of comparisons, of each 
algorithms in the worst case? 

(b) For which values of r the first method 
is faster, for which the second is, and for which they have the same running 
time. (your answer should be in asymptotic terms, that is say when one method 
is asymptotically faster/slower/the same.

(c) Show how to find the r'th biggest key in an AVL tree in time O(log n). 
You may assume that each node holds a record of the number of nodes in 
the subtree rooted at it (like question 1, A2).

6. Let T be a balanced binary tree that holds n keys {1,2,3,...n}.
Assume that nodes are associated with key in a random way, that it,
each of the ways to distribute keys to the nodes is equalliy likely. What is
the probability thatresulting tree is AVL?