splavl-tree/Online-Algorithms/abstract.tex

\documentclass[11pt]{article}
%\usepackage{clrscode3e}

\newcommand{\deq}{:=}
\newcommand{\RR}{\mathbb{R}}

\begin{document}
\begin{abstract}
\begin{center}
{\large \textbf{CS41 Final Project: Online Algorithms} }

\textbf{Tahmid Rahman, Dylan Jeffers}
\end{center}
\vspace{5 mm}
We plan to research online algorithms through a case analysis of splay
trees, an interesting self adjusting online search tree that is runtime competitive
with offline search trees counterparts. We first plan
to study the core online algorithm concepts such as 
the Competitive Ratio, the Least Recently Used Property and the Marking
Strategy. Afterwards, we will apply these concepts in solving a
 currently unsolved splay
tree problem, known as the Dynamic Optimality Conjecture, which 
claims that splay trees can perform as well as offline
search tree algorithms, up to a constant factor. There are modern research
papers on this topic that we plan to use as reference.\\

As solving the above conjecture may prove difficult, we
are also interested in implementing our own splay tree, with the objective
of testing previous theoretical work on splay tree runtimes. 
Through a careful study of how
splay trees evolve over different input sets (i.e. a random set vs.
partially ordered set) we hope to not only determine for which inputs
splay trees prove the most preferable tree structure, but also ways to 
alter its implementation to competitively handle more general inputs.\\ 

We are both excited to learn more about this interesting topic, and
believe it will positively impact our algorithmic studies.
\end{abstract}

\end{document}