\documentstyle [11pt]{article}
\setlength{\parskip}{2 ex}
\setlength{\topmargin}{-0.5 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{9.5 in}
\setlength{\textwidth}{6.5 in}
\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}
\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcommand{\ceiling}[1]{\lceil #1 \rceil}
\newcommand{\floor}[1]{\lfloor #1 \rfloor}

\newtheorem{defi}{Definition}[section] % Specify Definition
\newtheorem{problem}[defi]{Problem}      % Specify Lemma


\begin{document}
{\large
\noindent
Algorithms Core 15-750 \hfill PROBLEM SET \# 6 \hfill Spring 1999
\begin{center}
DUE: 1:00PM Wednesday April 28 1999 \\
\end{center}}



\section{Analysis of MIS Algorithm version 2}

This problem is worth two problems.

Recall, version 2 of the Luby's Maximal Independent set Algorithm:

Let $G=(V,E)$ be simple undirected graph

Procedure: MIS$(G=(V,E))$  
\begin{mylist}{.0 in}
\item[0)]
If $|V|=0$ return. 
\item[1)]
For each vertex $v$ pick a random number $p_v$ in the range $[0,1]$.
You may assume the values $p_v$ are distinct.
\item[2)]
Place $v$ in $I$ if $p_v < p_u$ for all $u \in N(v)$.
\item[3)]
$V' = V - N(I) -I$ and $E' = \{(u,v) \in E \quad | \quad u,v \in V'\}$    
\item[4)] 
return $I * MIS(G'=(V',E'))$  
\end{mylist}

The goal of this problem is to show that with high probability MIS
will be called at most $O(\log n)$ times. In parts 2. and 3. below you
need not use the constants that I have used. 

For each call prove the following:

\begin{mylist}{.1 in}
\item[1.]
$Prob(v \in I) = \frac{1}{d(v)+1}$
\item[2.]
Pick a definition of a ``good'' vertex and a ``good'' edge. I picked 
$v$ is {\bf good} if 
\[
\sum_{u \in N(v)} \frac{1}{d(u)+1} \geq 1/3
\] 
\item[3.]
If $v$ is good then $Prob(v \in N(I)) \geq 1/9$ \\
Hint: Show that if $u$ and $w$ are two distinct vertices which do not
share an edge then
\[
\mbox{Prob}[u \in I \quad  \& \quad w \in I] =
\frac{d(u)+d(w)+2}{(d(u)+1)(d(w)+1)(d(u)+d(w)+2-k)}
\]
where $k$ is the number of vertices common to $u$ and$w$.

\item[3.]
The expect number of edges deleted is at least $|E|/18$
\end{mylist}

For each of the parts you may use results from Kozen.   

\section{Computing the minimum number of registers}
Let $\cal T$ an arbitrary computation tree over the domain of integer
$\cal Z$ with the operation at the internal nodes being $\{\oplus\}$
defined as following: 
\[
\oplus(a,b)=\left\{ \begin{array}{ll}
a + 1                                   & a = b \\
max(a,b)                                & otherwise 
\end{array}
\right. 
\]


Show that any tree over this operation can be evaluated in $O(\log n)$
time using $n/\log n$ processors.

Hint: Consider the following class of function:
\[
{\cal F}=\{f_{a,b}\mid a\in {\cal Z}\cup \{-\infty\}, b\in 
{\cal Z}, a \leq b \}
\]  
where
\[
f_{a,b}(x)=\left\{ \begin{array}{ll}
a            & x < a \\
\max(b,x)    &  \mbox{otherwise}\\
\end{array}
\right. 
\]


\section{Parallel Selection}

Consider the $O(n)$ deterministic sequential algorithm for section,
see page 190 of CLR.

\begin{problem}
Write this algorithm as a parallel algorithm using the parallel
constructs from class without changing the work performed. 
Analysis the asymptotic time for your parallel algorithm?
\end{problem}


Consider the Randomized-selection algorithm, see page 187 of CLR.

\begin{problem}
Write this algorithm as a parallel algorithm using the parallel
constructs from class without changing the work performed. 
Analysis the asymptotic expected time for your
parallel algorithm? Instead of computing the expect time you may use
Chernoff Bounds to bound the running time with high probability.
\end{problem}


\end{document}
