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

\head{3390}{Analysis of Algorithms}{14 October 1998}{8}

\begin{center}
\Large{\bf Problem Set 2 (due October 28)}
\end{center}

\bigskip
{\bf 1. (12 points total)} We are given a resource $R$ that is being shared
among $n$ users. (For example, the resource may be a printer or a broadcast
channel.) If exactly one of the users attempts to use $R$ at any time, then
the user is immediately granted access to it.  When two or more users attempt
to use $R$ simultaneously, however, there is a collision and none of the users
is given access.

Consider the scenario when each of the $n$ users simultaneously wishes to
access the resource.  Since they are all aware of the possibility of
collisions, each user runs the following procedure until it succeeds: in each
time step, attempt to access the resource with probability $1/2$.  

\begin{Enumerate}
\item[{\bf (a) (2 points)}]
In order to analyze the above process, we first need to establish the
following simple result.  Prove that for all $x < 1$, $\sum_{i = 1}^{\infty}
ix^{i-1} = 1/(1 - x)^2$.  ({\em Hint:} Differentiate both sides of the
infinite geometric series.)

\item[{\bf (b) (10 points)}]
Use part~(a) to show that the expected number of time steps taken for some
user to be granted access to $R$ is $2^n/n$.
\end{Enumerate}

{\bf 2. (5 + 5 = 10 points)} Problem 10--3.1.

{\bf 3. (2 + 5 + 10 = 17 points)} Parts~(a),~(b), and~(c) of Problem 10--2.

%%% Should leave part~(c) exactly the way it is stated in text.
{\bf 4. (5 + 5 + 10 = 20 points)} Problem 12--5.  In part~(c), read the
statement
\begin{eqnarray*}
h_{a,b}(x) = a \cdot x + b
\end{eqnarray*}
as
\begin{eqnarray*}
h_{a,b}(x) = \left(\sum_{i = 0}^{r} (a_i x_i + b_i)\right) \mbox{ mod } m.
\end{eqnarray*}

{\bf 5. (10 points)} This exercise is a generalization of POW--2.  In POW--2,
we reconstructed an ordered list based on the successor information that was
available for each node in the list.  Here, we wish to reconstruct the
structure of a tree $T$ from a list containing the nodes of the tree in
arbitrary order.  For each node of the tree, we are given two fields: the
first field is the name of the node, and the second field is the name of the
parent of the node.  For the root of the tree, the second field is NIL.  Using
hash tables, give an algorithm that constructs the tree in expected linear
time.

{\bf 6. (3 + 3 = 6 points)} Suppose we are using a binary search tree to
maintain a dynamic set.  Give a sequence of $n$ insert requests for which the
binary search tree obtained is a line.  Give a sequence of $n$ insert requests
for which the binary search tree obtained is a complete binary tree.  (For the
second part, you may assume that $n$ is of the form $2^k - 1$.)

{\bf 7. (5 + 5 + 2 + 3 + 10 = 25 points)} Problem 14--1.

\end{document}