%\documentstyle[10pt,twoside]{article}
\documentstyle[twoside]{article}
\setlength{\oddsidemargin}{0.25 in}
\setlength{\evensidemargin}{-0.25 in}
\setlength{\topmargin}{-0.6 in}
\setlength{\textwidth}{6.5 in}
\setlength{\textheight}{8.5 in}
\setlength{\headsep}{0.75 in}
\setlength{\parindent}{0 in}
\setlength{\parskip}{0.1 in}

%
% The following commands sets up the lecnum (lecture number)
% counter and make various numbering schemes work relative
% to the lecture number.
%
\newcounter{lecnum}
\renewcommand{\thepage}{\thelecnum-\arabic{page}}
\renewcommand{\thesection}{\thelecnum.\arabic{section}}
\renewcommand{\theequation}{\thelecnum.\arabic{equation}}
\renewcommand{\thefigure}{\thelecnum.\arabic{figure}}
\renewcommand{\thetable}{\thelecnum.\arabic{table}}

%
% The following macro is used to generate the header.
%
\newcommand{\lecture}[4]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{lecnum}{#1}
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CMPUT 675: Randomized Algorithms
                        \hfill Fall 2005} }
       \vspace{4mm}
       \hbox to 6.28in { {\Large \hfill Lecture #1: #2  \hfill} }
       \vspace{2mm}
       \hbox to 6.28in { {\it Lecturer: #3 \hfill Scribe: #4} }
      \vspace{2mm}}
   }
   \end{center}
   \markboth{Lecture #1: #2}{Lecture #1: #2}
   \vspace*{4mm}
}

%
% Convention for citations is authors' initials followed by the year.
% For example, to cite a paper by Leighton and Maggs you would type
% \cite{LM89}, and to cite a paper by Strassen you would type \cite{S69}.
% (To avoid bibliography problems, for now we redefine the \cite command.)
%
\renewcommand{\cite}[1]{[#1]}

\input{epsf}

%Use this command for a figure; it puts a figure in wherever you want it.
%usage: \fig{NUMBER}{FIGURE-SIZE}{CAPTION}{FILENAME}
\newcommand{\fig}[4]{
			\vspace{0.2 in}
			\setlength{\epsfxsize}{#2}
			\centerline{\epsfbox{#4}}
			\begin{center}
			Figure \thelecnum.#1:~#3
			\end{center}
	}

% Use these for theorems, lemmas, proofs, etc.
\newtheorem{theorem}{Theorem}[lecnum]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newenvironment{proof}{{\bf Proof:}}{\hfill\rule{2mm}{2mm}}

% Some useful equation alignment commands, borrowed from TeX
\makeatletter
\def\eqalign#1{\,\vcenter{\openup\jot\m@th
  \ialign{\strut\hfil$\displaystyle{##}$&$\displaystyle{{}##}$\hfil
      \crcr#1\crcr}}\,}
\def\eqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\llap{$##$}\tabskip\z@skip\crcr
    #1\crcr}}
\def\leqalignno#1{\displ@y \tabskip\@centering
  \halign to\displaywidth{\hfil$\displaystyle{##}$\tabskip\z@skip
    &$\displaystyle{{}##}$\hfil\tabskip\@centering
    &\kern-\displaywidth\rlap{$##$}\tabskip\displaywidth\crcr
    #1\crcr}}
\makeatother

% **** IF YOU WANT TO DEFINE ADDITIONAL MACROS FOR YOURSELF, PUT THEM HERE:

\begin{document}
%FILL IN THE RIGHT INFO.
%\lecture{**LECTURE-NUMBER**}{**DATE**}{**LECTURER**}{**SCRIBE**}
\lecture{1 Introduction }{Sep 8, 2005 }{Mohammad R. Salavatipour}{Mohammad R. Salavatipour}

% **** YOUR NOTES GO HERE:

% Some general latex examples and examples making use of the
% macros follow.  
%**** IN GENERAL, BE BRIEF. LONG SCRIBE NOTES, NO MATTER HOW WELL WRITTEN,
%**** ARE NEVER READ BY ANYBODY.
%This lecture's notes illustrate some uses of
%various \LaTeX\ macros.  
%Take a look at this and imitate.
%
%\section{Some theorems and stuff} % Don't be this informal in your notes!
%
%We now delve right into the proof.
%
%\begin{lemma}
%This is the first lemma of the lecture.
%\end{lemma}
%
%\begin{proof}
%The proof is by induction on \ldots.
%For fun, we throw in a figure.
%%%%NOTE USAGE !
%\fig{1}{1in}{A Fun Figure}{funfig.eps}
%
%This is the end of the proof, which is marked with a little box.
%\end{proof}
%
%\subsection{A few items of note}
%
%Here is an itemized list:
%\begin{itemize}
%\item this is the first item;
%\item this is the second item.
%\end{itemize}
%
%Here is an enumerated list:
%\begin{enumerate}
%\item this is the first item;
%\item this is the second item.
%\end{enumerate}
%
%Here is an exercise:
%
%{\bf Exercise:}  Show that ${\rm P}\ne{\rm NP}$.
%
%Here is how to define things in the proper mathematical style.
%Let $f_k$ be the $AND-OR$ function, defined by
%
%\[ f_k(x_1, x_2, \ldots, x_{2^k}) = \left\{ \begin{array}{ll}
%
%	x_1 & \mbox{if $k = 0$;} \\
%
%	AND(f_{k-1}(x_1, \ldots, x_{2^{k-1}}),
%	   f_{k-1}(x_{2^{k-1} + 1}, \ldots, x_{2^k}))
%	 & \mbox{if $k$ is even;} \\
%
%	OR(f_{k-1}(x_1, \ldots, x_{2^{k-1}}),
%	   f_{k-1}(x_{2^{k-1} + 1}, \ldots, x_{2^k}))	
%	& \mbox{otherwise.} 
%	\end{array}
%	\right. \]
%
%\begin{theorem}
%This is the first theorem.
%\end{theorem}
%
%\begin{proof}
%This is the proof of the first theorem. We show how to write pseudo-code now.
%%*** USE PSEUDO-CODE ONLY IF IT IS CLEARER THAN AN ENGLISH DESCRIPTION
%
%Consider a comparison between $x$ and~$y$:
%\begin{tabbing}
%\hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \= \hspace*{.25in} \=\kill
%\>{\bf if} $x$ or $y$ or both are in $S$ {\bf then } \\
%\>\> answer accordingly \\
%\>{\bf else} \\
%\>\>    Make the element with the larger score (say $x$) win the comparison \\
%\>\> {\bf if} $F(x) + F(y) < \frac{n}{t-1}$ {\bf then} \\%
%\>\>\> $F(x) \leftarrow F(x) + F(y)$ \\
%\>\>\> $F(y) \leftarrow 0$ \\
%\>\> {\bf else}  \\
%\>\>\> $S \leftarrow S \cup \{ x \} $ \\
%\>\>\> $r \leftarrow r+1$ \\
%\>\> {\bf endif} \\
%\>{\bf endif} 
%\end{tabbing}
%
%This concludes the proof.
%\end{proof}
%
%
%\section{Next topic}
%
%Here is a citation, just for fun \cite{CW87}.
%

% **** THIS ENDS THE EXAMPLES. DON'T DELETE THE FOLLOWING LINE:
\section{Introduction}
What is a randomized algorithm? Put it simply, any algorithm that makes random choices 
during its execution. We assume these algorithm have access to a source of fair random bits.
Why do we study and use randomized algorithms? There are several factors, some of the more
important ones are:

\begin{description}
\item{\bf Speed:} Randomized algorithms are usually fast, sometimes much faster than any
deterministic algorithm for the same problem. Even if the asymptotic running time is the
same as the deterministic one it can be faster in practice. For example QuickSort,
though has worse-case running time worse than that of MergeSort or Heapsort, it is the
fastest algorithm in practice. The disadvantage of some randomized algorithms (like QuickSort)
is that sometimes the running time is more than usual. Also, some randomized algorithms produce
a solution that is correct with high (but smaller than 1) probability, so there is a chance
that the solution is not correct.

\item{\bf Simplicity:} Even if the known randomized algorithm is not faster than the deterministic one,
it is often simpler. 

\item{\bf Only thing we can do:} In some situations, randomized algorithms are the only algorithms we know.
For example, in some protocols or online algorithms (in the presence of an adversary) randomness helps to
defeat the adversary, whereas any deterministic algorithm can be defeated by an adversary.
Or, to check if a multivariable polynomial is identical to zero we only know randomized algorithms.
Note that the description of the polynomial might be implicit, e.g. the determinant of a matrix whose entries
contain different variables. 
\end{description}

Randomized algorithms should not be confused with probabilistic analysis of algorithms and average case analysis:
in the average case analysis we assume some probability distribution (e.g. uniform) on input and then analyze the
running time based on the assumption that the input is drawn from that probability distribution (e.g. average
case analysis of QuickSort). However, when we analyze randomized algorithms we do not assume a particular (random)
distribution on input. The analysis must hold for all inputs.

\section{An Example: Comparing strings with communication costs}
Suppose that Alice and Bob each have an $n$-bit binary string, call them $a$ (for Alice) and $b$ (for Bob). 
They want to find out if these two strings are equal. There is a communication link between them over which they
can send bits. It is enough if one of them figures out whether $a=b$ or not.
However, there is a cost associated with each bit transmission. Clearly, any deterministic algorithm
needs to use $n$ bits of communication (Why?). Here we give a randomized algorithms which uses only $O(\log n)$ bits
and has a very high success probability. The idea behind the solution is general: instead of comparing two objects
from a large universe, map them into two objects from a smaller universe and then compare those two. These two
smaller objects behave as the fingerprint of the two larger ones.

We will fix the number $t$ later. Alice picks a prime number $p\leq t$ uniformly at random and then
sends both $p$ and $a\;{\rm mod}\; p$ to Bob. Bob computes $b\;{\rm mod}\;p$ and if it is equal to
$a\;{\rm mod}\;p$ then says they are equal. Otherwise he concludes that they are not equal.

Clearly if $a=b$ then this protocol gives the correct answer (since $a\;{\rm mod}\;p=b\;{\rm mod}\;p$).
However, if $a\not=b$ there is a chance that this algorithm give a wrong answer. We upper bound this probability
(and therefore find an upper bound on the error probability of the algorithm).

\begin{lemma}
With $t=c\cdot n\ln n$ for some large constant $c$: $\Pr[a\;{\rm mod}\; p=b\;{\rm mod}\;p]\in O(\frac{1}{c})$.
\end{lemma}
\begin{proof}
Since $|a-b|\leq 2^n$ and since every prime is at least 2, there are at most $n$ primes that divide $|a-b|$.
This is an upper bound on the number of ``dangerous'' primes, i.e. those that if we select the algorithm will fail.
The Prime Number Theorem says that the number of primes up to $x$ is about $\frac{x}{\ln x}$. Therefore, there
are $\frac{t}{\log t}$ primes that we can choose, out of which at most $n$ are dangerous. Thus:
\begin{eqnarray*}
\Pr[failure]=\Pr[a\;{\rm mod}\; p=b\;{\rm mod}\;p]&=&\Pr[p\;{\rm divides}\;|a-b|] \\
	&\leq& \frac{n}{\frac{t}{\ln t}}\\
	&=&\frac{n[\ln n + \ln\ln n + \ln c]}{c\cdot n\ln n} \in O(\frac{1}{c})
\end{eqnarray*}
\end{proof}

Therefore, the algorithm succeeds with probability at least $1-\epsilon$ where $\epsilon$ is made
arbitrary close to $0$ by making $c$ large enough.

\section{Paradigms for Randomized Algorithms}

{\bf Avoiding adversarial input (random reordering):} For deterministic algorithms, it is not difficult to
produce inputs that cause the algorithm to perform poorly. Randomness can be used to avoid
these situations . For example, compare the (deterministic) quicksort (where the pivot is always
the first element of the list) with randomized quicksort. Note that adversarial input could be
a well-structured input. For example, a sorted list causes the deterministic quicksort algorithm to
perform badly. The importance of foiling adversaries becomes more vivid in online algorithms.

{\bf Fingerprinting and hashing:} We use short fingerprints generated randomly for larger objects. Then we
only need to compare smaller objects (fingerprints). This is the idea behind hashing too where a small set $S$
of elements drawn from a large universe is mapped into a small set from a small universe.

{\bf Random sampling:} Used in graph algorithms, approximate counting, median finding, and several other
applications. The idea is that a random ``typical'' sample from a large population is a representation of
the whole population.

{\bf Load balancing:} Randomness can be used in problems where we want to spread the load among a
common resources, such as communication links.

{\bf Rapidly mixing Markov chains:} Is typically used to count the number of combinatorial objects with
certain properties (e.g. matchings, colorings). There are approximate algorithms based on random
sampling. However, generating a random sample is not always easy. In this technique, we show
that starting from an arbitrary sample and then doing a suitable random walk around this sample
in the space takes us to a random sample with high probability in a short amount of time.

{\bf Symmetry breaking:} Randomness can be quite helpful to keep everybody from doing the same thing.
For example, protocol in Ethernet card uses randomness to access the shared medium. Randomness
is also used to avoid deadlock in distributed systems.

{\bf Probabilistic Method and existential proofs:} The probabilistic method is a powerful technique in combinatorics.
The basic probabilistic method can be described as follows: in order to prove the existence of a combinatorial 
structure or object with certain properties, we construct an appropriate probability space and show that a randomly
chosen element in this space has the desired properties with positive probability.
In most applications, this probability is not only positive, but is actually high and frequently tends to 1 as the
parameters of the problem tend to infinity. This yields a randomized algorithm for constructing an object with
the desired properties. Sometimes we need to use more complicated techniques to turn these existential results
into randomized algorithms.


\end{document}


