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

\setcounter{page}{0}

\begin{document}

\handout{old-quiz-1}{Practice Quiz 1}{March 7, 1994}
%\exam{Quiz 1}{March 12, 1991}


\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.  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


\begin{problems}

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

\newpage
\problem \points{10} Show that any dag (directed acyclic graph) 
has a vertex with out-degree $0$.

\newpage
\problem \points{10} Prove that the sum of the first $n$ squares 
is~$\Theta(n^3)$.

\newpage
\problem \points{10} Let $R_1$ and $R_2$ be relations on $A\times B$.  
Prove that
if $R_1$ and $R_2$ are transitive, then $R_1\bigcap R_2$ is transitive.

\newpage
\problem \points{10} Let $T$ be a binary search tree whose keys are distinct, 
let $x$ be a leaf node, and let $y$ be its parent. Show that $key[y]$ 
is either the smallest key in $T$ larger than $key[x]$ or the largest 
key in $T$ smaller than $key[x]$.

\newpage
\problem \points{10} Use Stirling's formula $n! \sim \sqrt{2\pi
n}\paren{n/e}^n$ to show that \[\displaystyle \Pi_{i=1}^n (2i-1) \sim
\sqrt{2}(2n/e)^n .\]

\newpage
\problem \points{10} Prove that every free tree with more than one node 
has at least two leaves, i.e. nodes of degree 1 (\hint Handshaking Lemma).

\newpage
\problem \points{10} Prove that any graph with $2n$ nodes and 
no $3$-cycles has at most $n^2$ edges (\hint in inductive step, remove
from the graph on $2n+2$ vertices, two adjacent vertices so at most
$2n+1$ edges are removed).

\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 stongest 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} \\
& \lg n & n & n^2\\
& & & \\
\hline
\hline
& & & \\
2^{\lg\lg n} & \Theta & O & O \\
& & & \\
\hline
& & & \\
4^{\lg n}& & & \\
& & & \\
\hline
& & & \\
\lg (n!)& & & \\
& & & \\
\hline
& & & \\
n/\lg n& & & \\
& & & \\
\hline
& & & \\
n^2 + n + \lg n& & & \\
& & & \\
\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{\Theta(1) & \cif{n=1},\\
		T(n-1) + \lg n& \cif{n>1}.}\]

\newpage
\problem \points{10} Use the method of characteristic equations to
solve the linear recurrence \[f(n) = f(n-1) + f(n-2) + 1\ ,\] where
$f(1) = 1$ and $f(2)=2$.

\end{problems}

\end{document}
