\documentstyle[12pt,macpsfig,amssymb]{article}
\input{macros-course}

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

%\newcommand{\pr}{\problem}

\newcommand{\ef}[2]{
\begin{tabbing}
XX\=XX\=XX\=XX\=XX\=XX\=  \kill
\protect #1\\
\>Effect: \+ \+ \\
   #2 \- \-
\end{tabbing}}

\newcommand{\iocode}[2]{\begin{center}\footnotesize
\begin{minipage}[t]{.45\linewidth}
\hbox to\linewidth{}
#1
\end{minipage}
\hspace{.05\linewidth}
\begin{minipage}[t]{.45\linewidth}
\hbox to\linewidth{}
#2
\end{minipage}
\end{center}}

\newcommand{\prcef}[3]{\begin{tabbing}       
XX\=  XX\=XX\=XX\=XX\=  \kill
\protect #1\\
\>Precondition: \+ \+ \\ 
  #2  \-  \- \\ 
\>Effect: \+  \+ \\
  #3 \- \- 
\end{tabbing}} 

\newcommand{\newgcd}[2]{{\ms{gcd}}(#1, #2)}

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

\begin{document}


\handout{q1sol}{Quiz 1 Solutions}{October 31 1997}

%\qsol{1}{October 31 1997}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
\problem{\bf 10 points}

Use induction to prove that $\forall n \geq 1$,

$$
{1 \over 1 \cdot 2} + {1 \over 2 \cdot 3} + \ldots +{1 \over n(n+1)}
= {n \over n+1}
$$

\bigskip


{\em Proof by induction.}\\
Let $P(n)$ be ``${{1}\over {1\cdot 2}} + {{1}\over {2\cdot3}} + ... +{{1}\over
{n(n+1)}} =  {{n}\over {n+1}}.$'' \\

{\bf Base case:} $n = 1$. $P(1)$ is true since ${{1}\over {1\cdot 2}} = {1
\over {(1+1)}}$.

{\bf Inductive step:}
Assume $P(n)$ is true, in order to show that $P(n+1)$ is true.

\begin{eqnarray*}
{{1}\over {1\cdot 2}} + {{1}\over {2\cdot 3}} + ... +{{1}\over
{(n+1)\cdot((n+1)+1)}} &=& {{1}\over {1\cdot 2}} + {{1}\over {2\cdot 3}} +
 ...{{1}\over {n(n+1)}} + {{1}\over{(n+1)((n+1)+1)}} \\
&=&  {{n}\over {n+1}} + {{1}\over {(n+1)\cdot ((n+1)+1)}}
\mbox{ true by {\bf I.H.}}\\
&=&{{n(n+2)} \over {(n+1)(n+2)}} + { 1 \over {(n+1)(n+2)}}\\
&=&{{n^2 + 2n +1} \over {(n+1)(n+2)}}\\
&=& {{(n+1)}^2 \over {(n+1)(n+2)}} \\
&=& {{n+1}\over {n+2}} \\
&=& {{n+1}\over {(n+1)+1}} 
\end{eqnarray*}


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2

\problem{\bf 10 points}

\bparts

\ppart{\bf[6 points]}
Cast each of the following statements in propositional symbol form.  

Definitions:
\begin{enumerate}
\item $C =$ set of classes.
\item $M =$ set of majors.
\item for $x \in C$, $H(x)$ means $x$ is hard.
\item for $x \in C, y \in M$,
$R(x,y)$ means $x$ is required for $y$.
\end{enumerate}

Statements:
\begin{enumerate}
\item{\bf [2 points]} At least one class is hard.

\bigskip

$\exists x \in C : H(x)$

\bigskip

\item{\bf [2 points]} Every major requires at least one hard class.

\bigskip

$\forall y \in M \exists x \in C : H(x) \wedge R(x,y)$

\bigskip

\item{\bf [2 points]} No class is required for two or more majors.

\bigskip

$\neg \exists x \in C, \exists y_1 \in M \exists y_2 \in M:
(y_1 \neq y_2) \wedge R(x,y_1) \wedge R(x,y_2)$

\end{enumerate}

\bigskip

\ppart{\bf [4 points]}
Write the negation of $\forall y \exists x H(x) \wedge R(x,y)$
in terms of $\neg H(x)$ and $\neg R(x,y)$ (and without using any other 
negation symbols -- i.e., $\neg \forall$ is not allowed.)

\bigskip

$\exists y \forall x \neg H(x) \vee \neg R(x,y)$

\eparts


\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3

\problem{\bf [10 points]}
 
What denominations of postage can be made with an unlimited supply of 
stamps of $5,6$, and $7$ cents? Be sure to prove your answer.

The set of possible postage denominations is
$S = \{ 5,6,7 \} \cup \{n \in \nat; n \geq 10 \}$

The cases for $5,6,7$ are immediate.  Also, it is clear that $1,2,3,4,8,9$
cannot be made.

We use induction for the rest.

Let $P(n) = ``$ $n$ can be made with stamps of value 5,6,and 7 cents''.

{\bf Claim:} $\forall n\geq 10: P(n)$

{\bf Base case:}
$n = 10$ can be made with two 5-cent stamps

{\bf Inductive hypothesis:}
Assume $P(n)$ is true in order to show that $P(n+1)$ is true.

We want to show that a postage of $n+1$ can be made by the available stamps.
By the inductive hypothesis $n$ can be made by the available stamps.
If $n$ can be made with a 5, we take out the 5 cent stamp and replace it
with a 6 cent stamp.
If $n$ can be made with a 6, we take out the 6 cent stamp and replace it
with a 7 cent stamp.
If $n$ contains neither a 5 or a 6, then $n$
must contain two 7 cent stamps (because it's bigger than 10).  So we can
replace the two 7 cent stamps with three 5 cent stamps.
The induction is complete.

\bigskip

Here's an alternative proof that uses strong induction.  We provide the
inductive step.

Assume $P(10)\wedge P(11) \wedge \ldots \wedge P(n)$, in order to show 
$P(n+1)$.

Note that $P(n-4) \Rightarrow P(n+1)$ since we can add a 5-cent stamp to
$n-4$.  So the inductive hypothesis is proved for $n-4 \geq 10 
\Rightarrow n \geq 14$.  Hence we must check the inductive hypothesis
for $10 \leq n < 14$.

$10$ is just the base case.\\
$11 = 5+6$\\
$12 = 6+6$\\
$13 = 6+7$\\
$14 = 7+7$\\

The induction is complete.

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
\problem{\bf [20 points]}

Recall that a coloring of a graph is an assignment of a color to each
vertex.  A graph is defined to be $k$-colorable if it has a coloring
using at most $k$ colors such that no two adjacent vertices have the same
color. ({\em Note: we consider only graphs without loops in this problem})

\bparts
\ppart{\bf [5 points]}

Prove that if a graph has maximum node degree $k$ then it is
($k+1$)-colorable.

Proof by induction on the number of vertices:

Inductive hypothesis:\\
$P(n) = $``Every graph of n vertices with maximum node degree $k$ is $(k+1)$
colorable.''

{\bf Base case:} $(n=1)$\\
The only graph with a single vertex can always be colored with one color, so
for any $k\geq$0, it is $(k+1)$-colorable.

{\bf Inductive step:}

Assume $P(n)$ in order to prove $P(n+1)$.\\
Given any graph $G_{n+1}$ with n+1 vertices and maximum degree $k$, remove
one vertex, $v$, to produce a graph $G_n$ with $n$ vertices.  Since we
have not added any edges, $G_n$ must have maximum vertex degree at most
$k$. By the inductive hypothesis, we can color $G_n$ with $k+1$ colors. 
We can then add $v$ back into the graph.  Since $v$ has at most $k$ neighbors,
we can color it with one of the original $k+1$ colors, giving a
$(k+1)$-coloring for $G_{n+1}$.

\newpage

\ppart{\bf [15 points]}

A graph is defined to be \underline{regular} if every vertex in the 
graph has the same degree.  Show that if a
connected graph has maximum node degree $k$ and is not regular then
it is $k$-colorable. 
({\em You may use the result from part (a) without proof}).

\bigskip

Proof by strong induction on the number of vertices:

Inductive hypothesis:\\
$P(n) = $``Every connected graph of $n$ vertices and maximum node degree $k$ 
that is not regular is $k$-colorable.''

{\bf Base case:} (n=1)\\
The graph with one vertex is always regular, so $P(1)$ holds vacuously.

{\bf Inductive step:}

Assume $P(1)\wedge P(2) \wedge\cdots\wedge P(n)$, in order to prove $P(n+1)$.\\
Given any graph $G_{n+1}$ with $n+1$ vertices and maximum vertex degree $k$,
$P(n+1)$ holds trivially if the graph is not connected or is regular.
Therefore assume $G_{n+1}$ is connected and not regular.
Then, since $G_{n+1}$ is not regular, it must have some vertex of degree
less than $k$.  Remove that vertex, $v$, to produce a graph $G_n$.  Then we
can consider each connected component $C_i$ of $G_n$:

Case 1: $C_i$ is regular.  Since $G_{n+1}$ was connected, $v$ must have
been connected to at least one node in $C_i$.  Therefore, at least one
node of $C_i$ must have a lower degree than it did before $v$
was removed.  Therefore $C_i$ has at least one node of degree less than
$k$.  Since $C_i$ is regular, all nodes must therefore have degree less
than $k$, meaning $C_i$ has a maximum node degree less than $k$.  Therefore
$C_i$ is $k$-colorable by part (a).

Case 2: $C_i$ is not regular.  $C_i$ must have degree at most $k$
and it is connected by definition, so
by the inductive hypothesis, it is $k$-colorable.

Since all components of $G_n$ are $k$-colorable, $G_n$ is $k$-colorable.  We
can therefore assume $G_n$ is assigned some $k$-coloring.  Now we can
reattach $v$.  Since $v$ has less than $k$ neighbors, there must be some
$j \leq k$ such that $v$ is not adjacent to any node of color $j.$  Thus,
we can color $v$ with color $j$, producing a $k$-coloring of $G_{n+1}$.
Therefore, if $G_{n+1}$ has maximum vertex degree $k$ and is not regular
then it is $k$-colorable.

\eparts

\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
%state machine problem
\problem{\bf [10 points]}

Luke finished his lightsaber practice, and sits down for a game of 4
dimensional chess.  The space of moves is a four dimensional 
$11\times 11\times 11\times 11$ grid with cells\\
$\{ (x,y,z,w) | -5 \leq x,y,z,w \leq 5 ; x,y,z,w \in \integers \}$.
If his king moves 1 unit in each of two different
directions at each step, and he starts at $(1,0,0,0)$, can his
king reach $(5,4,-1,2)$?
Express the possible moves as a state machine and find an invariant to 
prove your answer.

\bigskip

The state is the possible positions $(x,y,z,w)$ on the chess-board
$-5 \leq x,y,z,w \leq 5 ; x,y,z,w \in \integers.$
The transitions are the movements of the king, i.e., exactly two coordinates
change by $\pm 1$ in a way such that the king remains in the chess board.
The initial state is $(1,0,0,0)$.

The invariant is $P(x,y,z,w): x+y+z+w \text{ is odd }$

The invariant is certainly true for the initial state, $(1,0,0,0)$.

Assume that it is true at state $(x,y,z,w)$.  At the next state transition
to state $(x',y',z',w')$
two of the state variables are changed by $\pm 1$, therefore the sum of 
the invariant is changed by either $-2,0,$ or 2.  Therefore 
$(x'+y'+z'+w')$ remains odd.  The invariant is proved.

The state $(5,4,-1,2)$ does not satisfy the invariant, therefore it is
not a reachable state.

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
\problem{\bf[9 points]}

For each of the following pairs of functions $f(n)$ and $g(n)$, fill
in the blank with $o$, $O$, $\omega$, $\Omega$, and $\Theta$ depending 
on whether $f(n)=o(g(n))$, $f(n)=O(g(n))$, $f(n)=\omega(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
the strongest one. You do not need to supply any proofs.  

\def\blank{\rule[-2pt]{.5in}{.5pt}}
\[
\renewcommand{\arraystretch}{4}         
\begin{array}{rcl}
 n^2                 & = & o (n^3)\\
 2^n                 & = & o (3^n)\\
 \log_2 n            & = & \Theta (\log_3 n)\\
n^3		     & = & o (2^n)\\
{n \over \log n}     & = & o (n)\\
\log_2 n             & = & o (\sqrt n)\\
8^{\log_2  n}        & = & \Theta  (n^{\log_2 8})\\
(n!)^2               & = & \omega (n^n) \\
2^{\log_3 n}         & = & o  (n^2) \\
\end{array}
\]

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
\problem{\bf [10 points]}

Your answer in the following problems should not contain $\sum$ or
$\prod$ and should be in closed form.

\bparts

\ppart{\bf [4 points]}

Find tight asymptotic ($\Theta$) bounds for

\begin{displaymath}
\sum_{k=1}^{n} {1 \over \sqrt k}
\end{displaymath}

\bigskip

We use the integration method for bounding summations.\\
\begin{eqnarray*}
{\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} & \leq {\displaystyle
\sum_{k=1}^n \frac{1}{\sqrt{k}}} &
\leq 1 + {\displaystyle \int_1^n \frac{1}{\sqrt{x}} dx} \\
{\displaystyle 2x^{\frac{1}{2}}|_1^n} &
\leq  {\displaystyle \sum_{k=1}^n \frac{1}{\sqrt{k}}} & 
\leq 1 + {\displaystyle 2x^{\frac{1}{2}}|_1^n} \\
2\sqrt{n} - 2 &
\leq {\displaystyle \sum_{k=1}^n \frac{1}{\sqrt{k}}} & \leq 2\sqrt{n} - 1 \\
\end{eqnarray*}

That is
\[ {\displaystyle \sum_{k=1}^n \frac{1}{\sqrt{k}}} = \Theta(\sqrt{n}).\]

\ppart{\bf [6 points]}

Evaluate the following product

\begin{large}
\begin{displaymath}
\prod_{i=1}^{\infty} e^{ (2^{-i})}
\end{displaymath}
\end{large}

\eparts

\bigskip

\begin{eqnarray*}
\prod_{i=1}^{\infty} e^{ (2^{-i})} & = & e^{\sum_{i=1}^{\infty} 2^{-i}}\\
& = & e^1\\ & = & e\\
\end{eqnarray*}

\newpage


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
\problem{\bf [11 points]}

Find tight asymptotic bounds for the following recurrences.  For each
recurrence $T(0) = 1$ and $n\in\nat$.

\bparts

\ppart{\bf [3 points]}

$T(n) = 2T\left(\floor{{n \over 4}}\right)+T\left(\floor{{n \over
3}}\right)+n$

\bigskip

We use Akra-Bazzi.

$h_1(n) = \floor{{n \over 4}} - {n \over 4}$, $h_2(n) = \floor{{n
\over 3}} - {n \over 3}$.  $g(n) = n$.  $a_1 = 2, a_2 = 1$.  $b_1 = {1
\over 4}, b_2 = {1 \over 3}$.

Setting $p=1$ we get $2{1 \over 4} +{1\over 3} = {5 \over 6} < 1$. We
conclude that $p < 1$, therefore the recurrence is of the order of the
inhomogeneous part $g(n) = n$.  Therefore $T(n) = \Theta(n)$.

\ppart{\bf [3 points]}

$T(n) = 4T\left(\floor{{n \over 2}+ \sqrt{n}}\right) + n^2$

\bigskip

We use Akra-Bazzi.

$h(n) = \floor{{n \over 2}+ \sqrt{n}}-{n \over 2}$.  $a_1 = 4, b_1 =
{1 \over 2}, g(n) = n^2$

$4 \left( {1 \over 2} \right) ^2 = 1 \Rightarrow p = 2$

$$T(n) = \Theta(n^{2}(1+ \int_1^n \frac{u^2}{u^{2 + 1}} du)) =
\Theta(n^{2}(1+ \int_1^n u^{-1} du)) = \Theta(n^2 \log n).$$


\newpage

\ppart{\bf [5 points]}

A society of devil-worshipers meets every week in a catacomb to
initiate new members.  Members who have been in the society for two or
more weeks initiate four new members each and members who have been in
the society for only one week initiate one new member each.  On week 0
there is one devil-worshiper.  There are two devil-worshipers on week
1.

Write a recurrence relation for the number of members $D(n)$ in the
society on the $n$th week.

{\bf You do NOT need to solve the recurrence.  Be sure to include the
base cases.}

\bigskip

The number of devil-worshipers on week $n$ is the number of
devil-worshipers that were around 2 weeks before plus their new
recruits, so $5D(n-2)$, and the number of devil worshipers that were
around only last week, $D(n-2) - D(n-1)$, plus their new recruits.  So
the total number of devil-worshipers on the $n$th week is

$D(n) = 5D(n-2) + 2(D(n-1)-D(n-2)) = 3D(n-2) + 2D(n-1)$

The initial conditions are

$D(0) = 1$

$D(1) = 2$

\eparts

\newpage

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

%In this problem you will show that $|(0,1)| = |(0,1)^\naturals|$.

%\bparts

%\ppart
%Let $(0,1)^\naturals$ denote the set of all functions from the
%natural numbers into the subset of the real line $(0,1)$.
%Find a (very easy) injection
%$\phi : (0,1) \rightarrow (0,1)^\naturals$.

%\ppart
%Let $f \in (0,1)^\naturals$. Note that $f$ assigns to every natural number
%$i$, a real number $a_i \in (0,1)$.  Show that you can represent a given
%function $f$ with a sequence of natural numbers. 
%{\em Hint:  Use dove-tailing}

%\ppart
%Use the previous part to establish an injection
%$\psi : (0,1)^\naturals \rightarrow (0,1)$.

%\ppart
%From parts (a) and (c) conclude that $|(0,1)| = |(0,1)^\naturals|$.

%\eparts

%\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
\problem{\bf [10 points]}

Suppose that you have $n$ balls where $n-1$ of them have the same
weight and one of them is heavier.  You also have a scale that can
compare any two groups of balls and tell you which group is heavier
(or if they are equal).

\bparts

\ppart{\bf [4 points]}

Describe an algorithm to find the heavier ball when $n=9$ using two
weighings.

\bigskip

Weigh balls 1-3 against balls 4-6. \\ 
If they are equal, weigh 7 against 8.  
If they are unequal, choose the heavier.  If they are equal choose 9.\\ 

If 1-3 is heavier, weigh 1 against 2.  If they are
unequal, choose the heavier.  If they are equal choose 3.\\ If 4-6 is
heavier, weigh 4 against 5.  If they are unequal, choose the heavier.
If they are equal choose 6.\\

\ppart{\bf [6 points]}

Prove that there is no algorithm that uses two weighings for $n=10$.

\bigskip

There are 10 possibilities for the heavy ball.
With 2 weighings, there are $3^2 = 9$ possible outcomes of the algorithm.  
Since $10 > 9$, the pigeonhole princeple means that 
some outcomes of the weighings cannot distinguish between
two of the possibilities.

\eparts

\end{problems}

\end{document}







