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

\addtolength{\topmargin}{-.2in}
\setlength{\textheight}{9in}

\setcounter{page}{0}

%\newcommand{\pr}{\problem}
\newcommand{\pr}{\newpage\problem}
\renewcommand{\bparts}{\begin{testproblemparts}}
\renewcommand{\eparts}{\end{testproblemparts}}

\begin{document}

\examinitials{Quiz 2}{April 25, 1995}


\begin{closeitemize}
\item This quiz is open book. 

\item Put your name on the top of each page---the pages of this booklet  
will be separated for grading.

\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.  {\bf Be neat}.

\item This quiz ends at 9 {\sc p.m.} It contains six problems.  The 
problems are 16 points each, and you will get 4 points for writing
your name, tutorial TA and time clearly. 

\item GOOD LUCK!
\end{closeitemize}

\bigskip
\bigskip

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

\noindent Name:\ \mbox{}\hrulefill\mbox{}\par
\bigskip \bigskip
\noindent Please circle your tutorial TA:
 \hspace{.7in} Jennifer
 \hspace{.7in} Parry
 \hspace{.7in} Steve
 \hspace{.7in} Ravi
\bigskip
\bigskip

\noindent Please circle your tutorial  time: 
\hspace{.5in} 10
\hspace{.5in} 11
\hspace{.5in} 12
\hspace{.5in} 1
\hspace{.5in} 2
\hspace{.5in} 3
\newpage
\begin{problems}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr 
\points{16} 

Prove that if
\[\Lambda \cup \{\psi\} \models \chi \mbox{ and }
\Lambda \cup \{\phi\} \models \chi \mbox{ and }
\Lambda \models \psi\vee \phi
\]
then
\[
\Lambda \models \chi
\]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr  
\points{16} 

%Prove or disprove:
%$f(n)=O(g(n))$ implies $\lg(f(n)) = O(\lg(g(n)))$, where $\lg(g(n)) > 0$ and
%$f(n) \geq 1$ for all sufficiently large $n$.

Prove or disprove: $f(n)=O(g(n))$ implies $\lg(f(n) = O(\lg(g(n)))$,
where $g(n)$ is nondecreasing, $g(1) > 1$ and $f(n) \geq 0$ for all
sufficiently large $n$.



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

\pr 
\points{16} 

Solve the following recurrence:
\[
f(1)=f(2)=1
\]
\[
f(n)-4(n-1)+4(n-2) = 3^n
\]

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

\pr
\points{16}
 
Give tight ($\Theta$) bounds for $T(n)$. Assume that $T(n)$ is constant for $n \leq 2$.

\bparts
\ppart $T(n) = 7T(n/3) + n^2$
\bigskip
\bigskip
\bigskip
\ppart $T(n) = T(2n/3) + T(n/4) + n$
\bigskip
\bigskip
\bigskip
\ppart $T(n) = 4T(n/3) + n$
\eparts

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

\pr  
\points{16} 

\bparts
\ppart How many ways are there to color $n$ (distinguishable) balls
using exactly $k$ colors? (Use no more and no fewer than $k$ colors)
\bigskip
\bigskip
\bigskip
\ppart If $x > k$ colors are available, how many ways are there to color
the $n$ balls using exactly $k$ of those colors?
\bigskip
\bigskip
\bigskip
\ppart Prove that
\[
x^n = \sum_{k=1}^n S(n,k)\cdot x(x-1)\cdots(x-k+1)
\]
by showing that the two sides agree for any positive integer $x$. ($S(n,k)$ is the Stirling number of the second kind.)

\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\pr
\points{16} 

How many permutations of ABCDEFG are there that don't contain
``$\cdots$BEG$\cdots$'' or ``$\cdots$AD$\cdots$''?

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


\end{problems}

\end{document}


