\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial2}{Problems for Tutorial 2}{September 16, 1996}

\section*{Problem 1}

I recently went to a party with my spouse; there were 11 other
married couples there.  A lot of handshaking happened (but of course
no one shook hands with their spouse).  At the end, it turned out that
for every $k$ from $0$ to $22$, someone other than me had shaken hands
with exactly $k$ people.  How many people did I shake hands with?
Prove it.

\bigskip

\section*{Problem 2}

The {\bf bubble sort} is one of the simplest sorting algorithms.  It puts a list of numbers in increasing order by successively comparing adjacent elements, interchanging them if they are in the wrong order.  To carry out the bubble sort we perform the basic operation, that is, interchanging a larger element with a smaller one following it, starting at the beginning of the list, for a full pass.  We iterate this procedure until the sort is complete.  We can imagine the elements in the list placed in a column.  In the bubble sort, the smaller elements ``bubble'' to the top as they are interchanged with larger elements.
A pseudocode description of the bubble sort is given below.
\\
\\

\noindent {\bf procedure} {\it bubblesort}($a_{1},...,a_{n}$) \\
{\bf for} $i:=1$ {\bf to} $n-1$ \\
{\indent} {\bf for } $j:=1$ {\bf to } $n-i$ \\
{\indent} {\indent} {\bf if} $a_{j} > a_{j+1}$ {\bf then} interchange $a_{j}$ and $a_{j+1}$ \\
{\bf end}
\\

As a warmup, use bubble sort to put 3,2,4,1,5 in increasing order.  Then use induction to prove that the bubble sort will always terminate with the list sorted in increasing order.

\end{document}

 






