\documentstyle[12pt,macpsfig]{article}
\input{/a/class/6.042/spring94/handouts/macros-course}
\input{psfig}
\setcounter{page}{0}

\begin{document}

\handout{quiz-solns}{Solutions to Quiz 1}{March 15, 1994}


\begin{closeitemize}

\item This quiz ends at 9 {\sc p.m.} It contains 10 problems.  You
have 120 minutes to earn 100 points.

\item This quiz is closed book.  You may use one $8\frac{1}{2}''\times
11''$ handwritten crib sheet.

\item Write your solutions in the space provided.  If you need more
space, write on the back of the sheet containing the problem.  Please do not
put part of the answer to one problem on the back of the sheet for
another problem.

\item Do not spend too much time on any problem.  Read them all
through first and attack them in the order that allows you to make the
most progress.

\item Show your work, as partial credit will be given.  You will be
graded not only on the correctness of your answer, but also on the
clarity with which you express it.  Be neat.

\end{closeitemize}

\renewcommand{\arraystretch}{.5}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& &\hspace*{1in}\\
Problem&Points&Grade\\
& &\\
\hline
\hline
& &\\
1 & 10 & \\
& &\\
\hline
& &\\
2 & 10 & \\
& &\\
\hline
& &\\
3 & 10 & \\
& &\\
\hline
& &\\
4 & 10 & \\
& &\\
\hline
& &\\
5 & 10 & \\
& &\\
\hline
& &\\
6 & 10 & \\
& &\\
\hline
& &\\
7 & 10 & \\
& &\\
\hline
& &\\
8 & 10 & \\
& &\\
\hline
& &\\
9 & 10 & \\
& &\\
\hline
& &\\
10 & 10 & \\
& &\\
\hline
\hline
& &\\
Total & 100 & \\
& &\\
\hline
\end{tabular}
\end{center}
\renewcommand{\arraystretch}{1}
\bigskip
\bigskip
\bigskip

\noindent Name:\ \mbox{}\hrulefill\mbox{}\par

\newpage
\begin{figure}[htbp]
\centerline{\psfig{figure=diag.ps,height=5in}}
\caption{Quiz 1 Statistics.}
% \\ 
%Note: For simplicity, only $l(A_4), r(A_4)$ and $S_2$ 
%are shown}
\label{fig:inter}
\end{figure}


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newpage \problem \points{10} Use the well-ordering principle to prove
that $\sqrt[3]{2}$ is irrational.

\newpage \problem \points{10} Use induction to prove that the sum of
the first $n$ odd numbers is~$n^2$.

\newpage \problem \points{10} Let $R_1$ and $R_2$ be binary relations 
on a set $A$.  Prove that if $R_1$ and $R_2$ are symmetric, then
$R_1\circ R_2$ is symmetric, or provide a counterexample.

\newpage
\problem \points{10} Use Stirling's formula $n! \sim \sqrt{2\pi
n}\paren{n/e}^n$ to show that \[\Choose{2n}{n}\sim
\frac{4^n}{\sqrt{\pi n}}\ .\]

\newpage \problem \points{10} Prove that in any undirected graph, the
sum of the squares of the vertex degrees is even, or provide a
counterexample.

\newpage \problem \points{10} Consider a binary tree $T$, and let $L$
be the set of leaf nodes of~$T$.  For any node $x$ in $T$, define
$w(x)=2^{-d}$, where $d$ is the depth (distance from the root) of~$x$.
Prove by induction that
\[\sum_{x\in L} w(x)\leq 1\ .\]

\newpage \problem \points{10} Consider the following recursive sorting
algorithm:

\codebox{%
\<$\procdecl{Sort}(A, i, j)$\\
\li \If $A[i]>A[j]$\\
\li \Then exchange $A[i] \leftrightarrow A[j]$\\
\li \If $i+1\geq j$\\
\li \Then \Return\\
\li $k\gets\floor{(j-i+1)/3}$\>\>\>\>\>\>\>\>\Comment Round down.\\
\li $\proc{Sort}(A,i,j-k)$\>\>\>\>\>\>\>\>\Comment Sort first two-thirds.\\
\li $\proc{Sort}(A,i+k,j)$\>\>\>\>\>\>\>\>\Comment Sort last two-thirds.\\
\li $\proc{Sort}(A,i,j-k)$\>\>\>\>\>\>\>\>\Comment Sort first two-thirds again.}

\begin{problemparts}

\problempart Argue that \proc{Sort}$(A,1,n)$ correctly sorts the input
array $A[1 \twodots n]$. 

\newpage

\problempart Give a recurrence for the worst-case running time of
\proc{Sort} and a tight asymptotic ($\Theta$) bound on the worst-case
running time.

\vspace*{5in}

\problempart Compare the worst-case running time of \proc{Sort} with
that of insertion sort and merge sort.

\end{problemparts}

\newpage
\problem \points{10}

For each function $f(n)$ along the left side of the table below and
each function $g(n)$ across the top, write $O$, $\Omega$, or $\Theta$
in the appropriate space, depending on whether $f(n)=O(g(n))$,
$f(n)=\Omega(g(n))$, or $f(n)=\Theta(g(n))$.  If there is more than
one relation between $f(n)$ and $g(n)$, write only the strongest one.
{\em Wrong answers will be penalized, so do not guess unless you are
reasonably sure.} The first line is a demo solution.

\[
\begin{array}{|c||c|c|c|}
\hline
& \hspace*{1in} & \hspace*{1in} & \hspace*{1in} \\
& n & n\lg n & n^2\\
& & & \\
\hline
\hline
& & & \\
3n\lg n & \Omega & \Theta & O \\
& & & \\
\hline
& & & \\
n^{0.99} \lg^2 n& & & \\
& & & \\
\hline
& & & \\
2n^2-5n\lg n& & & \\
& & & \\
\hline
& & & \\
\lg(n!)& & & \\
& & & \\
\hline
& & & \\
3^{\lg n}& & & \\
& & & \\
\hline
& & & \\
{\displaystyle \sum_{i=1}^n\lg i}& & & \\
& & & \\
\hline
\end{array}
\]

\newpage \problem \points{10} Use the substitution method (guess and
verify) to determine an asymptotic upper (big $O$) bound on the
recurrence
\[T(n) = \cases{ 1 & \cif{n\leq 3},\\
		T(\floor{n/2}) + T(\floor{n/4}) + n & \cif{n>3}.}\]

\newpage \problem \points{10} Use the method of characteristic
equations to solve the linear recurrence \[f(n) = 5f(n-1) - 6f(n-2) +
7^n\ ,\] where $f(1) = 1$ and $f(2)=2$.  (For partial credit, solve
only the homogeneous recurrence, that is, drop the $7^n$ term.)

\end{problems}

\end{document}
