Monday September 24
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.
- [Betty Yip] (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.
- [Peter Feiner]
(from lecture 1) Prove that for the general TSP (no triangle inequality)
if there is a polynomial time algorithm achieving approximation factor k
(for any constant k) then P=NP. You may assume that the Hamiltonian
cycle problem is NP-complete.
- [Michael Bodis]
(based on lecture 3 material) Using the potential method,
analyze the amortized cost of decrementing a binary counter that
initially holds the value $c$.
- [Anne Tran]
(based on lecture 4 material) Show, by giving an example, that
the amortized cost of delete-min in a lazy binomial heap can
really be as bad as \Theta( \log n).
- [Richard Peng]
(lecture 5) To do an amortized analysis of splay trees, we defined
D(x) = the number of descendants of node x, r(x) = log D(x),
and \Phi(T) = Sum {r(x): x a node}. What is the min and max \Phi
of a tree of n nodes?