\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1ex}

\head{3390}{Analysis of Algorithms}{30 October 1998}{15}

\begin{center}
\Large{\bf Sample Solutions for Problem Set 2}
\end{center}

\bigskip

{\noindent {\bf 1. Accessing a shared resource}}
\begin{itemize}
\item[(a)] 
For $x < 1$, the infinite geometric series, $\sum_{i = 0}^{\infty}
x^i = 1/(1 - x)$, can be rewritten as $1 + \sum_{i=1}^{\infty} x^i = 1/(1 -
x)$.  We differentiate both sides with respect to $x$ to obtain:
\begin{eqnarray*}
\sum_{i = 1}^{\infty} ix^{i-1} = 1/(1 - x)^2.
\end{eqnarray*}

\item[(b)]
 Let $X$ be  the random number denoting the number
of time steps it takes for some user to succeed.  For any $i$, given that all
users have failed in time steps $1$ through $i - 1$, the probability that
some user succeeds in step $i$ is ${n \choose 1} (1/2)\cdot (1/2)^{n-1} =
n/2^n$.  Thus, the probability that $X = i$ is given by:
\begin{eqnarray*}
\Pr[X = i] & = & (1 - n/2^n)^{i-1} \cdot n/2^n.
\end{eqnarray*}
Therefore,
\begin{eqnarray*}
E[X] & = & \sum_{i = 1}^{\infty} i\cdot (1 - n/2^n)^{i-1} \cdot n/2^n\\
     & = & (n/2^n) \sum_{i = 1}^{\infty} i\cdot (1 - n/2^n)^{i-1}\\
     & = & (n/2^n) \cdot (2^n/n)^2 \mbox{ (by part~(a))}\\
     & = & 2^n/n.
\end{eqnarray*}
\end{itemize}

