\documentstyle[amstex,12pt]{article}

\input{macros-course}

\def\brule#1{\enskip\vrule width#1 height -1.1pt depth 1.5pt\relax}

\newcommand{\pts}[1]{\relax[#1 pts]\enskip\ignorespaces}

\makeatletter
\renewcommand\theenumi{\@alph\c@enumi}
\renewcommand\theenumii{\@roman\c@enumii}

\renewcommand\labelenumi{\theenumi)}
\renewcommand\labelenumii{\theenumii)}

\def\ps@myheadings{%
    \let\@oddfoot\@empty\let\@evenfoot\@empty
    \def\@evenhead{\thepage\hfil\slshape\leftmark}%
    \def\@oddhead{\rlap{\slshape\rightmark}\hfil\thepage\hfil \llap{Name:\brule{2in}}}%
    \let\@mkboth\@gobbletwo
    \let\sectionmark\@gobble
    \let\subsectionmark\@gobble
    }

\makeatother

\begin{document}

%\examinitials{Quiz 1}{March 19, 1997}

\handout{quiz}{Quiz}{March 18, 1998}

\begin{closeitemize}
\item This quiz is closed book.  One two-sided crib sheet is allowed.

\item Put your name on the top of {\bf every} page---{\bf these pages
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
keep your entire answer to a problem on that problem's page.

\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 (6) problems totaling
100 points.   Each problem and problem part is labelled with the  number
of points it is worth. 

\item GOOD LUCK!
\end{closeitemize}

\medskip

\renewcommand{\arraystretch}{1}
\bigskip

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

\noindent \textbf{Circle the name of your TA}:\\
Alex Duran\quad
Stas Jarecki\quad
Al Lee\quad
Edmond Lee\quad
Mark Roh\quad
Tara Schenckel
\bigskip

\noindent Write the hour at when your Friday recitation begins \brule{3em}

\medskip

\centerline{DO NOT WRITE BELOW THIS LINE}

\medskip

\hrule


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


\newpage


\begin{problems}

\item\pts{25}

Let $L_n$ be the $n+1$-vertex simple ``line'' graph consisting of a
single simple path of length~$n$.  For example, $L_4$ is shown in the
figure below:
\begin{figure}[h]
\begin{center}
\begin{picture}(80,30)
\put(00,15){\circle*{3}} \put(00,15){\line(1,0){20}}
\put(20,15){\circle*{3}} \put(20,15){\line(1,0){20}}
\put(40,15){\circle*{3}} \put(40,15){\line(1,0){20}}
\put(60,15){\circle*{3}} \put(60,15){\line(1,0){20}}
\put(80,15){\circle*{3}}
\end{picture}
\end{center}

\centerline{The line graph $L_4$}
\end{figure}

Let's say a simple graph has ``two ends'' if it has exactly two
vertices of degree~one, and all its other vertices have degree~two.
In particular, for $n \ge 1$, the graph~$L_n$ has two ends.

\begin{enumerate}

\item\pts{3} 
Draw a diagram of the smallest simple graph with two ends which is not
isomorphic to any line graph.  \hint See part (d).

%%  What is the smallest $n \ge 1$ such that there is an
%%  $n+1$-vertex simple graph with two ends which is \emph{not} isomorphic
%%  to~$L_n$? \hint See part (d).\brule{2em}

\vfill


\item\pts{8}
Explain briefly, but clearly, what is wrong with the following
argument:

\paragraph{False theorem:}
Every simple graph with two ends is isomorphic to~$L_n$ for some~$n
\ge 1$.

\paragraph{False proof:}
We prove by induction on the number, $n \ge 1$, of edges in a simple
graph, that every two-ended graph with $n$ edges is isomorphic
to~$L_n$.

(Base case $n = 1$): A simple graph with one edge can only consist of
the two vertices connected by that edge and some number of vertices
not attached to  any edge, i.e., vertices of degree~zero.  Since a
two-ended graph cannot have vertices of degree~zero, the only
two-ended graph with one edge must consist solely of the two vertices
connected by the edge, which makes it isomorphic to~$L_1$.

(Induction case): Assume that $n \ge 1$ and every two-ended graph with
$n$ edges is isomorphic to~$L_n$.  Now let $G_n$ be any two-ended
graph with $n \ge 1$ edges.  By hypothesis, $G_n$ is isomorphic
to~$L_n$.  Suppose an edge is added to~$G_n$ to form a two-ended
graph~$G_{n+1}$.

Since $G_n$ is isomorphic to~$L_n$, it consists of a simple path of
length~$n$.  The only way to add an edge to the path and preserve
two-endedness is to have that edge go from one end---that is, one of
the degree-one vertices---to a new vertex, lengthening the path by
one.  That is, the resulting $n+1$-edge graph must be a simple path of
length~$n + 1$, so it is isomorphic to~$L_{n+1}$.  Q.E.D.

[Place your explanation on the next page.]

\newpage

\mbox{}

\newpage


\item\pts{7}
Here is another argument for the same False Theorem as in part~(b).
Explain exactly where it goes wrong.

\paragraph{False proof 2:}
Same induction hypothesis and base case as in part~(b).

(Induction case): For any $n\geq 1$, let $G_{n+1}$ be any two-ended graph
with $n+1$ edges.  Let $G_n$ be the graph which results from removing one
of the degree-one vertices~$v$ of~$G_{n+1}$ and the edge~$\{v,w\}$
attached to it.  So $G_n$ no longer has the vertex, $v$, of degree~one.
But the degree of $w$ is one less in~$G_n$ than it was in~$G_{n+1}$, so
$G_n$ still has two vertices of degree~one and one fewer vertex of
degree~two.  Therefore $G_n$ is also two-ended.  By induction $G_n$
consists of a simple path of length~$n$.  But $G_{n+1}$ is obtained by
attaching an edge from one end of the path to a vertex~$v$ not on the
path, thereby lengthening the path by one.  So $G_{n+1}$ is isomorphic to
a simple path of length~$n+1$; that is, it is isomorphic to~$L_{n+1}$.
Q.E.D.


\newpage


\item\pts{7}
Describe how to make a small revision to one of the false proofs above
so that it becomes a correct proof of the theorem ``Every
\emph{connected} simple graph with two ends is isomorphic to~$L_n$ for
some~$n \ge 1$.''

\end{enumerate}


\newpage


\item\pts{20}

Consider the following simple graphs:
\[
    K_8 \quad
    C_8 \quad
    K_{4,4} \quad
    W_7 \quad
    Q_3 \quad
    L_7
\]
(If you've forgotten how these graphs are defined, you can find the
definitions in the Appendix of this quiz.)

\begin{enumerate}

\item\pts{6} What is the minimum number of colors (chromatic number)
needed to vertex-color each of these graphs so that adjacent vertices have
different colors?
\[
    K_8     \brule{2em}\quad
    C_8     \brule{2em}\quad
    K_{4,4} \brule{2em}\quad
    W_7     \brule{2em}\quad
    Q_3     \brule{2em}\quad
    L_7     \brule{2em}
\]

\item\pts{8}
Let $v_1$, $v_2$, \ldots be variables ranging over vertices and
$E(v_1, v_2)$ mean that $v_1$ and~$v_2$ are connected by an
(undirected) edge.  For each of the following logical statements,
indicate exactly which of the six graphs above satisfies the
statement.

\begin{enumerate}

\item
$\exists v_1 v_2 : v_1 \ne v_2 \wedge \neg E(v_1, v_2)$

\vfill

\item
$\forall v_1 v_2 : E(v_1, v_2)$

\vfill

\item
$\forall v_1 v_2 : v_1 \ne v_2 \implies \left[ E(v_1, v_2) \vee
\exists v_3 : E(v_1, v_3) \wedge E(v_3, v_2) \right]$

\vfill

\item
$\exists v_1 v_2 v_3 v_4 :  v_2 \ne v_3 \wedge
                            v_2 \ne v_4 \wedge
                            v_3 \ne v_4 \wedge
                            E(v_1, v_2) \wedge 
                            E(v_1, v_3) \wedge 
                            E(v_1, v_4)$

\vfill


\end{enumerate}

\newpage

\item\pts{6}
Write a logical statement like those in part~(b) (involving only
variables ranging over vertices, the expressions $E(v_i, v_j)$, $v_i =
v_j$, $v_i \ne v_j$, logical connectives and quantifiers) which is
satisfied precisely by those simple graphs which have a vertex of
degree~two.


\end{enumerate}

\newpage


\item \pts{15}

$Q_n$ is the simple graph with $2^n$ vertices known as the
$n$-dimensional hypercube.  It can be defined recursively by the
conditions that $Q_0$ consists of a single vertex and $Q_{n+1}$ is
obtained by taking two copies of~$Q_n$ and adding edges between each
vertex in one copy and the corresponding vertex in the other copy.

\begin{enumerate}

\item\pts{2}
How many edges are there in~$Q_3$?\brule{2em}

\item\pts{8}
Describe a simple, closed-form formula for the number of edges
in~$Q_n$.\brule{5em}

\item\pts{5}
Prove below the correctness of your answer to part~(b).

\end{enumerate}


\newpage

\item\pts{15}

Start with 100 coins on a table, 98 showing ``heads'' and two showing
``tails.''  There are two ways to change the coins:
\begin{enumerate}
\item[(i)] flip over any ten coins, or

\item[(ii)] let $n$ be the number of coins on the table showing heads.  Place
$n+1$ additional coins on the table, with all the new coins initially
showing tails.
\end{enumerate}
For example, you might begin by flipping eight heads and two tails,
yielding 92 heads and 8 tails, then add 93 tails, yielding 92 heads and
101 tails.

\begin{enumerate}
\item \pts{3}
Model this situation as a state machine, carefully defining the set of
states, the start state and the possible state transitions.

\vskip3.5in

\item\pts{2} Explain how to reach a state with exactly one tail showing.


\newpage
\item\pts{4}
 Define the following derived variables of a state $q$:
\begin{enumerate}
\item $C(q) =$ the number of coins on the table
\item $H(q) =$ the number of heads
\item $T(q) =$ the number of tails
\item $C_2(q) = C(q) \bmod 2$ 
\item $H_2(q) = H(q) \bmod 2$ 
\item $T_2(q) = T(q) \bmod 2$ 
\end{enumerate}

Which of these variables is
\begin{enumerate}
\item increasing    \brule{15em} \bigskip
\item nondecreasing \brule{15em} \bigskip
\item decreasing    \brule{15em} \bigskip
%\item nonincreasing \brule{15em} \bigskip
%\item nonskipping   \brule{15em} \bigskip
\item constant      \brule{15em}
\end{enumerate}

\item\pts{6}
Prove that it is not possible to reach a state in which there is
exactly one head showing.


\end{enumerate}


\newpage


\item\pts{10}

Derive a closed form formula for
\[
    \sum_{i=0}^n \sum_{j=0}^i x^j
\]

\newpage

\item\pts{15}

\begin{enumerate}

\item\pts{7}
Prove that $\log(n!) = \Theta(n \log n)$.

\vfill

\item\pts{8}
Prove or disprove: For functions $f,g$ from positive integers to positive
integers,
\[f(n) = O(g(n)) \implies 2^{f(n)} = O(2^{g(n)}).\]

\vfill

\end{enumerate}

\end{problems}

\newpage

\subsection*{Appendix}

$K_n$ is the ``complete'' graph with $n$ vertices.  It has an edge between
every two vertices.

$K_{n,m}$ is the ``bipartite'' graph with $n + m$ vertices.  Each one of
the first $n$ vertices is adjacent to every one of the last $m$ vertices.

$C_n$ is the simple cycle of $n$ vertices.

$W_n$ is the ``wheel'' graph.  It consists of a simple cycle of $n$
vertices, along with an $n+1$st vertex adjacent to each vertex on the
cycle.

$Q_n$ is the $n$-dimensional hypercube (see Problem~3).  It has $2^n$
vertices.

$L_n$ is the simple path of length~$n$ (see Problem~1).  It has $n$ edges
and $n+1$ vertices.

\end{document}
