\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS7800}{Advanced Algorithms}{Fall 2014}{8 September 2014}{3}

\begin{center}
\Large{\bf Problem of the Week -- 2}
\end{center}

{\noindent \bf Lower bound on almost-sorting}

We know that every comparison-based sorting algorithm needs to make
$\Omega(n \log n)$ comparisons to sort an $n$-element list.  Some
applications are happy to work with partially sorted lists.  Call a
list {\em sorted-to-within-$k$}\/ if every element in the list is
within $k$ positions of its position in the sorted list.  (Assume that
all elements are distinct.)

Give your best lower bound, in terms of $n$ and $k$, on the number of
comparisons needed by an algorithm that takes as input an $n$-element
list and returns a sorted-to-within-$k$ list containing the same
elements.


\end{document}
