%% This LaTeX-file was created by <jl> Wed Feb 11 11:53:49 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}

2/11/98 day 10 Qoute of the day, ``Someone has to be bigger than the other.''


\section{Union find}


\subsection{operations}

\begin{itemize}
\item \emph{union(\( u,v \))}
\item \emph{is \( u=v \)}? = (find(v)=find(u))
\end{itemize}
used by Kruskal's algorithm


\subsection{implementation}

Have a large array (one entry per element) which points towards a representative
member of each equivalence class. Each equivalence class has some root representative
member. 


\subsubsection{implementing union}

Union is implemented by linking the root of one tree to the root of another
tree.

Improvement: (weighted union) Link the smaller tree to the larger tree to improve
balance. It's necessary to keep along a 'size' field.


\subsubsection{find}

Recurse towards the root and return the root.

Improvement: (path compression) When you find the representative from an element,
adjust every pointer in the path to point directly towards the root.


\subsection{analysis}


\subsubsection{Tree height limitation}

Let T, a tree. height(T)=\#edge on max length path

lemma: with weighted union \( |T|\geq 2^{height(T)} \)

proof: assume \( |T_{1}|\geq 2^{h(T_{1})} \), \( |T_{2}|\geq 2^{h(T_{2})} \) and without loss of generality \( |T_{1}|\geq |T_{2}| \)

\( T=union(T_{1},T_{2}) \).

case 1: \( height(T)=height(T_{1}) \). Ok, because the height hasn't increased while the size has.

tcase 2: \( height(T)=1+height(T_{2}) \). Ok, because \( 2^{1+height(T_{2})}=2*2^{height(T_{2})} \) \( \leq 2*|T_{2}|\leq |T_{2}|+|T_{1}|=|T| \)


\subsubsection{Ackermann function}

\begin{itemize}
\item \( A_{0}(x)=x+1 \)
\item \( A_{k+1}(x)=A_{k}^{x}(x) \) where \( A_{k}^{i}(x)=A_{k}(A_{k}(...(A_{k}(x))..) \)
\end{itemize}
This is pretty fast. 

\begin{itemize}
\item \( A_{0}(x)=x+1 \)
\item \( A_{1}(x)=A_{0}^{x}(x)=2x \)
\item \( A_{2}(x)=A_{1}^{x}(x)=2^{x}x \)
\item \( A_{3}(x)=A_{2}^{x}(x)\geq 2^{2^{.^{.^{.^{2}}}}}x \) etc...
\end{itemize}
Now, define the ackermann function as \( A(k)=A_{k}(2) \).

Define the inverse Ackermann as: \( \alpha (n)=min\{k:A(k)\geq n\} \). This grows pretty slow.


\subsubsection{union find analysis}


\paragraph{Theorem: with m union find and n objects, the timing is \protect\( O((m+n)\alpha (n))\protect \).}


\paragraph{proof:}

\begin{itemize}
\item \( T_{t}(u)= \) subtree rooted at u at time t
\item \( rank_{t}(u)=2+height(T_{t}(u)) \)
\end{itemize}
Rank increases while a node is a root, but never increases when it is not a
root.


\paragraph{lemma: if \protect\( \exists \protect \) time s.t. u is a descendent of v, then \protect\( rank(u)\leq rank(v)\protect \) then it will be true forever
after.}


\paragraph{lemma: max rank \protect\( \leq \left\lfloor log(n)\right\rfloor +2\protect \)}


\paragraph{proof: \protect\( n\geq |T(u)|\geq 2^{h(T(u))}\geq 2^{rank(u)-2}\protect \)}


\paragraph{lemma: \protect\( |\{u|rank(u)=v\}|\leq \frac{n}{2^{v-2}}\protect \) proof: a matter of counting}

define: \( 0\leq \delta (u)=max\{k|rank(parent(u))\geq A(rank(u)) \). Then for \( n\geq 5 \), \( \delta (n)\leq \alpha (n) \)


\paragraph{Charging rules for find:}

\begin{itemize}
\item if \( \exists  \) ancestor(x)=y s.t. \( \delta (y)=\delta (x) \) then charge x
\item else charge 'Find'
\end{itemize}
'Find' has \( \alpha (n) \) cost because it can only be charged once for each value of \( \delta  \). 


\paragraph{Charge to x over all finds:}

let x' = parent(x), v = root

\begin{itemize}
\item \( rank(x')\geq A_{k}(rank(x)) \)
\item max i of rank(x') \( \geq A_{k}^{i}(rank(x)) \)
\item \( rank(v)\geq rank(y')\geq A_{k}(rank(y)\geq A_{k}(rank(x'))\geq A_{k}(A_{k}^{i}(rank(x)))=A_{k}^{i+1}(rank(x)) \)
\end{itemize}
If x gets \( rank(x) \) charges then \( \delta (x) \) increases. This means it can in incur at most \( rank(x)\alpha (n) \) charges.
This is a rather large number in comparison to \( \alpha (n) \) but we are save by the lemma
limiting the number of nodes at a particular rank.

total charges \( <\sum _{i=1}^{log(n)}r\alpha (n)(\frac{n}{2^{r-2}})\leq n\alpha (n)\sum _{i=1}^{infinity}\frac{r}{2^{r-2}}=O(n\alpha (n)) \)

This means with m union-finds on a set of size n, the timing is \( O((m+n)\alpha (n)) \)

\end{document}