\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}

\begin{document}
{\large
Algorithms Core 15-750 \hfill PROBLEM SET \# 6 \hfill Spring 1998
\begin{center}

DUE: 10:30AM Monday  27 April 1998 \\
\end{center}}


Answer each question on separate sheets of paper for grading purposes.
Make sure that each page has your name and email address.

Make sure that each algorithm you consider includes the following
three bullets. 
\begin{mylist}{.1 in}
\item[DESCRIPTION:] A high level description of the algorithm.
\item[CORRECTNESS:] At least a high level outline of how the full proof 
would go. Possibly citing lemmas from class.   
\item[TIMING:] A timing analysis.
\end{mylist}
The algorithms will be graded based on what you put in each bullet.

\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[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.]
If $v$ is good then $Prob(v \in N(I)) \geq 1/5$
\item[3.]
The expect number of edges deleted is at least $|E|/10$
\end{mylist}

Finally show that There exist a constant $c$ independent of $n$ such
that the probability that after $c \log n$ calls MIS is not finish is
at most $1/n$
   
\section{Toeplitz Matrices}
An $n \times n$ matrix $A$ is {\bf Toeplitz} if $A_{ij} = A_{i+1,j+1}$
for $0 \leq i,j \leq n-2$.

\begin{mylist}{.1 in}
\item
Is the sum (product) of Toeplitz matrices Toeplitz?
\item
Give a representation of Toeplitz matrices so that the sum is $O(n)$
time.
\item
Give an $O(n \log n)$ time algorithm for multiplying an $n \times n$
Toeplitz matrix by a length $n$ column vector. 
\item
Give an efficient algorithm for multiplying two $n \times n$ Toeplitz
matrices.
\end{mylist}




\end{document}