\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, Conflict Exam}{April 26, 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 is a two-hour quiz. 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} 

Let the universe be the nodes $V$ of a graph.
Let $E(x,y) = 1$ iff there is an edge from node $x$ to node $y$.
Let $A: V \mapsto \{0,1\}$ be a function from $V$ to $\{0,1\}$.
$R, B, G$ are also functions from $V$ to $\{0,1\}$.
What graph properties do the following sentences express? 
  
\bparts
\ppart
 $  \exists A \, [\exists x,y  \, (A(x) \wedge \neg A(y))]
	\wedge  [\forall x,y  \, ((A(x) \wedge \neg A(y)) 
			\rightarrow \neg E(x,y))]
	 $
\bigskip
\bigskip
\bigskip
\bigskip
\bigskip


\ppart $ \exists R, B, G, \\ 
\begin{array}{rrrcrcrc}
[ & (\forall x  &  ( R(x) & \wedge & \neg B(x) &\wedge &\neg G(x)) & \vee \\
  &	&	(\neg R(x) &\wedge &  B(x) & \wedge & \neg G(x)) & \vee \\
  &	&	(\neg R(x) &\wedge & \neg B(x)& \wedge & G(x)) & )
\end{array} \\
\begin{array} {ccccc}
\wedge &(\forall x,y &((R(x) \wedge R(y)) \rightarrow \neg E(x,y)) & \wedge
&\\
	& & ((B(x) \wedge B(y)) \rightarrow \neg E(x,y)) & \wedge &\\
	& & ((G(x) \wedge G(y)) \rightarrow \neg E(x,y)) & ) & ]
\end{array} $
\eparts

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

\pr  
\points{16} 

Prove of disprove:
$f(n)= \Theta(f(n/2))$.

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

\pr 
\points{16} 

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

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

\pr
\points{16}
 
Give asymptotic upper and lower bounds for $T(n)$ (i.e. $T(n) = \Theta(f(n))$).
Assume that $T(n)$ is constant for $n \leq 2$.

\bparts
\ppart $T(n) = 6T(n/3) + n^2$
\bigskip
\bigskip
\bigskip
\ppart $T(n) = 3T(n/9) + \sqrt{n}$
\bigskip
\bigskip
\bigskip
\ppart $T(n) = 5T(n/3) + n$
\eparts

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

\pr  
\points{16} 

Let $c(n,k)$ be the number of permutations of $\{1, \cdots,n \}$ with exactly $k$
 cycles. State and prove a recurrence for $c(n,k)$ in terms of $c(n-1,k)$
 and $c(n-1,k-1)$.

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

\pr
\points{16} 

How many graphs are there on $5$ nodes that has no vertex of degree $4$? 

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


\end{problems}

\end{document}