{\noindent {\bf 2. The effect of group-size in the algorithm for selection}} 
\begin{itemize}
\item
Dividing into groups of $7$: If the input elements are divided into groups of
$7$, then we need to place new bounds on the size of low and high sides of the
partition that are obtained in step~4 of {\sc Select} on page~190 of the text.
As before, at least half of the medians found in step~2 are greater than or
equal to the median-of-medians $x$.  Since there are $\lceil n/7 \rceil$
groups in our case, we find that at least half of the $\lceil n/7 \rceil$
groups contribute $4$ elements or more that are greater than $x$, except for
the one group that has fewer than $7$ elements if $7$ does not divide $n$
exactly, and the one group containing $x$ itself.  Discounting these two
groups, it follows that the number of elements greater than $x$ is at least
\[
4\left(\left \lceil \frac{1}{2} \left \lceil \frac{n}{7} \right\rceil \right \rceil
 - 2\right) \ge \frac{2n}{7} - 8.
\]
Similarly, the number of elements that are less than $x$ is at least $2n/7 -
8$.  It thus follows that the each of the two sides of the partition is of
size at most $n - 2n/7 + 8 = 5n/7 + 8$.  Before establishing our recurrence,
we obtain a lower bound on $n$ such that $5n/7 + 8 < n$.  We note that the
preceding inequality holds whenever $n > 19$.  We now have the following
recurrence, where $n_0$ is a sufficiently large constant ($\ge 19$) that is
chosen later:
\[
T(n) \le \left \{
\begin{array}{ll}
	\Theta(1) & \mbox{ if $n \le n_0$.}\\
	T(\lceil n/7 \rceil) + T(5n/7 + 8) + O(n) & \mbox{ if $n > n_0$.}
\end{array}
\right.
\]
We now show by substitution that $T(n) \le cn$ for some constant $c$.  For our
induction basis, we will select $c$ big enough that $T(n) \le cn$ for all $n
\le n_0$.  Assume as our induction hypothesis that $T(m) \le cm$ for all $m <
n$.  Substituting this inductive hypothesis into the right-hand side of the
recurrence yields
\begin{eqnarray*}
T(n) & \le & c\lceil n/7 \rceil + c(5n/7 + 8) + O(n)\\
& \le & cn/7 + c + 5cn/7 + 8c + O(n)\\
& = & 6cn/7 + 9c + O(n)\\
& = & cn - (cn/7 - 9c - O(n))\\
& \le & cn,
\end{eqnarray*}
since we can pick $c$ and $n_0$ large enough that $cn/7 \ge 9c + O(n)$ for all
$n \ge n_0$.  (Note that this is where $n_0$ is specified.)  The choice of $c$
will depend on the hidden constant in the $O(n)$ term.  Moreover, note that
$c$ must also satisfy the induction basis as mentioned above.  So we will pick
the larger of the two values needed.  In any case, we can always select a $c$
and $n_0$ appropriately and this completes the proof.  Therefore, {\sc Select}
is linear if we divide the input elements into groups of $7$.
\item
Dividing into groups of $3$: {\sc Select} is not linear in the worst-case,
however, if we divide the input elements into groups of $3$ instead.  We get a
good indication of that when we try to follow the same argument as we have
done above.  Since we can only claim that half of the $\lceil n/3 \rceil$
groups contribute $2$ elements each, the best lower bound for any side of the
partition that we are able to show is at most $2((1/2) \cdot (n/3))$, which is
at most $n/3$.  Thus the best upper bound for any side of the partition is at
least $2n/3$.  In fact, we can ensure this by choosing the input
appropriately. Assume that $n$ is a multiple of $6$.  We can select the input
such that the number of groups with medians greater than the median-of-medians
$x$ is exactly $(1/2)(n/3) = n/6$.  This implies that the number of elements
greater than $x$ is exactly $2n/6 + 1 = n/3 + 1$.  Therefore, the number of
elements less than $x$ is exactly $2n/3 - 1$.  We set the input rank such that
it falls in the low side of the partition.  If we do this for every level of
the recursion, then this yields a recurrence of the form
\[
T(n) \ge T(n/3) + T(2n/3 - 1) + \Theta(n),
\]
which leads to $T(n) = \Omega(n \lg n)$.  You can see this if you unravel the
recursion tree obtained by the above recurrence and note that each of the
$\Omega(\log n)$ levels of the recursion tree sum to $\Omega(n)$.
\end{itemize}

{\noindent {\bf 3. Weighted median}} 

Let $X$ denote the set $\{x_1, x_2, \ldots, x_n\}$.  If the weight
of an element $x$ in $X$ is written as $w(x)$, we can rewrite the definition
of weighted median as follows.  The weighted median of $X$ is the element
$x^*$ satisfying
\begin{eqnarray*}
\sum_{x \in X, x < x^*} w(x) & \le & \frac{1}{2}, \mbox{ and}\\
\sum_{x \in X, x > x^*} w(x) & \le & \frac{1}{2}.
\end{eqnarray*}

\begin{itemize}
\item[(a)] 
Let the median of $X$ be $\hat{x}$.  By definition, the number of
elements less than $\hat{x}$ (resp., greater than $x$) is at most $n/2$
(resp., $n/2$).  For all $x$ in $X$, $w(x) = 1/n$.  Therefore, we have
\begin{eqnarray*}
\sum_{x \in X, x < \hat{x}} w(x) & \le & \frac{n}{2} \cdot \frac{1}{n} \le
\frac{1}{2}, \mbox{ and}\\
\sum_{x \in X, x > \hat{x}} w(x) & \le & \frac{n}{2} \cdot \frac{1}{n} \le
\frac{1}{2}.
\end{eqnarray*}
Therefore $\hat{x}$ is a weighted median.
\item[(b)]
 The weighted median can be computed using sorting in the following manner:
\begin{tabbing}
{\sc Weighted-Median-By-Sorting}($X$)\\
1.  \= sort $X$ using mergesort (let $X[1], \ldots, X[n]$ be the sorted order);\\
2.\>$W \leftarrow 0$;\\
3.\>$i \leftarrow 0$;\\
3.\> \while\ \=  $W \le 1/2$ do\\
4.\> \> $i \leftarrow i + 1$;\\
5.\> \> $W \leftarrow W + w(X[i])$;\\
6.\> \ret\ $X[i]$;
\end{tabbing}
The above algorithm first sorts $X$ and does a pass through $X$ to determine
the largest element $X[i]$ such that the sum of the weights of the elements
less than $X[i]$ is at most $1/2$.  At termination, we have $X[1] + \ldots +
X[i-1] \le 1/2$.  Moreover, since $X[1] + X[2] + \ldots + X[i] > 1/2$, we have
$X[i+1] + \ldots X[n] \le 1/2$.  Therefore, $X[i]$, the element returned, is
the weighted median.

Step~1 of {\sc Weighted-Median-By-Sorting} takes $O(n \lg n)$ time.  Steps~2
and~3 take O(1) time.  The while loop is executed $O(n)$ times (since the sum
of all of the weights is $1$).  Thus the overall running time is $O(n \lg n)$.
\item[(c)]
A linear time algorithm can be obtained by using the selection algorithm
defined in text.  We design an algorithm that takes as input a set $X$ and a
weight $v$ and returns the largest element $x$ in $X$ such that the weight of
all the elements less than $x$ in $X$ is at most $v$.  It is easy to see that
the weighted median is the element returned by {\sc
Weighted-Median-By-Select}($X, 1/2$).

\begin{tabbing}
{\sc Weighted-Median-By-Select}($X, v$)\\
1. \= \myif\ $X$ has one element, then return that element;\\
2. \> find the $\lfloor (|X| + 1)/2 \rfloor$th element (median) $\hat{x}$ of
$X$ using the algorithm {\sc Select} of text;\\ 
3. \> partition $X$ into two parts $X_1 = \{x \in X: x \le \hat{x}\}$ and $X_2 =
\{x \in X: x > \hat{x}\}$;\\
4. \> $w_1 \leftarrow \sum_{x \in X_1} w(x)$;\\
5. \> \myif\ $v \le w_1$ then \ret\ {\sc Weighted-Median-By-Select}($X_1, v$)\\
6. \> \myelse\ \ret\ {\sc Weighted-Median-By-Select}($X_2, v - w_1$)
\end{tabbing}
We prove by induction on the size $n$ of $X$ that the algorithm is correct;
that is, it returns the largest element in $X$ such that the weight of all the
elements less than $x$ in $X$ is at most $v$.  For the base case, $n = 1$.  In
this case, the lone element of $X$ is returned and the claim trivially holds.
Assume the claim holds for all sets of size less than $n$.

For the induction step, we consider the claim for $X$ of size $n$.  In step~2,
the median $\hat{x}$ splits the set into two parts, each of which is of size
strictly less than $n$.  There are two cases.  If $w_1$, the sum of the
weights of all elements in $X_1$ that are less than or equal to $\hat{x}$, is
greater than or equal to $v$, then the desired element is the largest element
in $X_1$ such that the weight of all the elements less than $x$ in $X_1$ is at
most $v$.  Otherwise, the desired element is the largest element in $X_2$ is
such that the weight of all the elements less than $x$ in $X_2$ is at most $v
- w_1$.  In either case, it follows from the induction hypothesis and the
recursive calls in steps~5 and~6 that the desired element is returned by the
algorithm.

We now analyze the running time of the algorithm.  Let $T(n)$ be the
worst-case running time for an input of size $n$.  Step~1 takes $O(1)$ time.
Steps~2,~3, and~4 each take $O(n)$ time each.  Each of the steps~5 and~6 take
time at most $T(\lceil (n+1)/2\rceil) \le T(n/2 + 1)$.  We thus have the
following recurrence:
\[
T(n) \le T(n/2 + 1) + O(n),
\]
which can be easily seen to yield $T(n) = O(n)$ by substitution or the master
method. 
\end{itemize}

{\noindent {\bf 4. $k$-Universal hashing}}
\begin{itemize}
\item[(a)] Let $[m]$ denote the set $\{0, 1, \ldots, m-1\}$ for convenience.
 If $\Hash$ is $2$-universal, then for any distinct $x$ and $y$ in $U$ and any
 $\alpha, \beta \in [m]$, we have
\[ 
\Pr[\langle h(x), h(y) \rangle = \langle \alpha, \beta \rangle] = 1/m^2,
\]
where $h$ is assumed to be chosen uniformly at random from $\Hash$.
Therefore, 
\begin{eqnarray*}
\Pr[h(x) = h(y)]
& = & \sum_{\alpha \in [m]} \Pr[\langle h(x), h(y) \rangle =
\langle \alpha, \alpha \rangle]\\
& = & m \cdot 1/m^2\\ 
& = & 1/m.
\end{eqnarray*}
Therefore, $\Hash$ is universal.
\item[(b)] 
Set $x = \langle 0, 0, \ldots, 0 \rangle$ and $y$ to be any element
distinct from $x$.  Set $\alpha$ and $\beta$ to be both $1$.  For any choice
of $a$, the hash function $h_a$ defined in Section~12.3.3 of the text, yields
$h_a(x) = 0$.  Therefore, the number of hash functions for which $\langle
h(x), h(y) \rangle = \langle 1, 1\rangle$ is $0$.  Hence, $\Pr[\langle h(x),
h(y) \rangle = \langle 1, 1\rangle] = 0 \neq 1/m^2$ implying that the class
$\Hash$ of Section~12.3.3 is not $2$-universal.
\item[(c)] There are a total of $m^{2(r + 1)}$ hash functions in $\Hash$,
since we have $m^{r+1}$ choices for $a$ and $m^{r+1}$ choices for $b$.  Fix
distinct $x$ and $y$ in $U$ and arbitrary $\alpha$ and $\beta$ in $[m]$.
Without loss of generality assume that $x_0 \neq y_0$. We will prove that the
number of hash functions in $\Hash$ for which $\langle h(x), h(y) \rangle =
\langle \alpha, \beta \rangle$ is $m^{2r}$.  This implies that $\Pr[\langle
h(x), h(y) \rangle = \langle \alpha, \beta \rangle] = 1/m^2$.

We need the following two equations to be satisfied:
\begin{eqnarray*}
\sum_{i = 0}^{r} (a_i x_i + b_i) & \equiv & \alpha  \; (\bmod m) \mbox{ and}\\
\sum_{i = 0}^{r} (a_i y_i + b_i) & \equiv & \beta  \; (\bmod m).
\end{eqnarray*}
Let us fix the values for $a_1$ through $a_r$ and $b_1$ through $b_r$.  We are
now left with two equations with two unkwowns $a_0$ and $b_0$.
\begin{eqnarray}
a_0 x_0 + b_0 & \equiv & \alpha - \sum_{i = 1}^{r} (a_i x_i + b_i) \; (\bmod m)
\label{eqn:1}\\
a_0 y_0 + b_0 & \equiv & \beta - \sum_{i = 1}^{r} (a_i y_i + b_i) \; (\bmod m) \label{eqn:2}.
\end{eqnarray}
We now subtract the two equations and obtain an equation with one unknown
$a_0$.
\begin{eqnarray}
a_0 (x_0 - y_0) \equiv \alpha - \beta - \sum_{i = 1}^{r} a_i (x_i - y_i)
\; (\bmod m) \label{eqn:a_0}
\end{eqnarray}
We invoke the argument used in text to claim that there is exactly one value
of $a_0$ that satisfies Equation~\ref{eqn:a_0}.  (Note that we can claim this
because $x_0 - y_0 \neq 0$ and $m$ is prime.)  We now put the value of $a_0$
in Equation~\ref{eqn:1} and claim that there is exactly one value of $b_0$ for
which Equation~\ref{eqn:1} is satisfied.  Of course, Equation~\ref{eqn:2} is
also satisfied for this choice of $a_0$ and $b_0$.  Thus for any given values
of $a_1$ through $a_r$ and $b_1$ through $b_r$, there is exactly one value of
$a_0$ and $b_0$ for which $\langle h_{a,b}(x), h_{a,b}(y) \rangle = \langle
\alpha, \beta \rangle$.  Thus, there are $m^{2r}$ such hash functions and the
desired claim now follows.

{\noindent {\bf Remark:}} It turns out that we could have proved the same
result with a simpler interpretation of $h_{a,b}(x)$ than what I had asked you
to consider.  Take $b$ to be just a number in $[m]$ rather than $\langle b_0,
b_1, \ldots, b_{r-1} \rangle$ as we have done above.  So $h_{a,b}(x)$ is the
following: 
\[
h_{a,b}(x) = \left(\sum_{i = 0}^{r-1} a_i x_i \right) + b.
\]
Thus, there are $m^{r+2}$ hash functions in $\Hash$ (much less than what we
had above).  Even then, we can argue that $\Hash$ is $2$-universal.  We will
use a similar argument as above.  Fix distinct $x$ and $y$ in $U$ and $\alpha$
and $\beta$ in $[m]$.  Without loss of generality assume that $x_0 \neq y_0$.
We will show that the number of hash functions $h$ in $\Hash$ for which
$\langle h(x), h(y) \rangle = \langle \alpha, \beta \rangle$ is $m^r$.  This
will give us the value $1/m^2$ for the relevant probability. 

We need the following two equations to be satisfied:
\begin{eqnarray*}
\left(\sum_{i = 0}^{r} a_i x_i\right) + b & \equiv & \alpha \; (\bmod m) \mbox{ and}\\
\left(\sum_{i = 0}^{r} a_i y_i\right) + b & \equiv & \beta \; (\bmod m).
\end{eqnarray*}
Let us fix the values for $a_1$ through $a_r$.  We are
now left with two equations with two unkwowns $a_0$ and $b$.
\begin{eqnarray}
a_0 x_0 + b & \equiv & \alpha - \sum_{i = 1}^{r} a_i x_i \; (\bmod m)
\label{eqn:3}\\
a_0 y_0 + b & \equiv & \beta - \sum_{i = 1}^{r} a_i y_i \; (\bmod m) \label{eqn:4}.
\end{eqnarray}
We now subtract the two equations and obtain an equation with one unknown
$a_0$.
\begin{eqnarray}
a_0 (x_0 - y_0) \equiv \alpha - \beta - \sum_{i = 1}^{r} a_i (x_i - y_i)
\; (\bmod m) \label{eqn:a_0new}
\end{eqnarray}
We invoke the argument used in text to claim that there is exactly one value
of $a_0$ that satisfies Equation~\ref{eqn:a_0new}.  (Note that we can claim this
because $x_0 - y_0 \neq 0$ and $m$ is prime.)  We now put the value of $a_0$
in Equation~\ref{eqn:3} and claim that there is exactly one value of $b$ for
which Equation~\ref{eqn:3} is satisfied.  Of course, Equation~\ref{eqn:4} is
also satisfied.  Thus for any given values of $a_1$ through $a_r$, there is
exactly one value of $a_0$ and $b_0$ for which $\langle h_{a,b}(x), h_{a,b}(y)
\rangle = \langle \alpha, \beta \rangle$.  Thus, there are $m^{r}$ such hash
functions and the desired claim now follows.
\end{itemize}

{\noindent {\bf 5. Reconstructing a tree from parent information}} 

Let $L$ denote the list of nodes given.  To distinguish these nodes from the
nodes of the tree that we will build, we refer to the nodes in the list as
{\em list-nodes}\/ while we refer to the nodes in the tree as {\em
tree-nodes}\/.  A list-node $x$ has two fields $\name[x]$ and
$\parentname[x]$.  For a tree-node $u$, we will maintain three fields: (i)
$\name[u]$, the name of $u$, (ii) $\parent[u]$, a pointer to the parent of
$u$, and (iii) $\children[u]$, a doubly linked list containing pointers to the
children of $u$.

We use hash tables for efficiently searching a node.  In order to ensure
expected $O(1)$ time for a search, we will choose our hash function from a
class of universal hash functions.  In order to resolve collisions, we use
chaining.  Theorems~12.1 and~12.3 of text together then guarantee that a given
search takes expected $O(1)$ time.  Insertion and deletion take $O(1)$ time as
we will maintain each chain as a doubly linked list.

In our hash table, we will store the tree-nodes that we create.  There are two
ways in which we can hash the tree-nodes.  One is using the name of their
parent.  The other is through their own name.  If we hash according to the
parent name, there are two kinds of collisions that take place.  One is when
two nodes have the same parent.  And the other is due to the hash function.
Due to the latter kind of collisions, it is {\em not the case that after all
the nodes have been hashed, a given slot contains a list of siblings}.  We
must keep this in mind when we do the construction of the tree.  The best way,
perhaps, to avoid this problem is to maintain a chain of linked lists in each
slot.  Each slot maintains a linked list of pointers, each pointer pointing to
a linked list of children associated with a parent that maps to this slot.
Suppose we are hashing a node $x$ according to its parent's name.  So we check
slot $A[h[\parentname[x]]]$, where $A$ is the hash table and $h$ is the hash
function.  Instead of just storing the node $x$ into a chain in this slot, we
will obtain a pointer to the linked list that maintains the children of
$\parentname[x]$ and then insert node $x$ (or an associated entity) into this
list.  If we do not maintain a chain of linked lists, then either we may not
be able to reconstruct a correct tree or we may not ensure expected linear
running time.

We now give a detailed description of the algorithm in which we hash according
to the given name (rather than the parent's name).  This avoids some of the
problems discussed in the above paragraph.  Here is the algorithm:
\begin{tabbing}
{\sc Tree-Construct}($L$)\\
1.  \=  \for\ \= each list-node $x$ in $L$ do\\
2.  \> \> create new tree-node $u$;\\
3.  \> \> $\name[u] \leftarrow \name[x]$;\\
4.  \> \> $\parent[u] \leftarrow \nil$;\\
5.  \> \> $\children[u] \leftarrow \nil$;\\
6.  \> \> $\hi(T, u)$; \mbox{ (hash according to \name)}\\
7.  \> \for\ \> each node $x$ in $L$ do\\
8.  \> \> $u \leftarrow \hs(T, \name[x])$;\\
9.  \> \> \myif\ $\parentname[x] \neq \nil$ then $p \leftarrow \hs(T,
\parentname[x])$;\\
10. \> \> \myelse\ $\myroot \leftarrow u$;\\
11. \> \> $\parent[u] \leftarrow p$;\\
12. \> \> insert $u$ into $\children[p]$;\\
13. \> \ret\ \myroot.
\end{tabbing}
In the first for-loop, {\sc Tree-Construct} first creates a tree-node for
every list-node in $L$ and inserts the tree-node into the hash table $T$ using
universal hashing and chaining.  In the second for-loop, the algorithm goes
through the list-nodes again and (i) sets the parent pointer of each tree-node
(except the root) to point to the appropriate tree-node that we search in the
hash table, and (ii) inserts the tree-node into the children list of its
parent tree-node.  Finally, the algorithm returns the root.  Clearly, at the
end of the procedure, each tree-node $u$ has a pointer to its parent (since
step~9 is executed once for the list-node corresponding to $u$) and each of
its children is inserted into its children linked list exactly once (since
step~11 is executed exactly once for each of its children).  Note that there
is no recursion.

For the running-time, we first consider the first for-loop.  In each
iteration, steps~2 through~6 take $O(1)$ time.  In the second for-loop, step~8
takes expected $O(1)$ time.  Steps~9 through~11 take $O(1)$ time.  Also, since
the children field is a doubly linked list, step~12 takes $O(1)$ time.
Finally, step~13 takes $O(1)$ time.  Since there are exactly $n$ iterations
for each for-loop, the expected running time is $O(n)$.

{\noindent {\bf 6. Effect of insert sequences on binary search trees}} 
\begin{itemize}
\item
If we insert the numbers $1$, $2$, \ldots, $n$ in sequence into a binary
search tree, we obtain a line.  We prove by induction on $n$ that the tree
obtained after inserting $1$, $2$, \ldots, $n$ is the following: (i) the root
is the element $1$, (ii) the left child of each element $i$ is \nil, (iii) the
right child of each element $i < n$ is the element $i + 1$, and (iv) the right
child of $n$ is \nil.

The claim is trivially true for $n = 1$.  For the induction hypothesis, we
assume that the claim is true for all $n < m$.  When we insert $n$ into the
tree that has properties~(i) through~(iv) above, $n$ becomes the rightmost
node in the tree since it is the largest element.  Hence, properties~(i)
through~(iv) hold after insertion.  The desired claim is shown.
\item
In order to obtain a complete binary tree, we consider the sequence that is
defined recursively as follows.  Let $S_k$ denote the sequence of insert
requests that yields the complete binary tree on $2^k - 1$ nodes.  For a given
sequence $S = s_1, \ldots, s_\ell$, let $S \oplus x$ denote the sequence $s_1 +
x, s_2 + x, \ldots s_\ell + x$.  We now define $S_k$ as:
\[
S_k = \left \{
	\begin{array}{ll}
		1 & \mbox{if $k = 0$}\\
		2^{k-1}, S_{k-1}, S_{k-1} \oplus 2^{k-1} & \mbox{if $k > 0$.}
	\end{array}
\right.
\]
Note that according to $S_k$, we first insert the median element of the $2^k -
1$ elements, then recursively the smallest $2^{k-1} - 1$ elements and then
recursively the largest $2^{k-1} - 1$ elements.  

To prove that $S_k$ is indeed the sequence of insert requests that yields the
complete binary tree on $2^k - 1$ nodes, we use induction on $k$.  We prove by
induction on $k$ that: (i) $S_{k}$ consists of numbers from $\{1, 2,
\ldots,2^k - 1\}$, and (ii) $S_k$ yields a complete binary tree on $2^k - 1$
nodes.  For the base case, we consider $k = 0$ and the claim trivially holds.
For the induction hypothesis, assume that (i) $S_{k-1}$ consists of numbers in
in $\{1, 2, \ldots, 2^{k-1} - 1\}$, and (ii) $S_{k-1}$ yields the complete
binary tree on $2^{k-1} - 1$ nodes. 

We now prove the induction step.  By definition, $S_k = 2^{k-1}, S_{k-1},
S_{k-1} \oplus 2^{k-1}$.  By property~(i) of $S_{k-1}$, we have that each
number in $S_k$ is between $1$ and $2^{k-1} + 2^{k-1} - 1 = 2^k - 1$.  Thus,
we have shown property~(i) of $S_k$.  It also follows from property~(i) of
$S_{k-1}$ that if we insert the elements of $S_k$, we first insert $2^{k-1}$,
then elements less than $2^{k-1}$, and finally elements greater than
$2^{k-1}$.  Thus we first have $2^{k-1}$ as the root, then elements in
$S_{k-1}$ form the left subtree, and finally $S_{k-1} \oplus 2^{k-1}$ forms
the right subtree.  Since $S_{k-1}$ yields a complete binary tree of $2^{k-1}
+ 1$ nodes, so does $S_{k-1} \oplus 2^{k-1}$ since the order of elements is
exactly the same.  It thus follows that the tree obtained by $S_k$ is a root
element $2^{k-1}$ whose left and right subtrees are complete binary trees over
$2^{k-1}$ nodes.  Property~(ii) of the induction step thus follows.
\end{itemize}

{\noindent {\bf 7. Persistent dynamic sets}} 
\begin{itemize}
\item[(a)] Consider the insertion of key $k$ into a binary search tree.  Let
$T$ be the current version of the persistent tree.  Let $x$ denote the new
node associated with key $x$ after a regular insertion into $T$.  Since we
wish to maintain previous versions of the persistent binary tree, $x$ should
be accessible only from the latest version of the binary search tree.
Consequently, we need to change every node that lies on the path from the root
to $x$.  This can also be seen by the observation that when we insert the new
node, the need for a new child pointer propagates up from the new node to all
of its ancestors.

When we delete $y$, there are two cases.  If $y$ has at most one child, $y$
will be removed or spliced out.  All of the ancestors of $y$ will be changed.

If $y$ has two children than the deletion process replaces the key of $y$ by
the successor key and then deletes the successor node that is guaranteed to
have fewer than two children.  In the persistent binary search tree, when we
delete the successor node, all of the nodes on the path from the root to the
successor need to be changed.  Thus, all ancestors of the successor of $y$
need to be changed.  Since $y$ itself is an ancestor of the successor of $y$,
the above changes include the change that occurs to $y$'s key.

\item[(b)]
We give a recursive procedure for \pti.  It takes as input a node
$r$ and a key $k$ and returns the new root obtained after inserting $k$ into
the subtree rooted at $r$.  So the insertion into the persistent tree would be
made by calling \pti($\myroot[T], k$).
\begin{tabbing}
\pti($r, k$)\\
1.  \= \myif\ \= $r = \nil$ then\\
2. \> \> $x \leftarrow \cnn(k)$; (set key to $k$ and child to $\nil$)\\
3. \> \myelse\\
4. \> \>  $x \leftarrow \cp(r)$; (copy all of $r$'s fields into $x$)\\
5. \> \> \myif\ \= $k < \key[r]$ then\\
6. \> \> \> $\myleft[x] \leftarrow \pti(\myleft[r], k)$;\\
7. \>\> \myelse\\
8. \> \> \> $\myright[x] \leftarrow \pti(\myright[r], k)$;\\
9. \> \ret\ $r$;
\end{tabbing}
If the root is not $\nil$, then \pti\ makes a copy of the root and recursively
calls \pti\ on the appropriate subtree.  If the root is $\nil$ (as would happen
at the last level of the recursion when the key is finally inserted), the
procedure creates a new node.

\item[(c)] 
The procedure \pti\ does a constant amount of work at each node
along the path from the root to the new node.  Since the height of the tree is
$h$, the total time taken is $O(h)$.

The procedure \pti\ allocates a new node (whenever $\cp$ or $\cnn$ is called)
for each ancestor of the inserted node (including itself).  Since the space
required for each node is a constant, total additional space requirement is
$O(h)$.

\item[(d)]
If each node also maintained a parent field, then owing to the new root, all
nodes of the tree (i.e., all descendants of the root) would have to be changed
whena new node is inserted.  This is because we need to be able to reach the
new root in the latest version of the tree.  Therefore, two versions of the
tree cannot share a node in common since we can only reach one root if we
repeatedly follow the parent pointers starting from that node.

\item[(e)] From part~(c), we know that insertion into an ordinary persistent
binary search tree requires changing $O(h)$ nodes where $h$ is the height of
the tree.  A red-black tree has height $O(\lg n)$.  But this does not
immediately imply that the insertion into the red-black tree will also require
changing $O(\lg n)$ nodes.  This is because, we need to address two problems
that arise.  

The first problem is: how do we find the parent pointers we need in $O(1)$
time without using a parent field.  Note that we cannot maintain a parent
field since part~(d) implies that a persistent tree with parent fields uses
$\Omega(n)$ time for insertion.  The second problem is: we need to account for
the changes made during red-black operations by rotation and recoloring and
show that these do not cause more than $O(\lg n)$ nodes to change.

We first consider how to obtain the parent of a node during insertion without
having a parent field.  The insertion in red-black trees consists of two
phases.  In the first phase, we do a regular insertion by walking down the
tree to find the place to insert the new node.  During this walk, we will
build a stack of the nodes that are traversed.  The parent pointers are only
needed in the second phase when we walk up the same path and make color
changes to siblings and uncles.  Since the stack of parents are maintained,
each parent information can be found in $O(1)$ time from the stack, just as if
it were stored in a parent field.

Rotation and recoloring changes nodes as follows:
\begin{itemize}
\item
\rbi\ rotates at most a constant number of nodes, and each rotation changes
the child pointers in $3$ nodes: the node $x$ around which the rotation is
performed, $x$'s parent, and the node that becomes $x$'s parent.  In a
persistent tree, all the ancestors of a changed node change, as we have
observed in part~(a).  So the $O(1)$ rotations imply that $O(\lg n)$ nodes
have to be changed because of the rotations.  
\item
\rbi\ changes the colors of some of the ancestors of the inserted node and some
of the children of these ancestors (the uncles).  The ancestors are being
changed anyway in persistent insertion.  Recoloring uncles does not cause any
additional node changes because the ancestors of the uncles are the same nodes
that are being changed anyway.  Thus, there are $O(\lg n)$ nodes that are
changed due to recolorings. 
\end{itemize}
We can show similarly that deletion in a persistent red-black tree also takes
worst-case time $O(\lg n)$.  We begin by observing that deletion in an
ordinary persistent binary search tree can also be done in $O(h)$ time where
$h$ is the height of the tree.  We have shown in part~(a) that $O(h)$ nodes
need to be changed.  We can write a procedure \ptd\ analogous to \pti.

As with insertion, we need to avoid using the parent field which we need while
doing the upward pass (recoloring and rotation) in the second phase of
deletion from a red-black tree.  We will apply the same technique as we did
for insertion and build up a stack of pointers.  When we need a parent or a
grandparent of a node, we will get that from the top (or the second from top)
of the stack. 

So now, all we need to argue is that the number of nodes that are changed due
to rotations or recolorings that occur in deletion is $O(\lg n)$.  The number
of rotations performed by \rbdf\ is constant, which requires $O(\lg n)$ time
since the set of nodes changed are the ancestors of the nodes ``involved'' in
the rotation (as we argued for insertion).  It also does $O(\lg n)$ color
changes, which take only $O(\lg n)$ time because the number of changed nodes
and their ancestors (due to persistence) is $O(\lg n)$.
\end{itemize}
\end{document}
