1. Suppose we implement an AVL tree in a heap-like array. That is, the root of
the AVL tree is in A[1], the left child of the root is A[2],
the right child of the root is A[3], and so on.
Give the worst case runtimes (in theta notation) for Search, Insert, and
Delete in this AVL tree implementation.
2. Most graph algorithms when using the adjacency matrix take time O(n^2).
This one is an exception, and can be done in time O(n).
Let G be a digraph that is given by its adjacency matrix. Show how to find
a vertex with out-degree 0 and in-degree n-1 if one exists, and report that
none exist otherwise.
- hint: by looking at two vertices uand v, and the edges between them,
what can you conclude?
3. Let U be a set of possible keys and let h:U --> {0,1,...,m-1} be a hash
function. What does it mean when we say that h satisfies the ``simple uniform hashing'' assumption?
Now, let U = {0,1,...,N-1} where N is some large number. Is the function
h(x) = x^2 mod m a uniform hash function? Explain.
4. Describe (in plain language) an algorithm that runs in time O(n+m) and
that computes all the connected components of an undirected graph G with n
vertices and m edges.
5. An undirected graph is a tree if it is connected and has no cycles. Show
that when running DFS on a tree all edges are "discovery-edges".
6. The median of a set of n distinct integers is the element
in ``the middle'' when the set is order, or in other words the floor((n+1)/2)
biggest element.
Show how it is possible to use an AVL tree in order to additionally support the following operations in time O(1):
* Min(T,x): Find the minimum key in T.
* FindMedian(T,x): Find the median of the keys in T.
* FindAvg(T,x): Find the average of the keys in T.
In addition, the tree should as usual support INSERT and DELETE opertions.
Note: Note that you may want to adjust the implementation of the INSERT/DELETE operations in the process.
7. Consider a binomial heap on 100. How many binomial trees does it contain?
8. consider a binomial heap that has all layers full (What can be said aboutt
about the number of keys this heap hold?) Now, suppose we take a "mirror-image"
of the tree, so if u was a left child of u it is now a right child and vice versa. Does the obtained tree still satisfy the heap property?