algorithms.tex

\PassOptionsToPackage{bookmarks={true}}{hyperref}
\pdfminorversion=4
\documentclass[mathserif,xcolor={dvipsnames,table}]{beamer}
\mode<presentation>{\usetheme{Warsaw}\usecolortheme{crane}}
\usepackage{centernot}
\usepackage{upgreek}
\usepackage{graphicx}
\usepackage{geometry}
\usepackage{transparent}
\usepackage{tikz}
\usetikzlibrary{shadows}
\usepackage[utf8]{inputenc}
\usepackage[english]{babel}
\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[babel=true]{microtype}
\usepackage{amsmath}
\beamertemplatenavigationsymbolsempty

\title{\textbf{Algorithms Worth Knowing}}
\date{}
\author{CS4803UWS at the\\
Georgia Institute of Technology
}

\begin{document}

{
\setbeamertemplate{background canvas}{%
\includegraphics[width=\paperwidth,height=\paperheight]{images/gt2.jpeg}
}%
\begin{frame}[plain]
\textcolor{white}{
\transparent{0.5}%
\colorbox{black}{\textbf{algorithms worth knowing}}
}
\vspace{2.7in}
\\
\hfill\includegraphics[scale=.25]{images/cc-logo.pdf}
\includegraphics[scale=.25]{images/cc-new.pdf}
\includegraphics[scale=.25]{images/cc-share.pdf}
\textcolor{white}{
\\
\hfill \tiny{CC3.0 share-alike attribution}\\
}
\textcolor{white}{
\hfill \scriptsize{copyright \copyright\ 2013}\\
}
\end{frame}
}

\begin{frame}{von Neumann's debiasing scheme}
\huge FIXME
\end{frame}

\begin{frame}{Bitonic sorters / sorting networks}
\huge FIXME
\end{frame}

\begin{frame}{Skip lists}
\huge FIXME
\end{frame}

\begin{frame}{Dancing links}
\huge FIXME
\end{frame}

\begin{frame}{Timer wheels}
\huge FIXME
\end{frame}

\begin{frame}{Interval trees}
\huge FIXME
\end{frame}

\begin{frame}{Space-filling curves and spatial indexing}
\huge FIXME
\end{frame}

\begin{frame}{Dynamic perfect hashing / $y$-fast tries}
\huge FIXME
\end{frame}

\begin{frame}{CityHash / SpookyHash}
\huge FIXME
\end{frame}

\begin{frame}{Fragment reassembly}
\huge FIXME
\end{frame}

\begin{frame}{VLHU}
\huge FIXME
\end{frame}

\begin{frame}{Mersenne Twister}
\huge FIXME
\end{frame}

\begin{frame}{Levenshtein automata / Burkhard-Keller trees}
\huge FIXME
\end{frame}

\begin{frame}{Cuckoo hashing}
\huge FIXME
\end{frame}

\begin{frame}{FunnelSort / FunnelHeap}
\huge FIXME
\end{frame}

\begin{frame}{Bloom filters}
\huge FIXME
\end{frame}

\begin{frame}{Loop detection (Floyd/Gosper, Nivasch)}
\huge FIXME
\end{frame}

\begin{frame}{PATRICIA (compact prefix) tries}
\huge FIXME
\end{frame}

\begin{frame}{Level compressed tries (LC-TRIE)}
\huge FIXME
\end{frame}

\begin{frame}{String searching I (Boyer-Moore-Galil)}
\huge FIXME
\end{frame}

\begin{frame}{String searching II (Aho-Corasick)}
\huge FIXME
\end{frame}

\begin{frame}{String searching III (Wu-Manber, Set Horspool, BNDM)}
\huge FIXME
\end{frame}

\begin{frame}{String searching IV (Volnitsky)}
\huge FIXME
\end{frame}

\begin{frame}{Parallel merge sort}
\huge FIXME
\end{frame}

\begin{frame}{Large matrices (Strassen, Coppersmith-Winograd)}
\huge FIXME
\end{frame}

\begin{frame}{Recommended reading}
\footnotesize{
\begin{itemize}
\item David Clark. ``RFC 815: IP Datagram Reassembly Algorithms'' (1982).
\item Geoff Pike. ``CityHash: Fast Hash Functions for Strings'' (2012).
\item Harald Prokop. ``Cache-Oblivious algorithms'' (1999).
\item Erik Demaine. ``Cache-Oblivious algorithms and data structures'' (2002).
\item Michael Mitzenmacher. ``Cuckoo Hashing: Theory and Practice'' (2007).
\item Daniel Rockmore. ``FFT: An algorithm the whole family can use'' (2000).
\item Olsson and Nilsson. ``TRASH: A dynamic LC-trie and hash'' (2010).
\item Dan Willard. ``$\log\log$ range queries are possible in space $\Theta(n)$'' (1983).
\item Leonid Volnitsky. ``Substring search algorithm'' (2012).
\item Nick Black. ``LRUmap: $\mathcal{O}(1)$ massively-scalable LRU'' (2010).
\item Henry Warren. \textit{Hacker's Delight (2e)} (2012).
\item Donald Knuth. \textit{The Art of Computer Programming, Vol. 2: Seminumerical Algorithms (3e)} (1997),
\textit{Vol. 4A: Combinatorial Algorithms, Part I} (2011).
\end{itemize}
}
% Aggregate Magic
% Aronson's bit-twiddling algorithms...
\end{frame}

\begin{frame}{Hack on!}
\small{``The experiences of various groups who work on problem solving, theorem
proving and pattern recognition all seem to point in the same direction: These
problems are tough. There does not seem to be a royal road or a simple method
which at one stroke will solve all our problems. My discussion of ultimate
limitations on the speed and amount of data processing may be summarized like
this: Problems involving vast numbers of possibilities will not be solved by
sheer data processing quantity. We must look for quality, for refinements, for
tricks, for every ingenuity that we can think of. Computers faster than those
of today will be a great help. We will need them. However, when we are
concerned with problems in principle, present day computers are about as fast
as they ever will be.\\
\vspace{.1in}
We may expect that the technology of data processing will proceed step by
step---just as ordinary technology has done. There is an unlimited challenge
for ingenuity applied to specific problems.''}\\
\vspace{.1in}
\scriptsize{\hfill---Hans-Joachim Bremermann,\\ \hfill``Optimization through evolution and recombination'' (1962).}
\end{frame}

\end{document}