\documentstyle[11pt,handout]{article}
\begin{document}
\input{localmacros}
\input{macros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{3390}{Analysis of Algorithms}{7 October 1998}{6}

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

\bigskip

A group of $n$ runners finished a close marathon race.  Unfortunately, the
officials at the finish line were unable to note down the order in which the
racers finished.  Each runner, however, noted the jersey number of the runner
finishing immediately ahead of her or him.  (There were no ties.)  The race
officials ask each runner to write on a separate sheet of paper two pieces of
information: (i) first, his or her own jersey number and (ii) second, the
jersey number of the runner who finished immediately ahead of him or her.  The
winner of the race, who did not see anybody finish ahead of her, did not turn
any information in.

Assuming each runner is honest, design and analyze an efficient algorithm for
reconstructing the order in which the runners finished from these $n - 1$
sheets of paper (given in a scrambled order)?

\junk{
{\noindent {\bf (b)} A group of $n$ people are having a round-table
discussion.  In order to be able to reconstruct the same seating order at a
later date, each person notes on a sheet of paper two pieces of information:
(i) first, his or her clockwise neighbor, and (ii) second, his or her
counterclockwise neighbor.  Can one reconstruct the ring from these $n$ sheets
of paper?  If so, design and analyze an efficient algorithm for this problem.
}}
\end{document}
