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

\parindent0pt

\begin{document}

\tutorial{tutorial4}{Problems for Tutorial 4}{March 3, 1997}

\begin{problems}

% a revamped 6.004 problem
\problem What does the following procedure compute?  Prove it.

\begin{tabbing}

something$(n, m)$ \\
\ \ \ \= $r \leftarrow m - n$ \\
      \> if $(r > 0)$ return$(n + \mbox{something}(n+1, m))$ \\
      \> else return(0) \\
\\
\end{tabbing}

% edited from an earlier tutorial problem
\problem  Bubble Sort is one of the simplest sorting algorithms.
Its goal is to put a list of $n$ numbers in increasing order.
Bubble Sort consists of $n - 1$ passes through the list.
On each pass, whenever an
element is encountered that is smaller than the element immediately
preceding it in the list, the two elements are interchanged.
If we imagine the list as running down a column, the smaller elements
will ``bubble'' upwards as they are interchanged with larger elements.
A pseudocode description of Bubble Sort is given below.

\begin{tabbing}
BubbleSort($a_{1},...,a_{n}$) \\
\ \ \ \= for $i = 1$  to $n-1$ \\
      \> \ \ \ \= for $j = 1$ to $n-i$ \\
      \>       \> \ \ \ \= if $(a_{j} > a_{j+1})$ interchange $a_{j}$ and $a_{j+1}$ \\
\\
\end{tabbing}

Use induction to prove that Bubble Sort will always terminate with the list sorted in increasing order.

\problem  We define a well-balanced string of parentheses to be:

\begin{itemize}

\item The empty string, $\epsilon$.

\item The string (V)W, where V and W are well-balanced strings of
parentheses.

\end{itemize}

The following procedure is designed to take an input that is a string
consisting only of left and right parentheses.
If its input is a well-balanced string of parentheses, it is meant
to return $\epsilon$.
If its input is a string of the form P)W, where P is a
well-balanced string of parentheses and W is an arbitrary
(possibly empty) string, then it is meant to return the string )W.
For any other input, it is meant to return the special value {\em error}.
It uses the auxiliary procedures First-char and Remove-first-char, which
return the first character of a string and everything but the first character
of a string, respectively.  (The strings are presumed to be non-empty in
both cases).

\begin{tabbing}

Check($w$) \\
\ \ \ \= if ($w = \epsilon$) return($\epsilon$) \\
      \> if (First-char($w$) = ``(") \\
      \> \ \ \ \= $w \leftarrow \mbox{Remove-first-char}(w)$ \\
      \>       \> $w \leftarrow \mbox{Check}(w)$ \\
      \>       \> if (($w = \epsilon$) or ($w = ${\em \ error})) \\
      \>       \> \ \ \ \= return({\em error}) \\
      \>       \> else \\
      \>       \>       \> $w \leftarrow \mbox{Remove-first-char}(w)$ \\
      \>       \>       \> $w \leftarrow \mbox{Check}(w)$ \\
      \> return($w$) \\
\\
\end{tabbing}

Is the procedure correct?  Either prove correctness or provide a
counterexample.  You should only consider inputs which consist entirely
of left and right parentheses.

\end{problems}

\end{document}







