\documentclass{article}
\pagestyle{empty}

\begin{document}
\begin{center}
{\LARGE CS140: Algorithms }\\
\vspace{.1 in}
{\Large Spring 2001}\\
\vspace{.3 in}
{\large Assignment 4}
\end{center}

\noindent
This assignment is due at the start of class on Thursday, Feb. 1.  You may collaborate
with your classmates to complete this assignment but you should reference your collaborators.  You
also must thoroughly understand any solutions you submit 
and must do your own write-up of those solutions.  This assignment is worth 100 points (65 points if handwritten).  


\vspace{.2 in}

\begin{enumerate}

\item
Complete the last step in the analysis of Randomized Select by showing that
$f(n)=O(n)$ where
\begin{enumerate}
\item
$f(1)=c$
\item
For $n>1$, $f(n) \le cn + \frac{2}{n} \sum_{i=\lceil \frac{n+1}{2} \rceil}^n f(i-1)$
\end{enumerate}

\item
Complete the last step in the analysis of the Select algorithm that uses
median-of-medians pivots by showing that
$f(n)=O(n)$ where
\begin{enumerate}
\item
$f(1)=c$
\item
For $n>1$, $f(n) \le cn + f(n/5) + f(3n/4)$
\end{enumerate}


\item
A pair of fair die are tossed.  Let $X$ be the sum of the
values that appear.
\begin{enumerate}
\item
What is the sample space of $X$?
\item
What are the probabilities of the elementary events in
the sample space?
\item
What is $E[X]$?
\item
What is $E[X^2]$?
\end{enumerate}
\end{enumerate}


\end{document}

