Monday October 1
To sign up for a problem, send email to alubiw "at" uwaterloo.ca.
I will update this list to indicate the first person who signs up.
- [Olga Irzak]
(from lecture 5) Show that the simple idea of splaying by doing single
rotations to move a node to the root of the binary search tree gives
amortized search cost \Omega(n).
-
[Patrick B.]
(This problem has changed -- it is now a repeat of Question 1
from Problem Set 1.)
(from lecture 1) In class we saw the factor 2 approximation algorithm for metric TSP that starts by finding a minimum spanning tree. Give an example where the approximation algorithm gives factor 2 -- or at least as close as possible.
- [Bryce Zimny]
(from lecture 6)
Complete the proof of the Theorem claiming O(log n) amortized cost
for splay tree operations. In particular, show that an insertion has
amortized cost O(log n).
- [Ning Zhang]
(from lecture 7)
Consider the implementation of Union-Find using an array A[1 .. n] where
A[i] gives the name of the set containing element i, and for a Union
we update the array entries for the smaller of the two sets. Prove
that m operations take time O(m + n log n).
- [Andrew Lo]
(from lecture 7)
For the tree-based implementation of Union-Find we used a rank function
defined as follows: the rank of a single node tree is 0, and linking two trees of ranks r1 and r2 with r1 >= r2 makes a tree of rank r = max{r1, r2 + 1}.
Prove that (i) a vertex of rank r has >= 2^r descendants; (ii) the number of
vertices of rank r is <= n / 2^r.