\documentclass{beamer}
\setbeamertemplate{navigation symbols}{}
\usepackage{hyperref}
\usepackage{color}
\usepackage{alltt}
\usetheme{Marburg} %Berkeley}

\usecolortheme{beaver}
\usepackage{endnotes}
\usepackage[ngerman]{babel}

\usepackage[T1]{fontenc}
%\usepackage[urw-garamond]{mathdesign}

\begin{document}
\title{Hashing}
\author{Florian Kirmaier und Mathias Riegel}
\date{\today}
\begin{frame}
\titlepage
\begin{center} made with \LaTeX \end{center}
\end{frame}


\section{Einleitung}
\begin{frame}[fragile]\frametitle{Table of contents}\tableofcontents
\end{frame}

\subsection{Die Hashfunktion}
\begin{frame}[fragile]\frametitle{Die Hashtabelle}
M = Index
0 $\leq$ h(k) < M

h'(x) = h(x) \% M'

\quad

\pause
Operationen:
\begin{itemize}
\item
Search
\item
Insert
\item
Remove
\end{itemize}

\end{frame}

\section{geschlossene Hashverfahren}
\begin{frame}
Mit Liste oder Baum als Struktur
\end{frame}

\subsection{Bucketsort} % zweimal? überhaupt nicht?


\subsection{Dynamisches Hashing}



\section{offene Hashverfahren}

\subsection{Einleitung}

\subsection{Lineares Sondieren}
\begin{frame}
Sondierungsfunktion:
s(i,k)
\end{frame}

\subsection{Deletion}

\subsection{Lazy Deletion}

\subsection{Deletion mit Linearen Sondieren}
\begin{frame}
Der folgende Algorithmus verhindert, dass Felder als occupied markiert werden: \pause

Vorbedingung: i ist der Index der Zelle die gel\"öscht werden soll.\pause

\begin{tabular}{ll}
R1 & $ Table[i] \leftarrow Empty $ \\
   & j $\leftarrow$ i \\
R2 & i $\leftarrow$ i - 1 \\
   & if i < 0 then i $\leftarrow$ i + M \\
R3 & if $ Table[i] = Empty $ then terminate \\
   & $ r \leftarrow h(Table[i]) $ \\
   & $ if ( i \leq r < j \vee r < j < i \vee j < i \leq r) Goto R2 $ \\
R4 & $ Table[j] \leftarrow Table[i] $ \\
   & Goto R1 \\

\end{tabular}

\quad
\end{frame}


\subsection{Quadratisches Sondieren}
\begin{frame}
Sondierungsfunktion: \\
$ S(i,k) = i^{2} $ \\
\end{frame}


\subsection{Double-Hashing}
\begin{frame}
Sondierungsfunktion: \\
$ S(i{,} k) = i * h'(k) $ \\
Wobei h' eine neue Hashfunktion ist!
\end{frame}

\subsection{Brent-Hashing}
%todo



\end{document}