%% This LaTeX-file was created by <jl> Wed Apr  1 11:47:20 1998
%% LyX 0.12 (C) 1995-1998 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass{article}
\usepackage[T1]{fontenc}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\spacefactor1000}

\makeatother

\begin{document}

day 21 4/1/98 ``I knew there should have been another step in here.''


\section{Recurrence relations}

Running time of merge sort:

\( T(n)=2T(\frac{n}{2})+n \) with \( T(1)=0 \)

Assume we want \( T(n)=O(n) \)

Then \( T(n)=2O(\frac{n}{2})+n=O(n)? \) Wrong! Bad!

Instead, try: \( T(n)=cn \) then \( T(n)=2c\frac{n}{2}+n=(c+1)n \) which doesn't work.

try: \( T(n)=cn\log n \) then \( T(n)=2c\frac{n}{2}\log \frac{n}{2}+n \) \( =cn\log \frac{n}{2}+n \) \( =cn\log n-cn+n \) which is solvable for \( c=1 \).


\section{All Prefix scan}

The Random-Mate algorithm essentially has every node in the list guess it's
parity. The algorithm (covered last meeting) works in 2 phases. In the first
phase, nodes are eliminated while in the second phase, you back up the tree
filling in the values of each node as in Wiley's algorithm.


\subsection{Timing analyses}

Probability that a node is removed from the list at each stage in the forward
algorithm is \( \frac{3}{4} \). So \( P_{t}=(\frac{3}{4})^{t} \) = probability that a node is still in the list after \( t \)
rounds. If we want \( P_{t}=\frac{1}{n^{2}} \) then \( t=2\log _{\frac{4}{3}}n \).

The probability that no node is left in the list is: \( P_{left}\leq \sum _{i=1}^{n-1}P_{t}\leq nP_{t}\leq \frac{1}{n} \) if \( t=2\log _{\frac{4}{3}}n \)


\subsection{Work analyses}

Because of the random nature of this algorithm it is difficult to group enough
nodes on each processor s.t. every processor will always have work to do. A
prescan can be done over the elements to reallocate their location at each step.


\section{Another random list ranking algorithm}

\begin{enumerate}
\item Make \( \frac{n}{\log n} \) queues of size \( \log n \)
\item Set the sex of all nodes to M.
\item Reset sex of top in each queue to a random sex.
\item If top element is F and points to M, the splice out F
\end{enumerate}
The algorithm works on a doubly linked list.


\subsection{Timing analyses}

Timing is \( O(\log n) \) with high probability

Let \( P(head)=\frac{1}{4} \) and \( P(tail)=\frac{3}{4} \)

Let \( S^{p}_{t}=\#head \) in \( t \) trials.

\( P(S^{p}_{t}<\log n) \) can be bounded by Chernoff Bounds


\subsubsection{Chernoff Bound}

\( P(S_{t}^{p}<(1-\beta )pt)<e^{-\beta ^{2}\frac{pt}{2}} \) for \( 0\leq \beta \leq 1 \)

In particular, \( P(S_{16\log n}^{\frac{1}{4}}<(\frac{1}{4})4\log n)<e^{-\frac{3^{2}}{4^{2}}\frac{4\log n}{2}} \) \( =e^{-\frac{9}{8}\log n}=\frac{1}{n^{\frac{9}{8}}}<\frac{1}{n} \) 

= probability that a processor is not done.

The probability that all processors is done is \( \leq \sum _{i=1}^{n\log n}\frac{1}{n}=\frac{n}{\log n}\frac{1}{n}=\frac{1}{\log n} \).



\end{document}