\documentstyle [11pt]{article}
\setlength{\parskip}{2 ex}
\setlength{\topmargin}{-0.5 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{9.5 in}
\setlength{\textwidth}{6.5 in}
\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}
\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcommand{\ceiling}[1]{\lceil #1 \rceil}

\begin{document}
{\large
Algorithms Core 15-750 \hfill PROBLEM SET \# 2 \hfill Spring 1998
\begin{center}

DUE: 10:30AM Wednesday 18 February 1998 \\
\end{center}}


\section{Amortized Analysis}

Show how to implement a linear-time dynamic data structure supporting
the First-In-First-Out (FIFO) queue operations: {\tt Enqueue}, {\tt
Dequeue} and {\tt Minimum}.  The {\tt Minimum} operation should
report the smallest value currently in the queue.  [Hints: (1) Aim
for $O(1)$ amortized costs. (2) You may want to use two arrays.]

\section{Maintaining a list with reversals}
\vspace*{-.2in}
Consider a data structure that represents an ordered list of elements
under the following three types of operations:

\begin{mylist}{reverse$(i,j)$x}
\litem{access$(k)$:}
Return the $k$th element of the list (in its current order).
\litem{insert$(k,x)$:}
Insert $x$ (a new element) after the $k$th element in the current
version of the list.
\litem{reverse$(i,j)$}
Reverse the order of the $i$th through $j$th elements.
\end{mylist}
For example, if the initial list is $[a,b,c,d,e]$, then access(2)
returns $b$.  After reverse(2,4), the represented list becomes
$[a,d,c,b,e]$, and then access(2) returns $d$.

\subsection{Reversals using Splay Trees}

Show how to modify splay tree construction so that
each operation runs in $O(\log n)$ amortized time, where $n$ is
the (current) number of elements in the list.  The list starts out
empty.

Hint: First consider how to implement access and insert using splay
trees.  Then think about a special case of reverse in which the
$[i,j]$ range is represented by a whole subtree.  Use these ideas to
solve the real problem.  Remember, if you store extra information in
the tree, you must state how this information can be maintained under
various restructuring operations.

(This data structure is useful in efficiently implementing the Lin
Kernighan heuristic for the travelling salesman problem.  This is a
good idea for a project in this course.)

\subsection{Reversals using Treaps}

Show how these three operations can also be implemented in $O(log n)$
expected time using treaps.

\end{document}