\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}{3 September 2014}{2}

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

{\noindent \bf Fitting hats on heads}

Planet Red Sox Nation ordered a Red Sox baseball hat for each of their
$n = 100,000$ members through IPS, the Interplanetary Parcel Service.
Each hat was ordered so as to perfectly fit the head of the
corresponding alien.  The hats were all delivered perfectly, but they
were all delivered together and no size was listed on any hat.  Though
all the alien heads and hats are round, there is no way to compare one
hat with another (the hats are too soft) or one alien head with
another (they don't like that).  The only comparison possible is by
fitting a hat on a head.  If a hat perfectly fits a head, then it will
be too big for smaller heads and too small for larger heads, and vice
versa.

The leader of the planet desperately and quickly wants to determine
which hat belongs to which alien, using the minimum number of hat-head
fittings as possible.  A deterministic procedure that needs $n(n-1)/2
= \Theta(n^2)$ fittings is easy to give.  

Can you help the leader do this with a {\em randomized}\/ algorithm
that uses expected $O(n \log n)$ fittings?  To earn the planet's Medal
of Honor, try coming up with an $o(n^2)$-fitting {\em deterministic}\/
algorithm.

\end{document}
