\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS7800}{Advanced Algorithms}{Fall 2010}{2 December 2010}{17}           

\begin{center}
\Large{\bf POW 11--14}
\end{center}

{\bf 11. Luckiest sheep}

A wolf is located at node $0$ of a ring consisting of $n+1$ nodes $0$,
$1$, \ldots, $n$, with an (undirected) edge between node $i$ and node
$(i + 1) \bmod (n+1)$ for $0 \le i \le n$.  Each node $i$, $i > 0$, has
a sheep.  The wolf starts a random walk on the ring from $0$.  In each
step, it selects one of its two neighbors uniformly at random, moves
there and gobbles up the sheep present there, if not already eaten.
Which sheep is likely to be eaten the last?  That is, for which $i$ is
the probability that the sheep at $i$ is eaten last the maximum?

{\bf 12. Computing coefficients of a polynomial given its roots} 

Give an $O(n \lg^2 n)$ time algorithm that takes as input numbers
$r_0, r_1, \ldots, r_n$ (where duplicates are allowed) and returns the
unique degree-$(n+1)$ polynomial with roots $r_0, r_1, \ldots, r_n$.

{\bf 13. Ancestral depth following a splay operation}

Let $T$ be a binary search tree, let $u$ be a leaf of $T$, and let $v$
be an ancestor of $u$.  Let $T'$ denote the tree obtained from $T$ by
performing a splay operation at $u$.  (Thus $u$ is the root of $T'$.)
Prove that if $v$ has depth $d$ in $T$ (i.e., there are $d$ edges on
the path from $v$ to the root of $T$), then it has depth at most
$\ceil{d/2}+2$ in $T'$.

{\bf 14. Do ranks and heights induce the same notion of balance?}

Recall that we defined the {\em rank}\/ $r(x)$ of a node $x$ of a tree
to be $\lfloor \log_2 n(x) \rfloor$, where $n(x)$ is the number of
nodes (including $x$) in the subtree rooted at $x$.  And we defined
the {\em total rank}\/ of the tree to be the sum of the ranks of all
of the nodes in the tree.

In the analysis of splay trees, we have seen that the total rank of a
complete binary tree -- a perfectly balanced binary tree -- with $n$
nodes is $\Theta(n)$, while the total rank of a line -- a perfectly
unbalanced tree! -- of $n$ nodes is $\Theta(n\lg n)$.  We also know
that the height of a complete binary tree is $\Theta(\lg n)$, while
that of a line is $\Theta(n)$.  We now ask whether the total rank and
height measures are closely related in terms of the notion of balanced
trees that they induce.  

Prove or disprove: If the total rank of a binary tree is $O(n)$, then
the height of the tree is $O(\lg n)$.
\end{document}
