\documentclass[12pt]{article}
\usepackage{amsmath}

\input{macros-course}

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

%\newcommand{\solution}[1]{}
\newcommand{\solution}[1]{\smallskip \textbf{Solution:} #1}

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

\handout{q1sol}{Quiz 1 Solutions}{March 12, 1999 (revised 9:30pm)}
\iffalse

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

\textbf{Circle the name of your TA}:\\
\begin{center}
\begin{tabular}{ccc}
Matt Blum & Stas Jarecki\&Eric Lehman & Amit Khetan\\
Mike Leonida & Zulfi Ramzan & Jared Smith-Mickelson
\end{tabular}
\end{center}

\medskip

\begin{closeitemize}
\item This quiz is open book.  There are six (6) problems totaling 100
points.  Problem parts are labelled with their point values.

\item Put your name on the top of {\bf every} page --- \emph{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.

\iffalse
\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}.
\fi

\item GOOD LUCK!
\end{closeitemize}

\bigskip

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

\medskip
\fi

\hrule
\smallskip
\centerline{\textbf{DO NOT WRITE BELOW THIS LINE}}
\smallskip
\hrule

\medskip

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


\newpage
\fi

\begin{problems}

\problem\pts{20}
\bparts
\ppart\pts{10} Write a logical formula expressing the following statement:\\
Every element of the set $D$ is contained in exactly two of the sets
$A$, $B$, and $C$.

\solution{
\[
\forall x \in D\, :\, (x \in A \wedge x \in B \wedge x \not\in C) \vee
             (x \in A \wedge x \not\in B \wedge x \in C) \vee
             (x \not\in A \wedge x \in B \wedge x \in C)
\]}


\ppart\pts{10} Assume that the statement above holds and that also $A, B,$
and $C$ are subsets of $D$.  Circle all the sets equal to $A - B$:
\[
A \cap (D - B),\quad C - B,\quad (C \cap A) - B,\quad \overline{(D - A) \cup B}
\]

\solution{The first three expressions do equal $A-B$.  The fourth does
not: for example, suppose $A=B=C=D=\emptyset$; then $A-B = \emptyset$, but
$\overline{(D - A) \cup B}$ is the whole universe.}

\eparts

\newpage
\problem\pts{15}

Let $H_n ::= \sum_{i=1}^{n} 1/i$ be the $n$th Harmonic number.
Use induction to prove:
\[ n+1 \geq H_{2^n} \geq n/2. \]

(We want a simple induction proof --- no fair appealing to the integral
method used in lecture to show that $H_n \sim \ln n$.)

\solution{
\begin{proof}

Induction on $n$, using the statement to be proved as the induction hypothesis.

Base case:  If $n=1$ then $H_{2^n} = 1 + 1/2$.  So
\[n+1 =  2 \geq 1 + \frac{1}{2} \geq 1. \]

Induction case: Suppose the claim holds for $n\geq 1$.  We claim it holds
for $n+1$.  To prove this, note that by definition
\[\begin{array}{rclcl}
H_{2^{n+1}} & = & \sum_{i=1}^{2^{n+1}} 1/i
& = & H_{2^n} + \sum_{i = 2^n + 1}^{2^{n+1}} 1/i. 
\end{array}
\]

But in the sum
\[\sum_{i = 2^n + 1}^{2^{n+1}} \frac{1}{i} =
\frac{1}{2^n + 1} + \frac{1}{2^n + 2} + \dots + \frac{1}{2^{n+1}}\]
each term is greater than $1/2^{n+1}$.  We get a lower bound on this sum by
replacing each term with $1/2^{n+1}$.  Since there are a total of $2^n$
terms, the lower bound is $2^n \cdot 1/2^{n+1} = 1/2$.  We can get an
upper bound by observing that each term in the above sum is smaller
than $1/2^n$.  Replacing each term in the sum, we get an upper bound of
$1$.  Summarizing, we have that:
\[ 1 \geq  \frac{1}{2^n + 1} + \frac{1}{2^n + 2} + \ldots + \frac{1}{2^{n+1}}
\geq \frac{1}{2}. \]

Now, by our inductive hypothesis, 
\[ n+1 \geq H_{2^n} \geq n/2. \]  
Adding the two inequalities together
gives us:
\[ (n + 1)+1 \geq H_{2^n} +  \frac{1}{2^n + 1} + \frac{1}{2^n + 2} +
\ldots + \frac{1}{2^{n+1}} \geq \frac{n}{2} + \frac{1}{2} = \frac{n+1}{2}, \]
and since the middle term in this inequality is equal to $H_{2^{n+1}}$, the
claim for $n+1$ is proved.
\end{proof}
}
\vfill

\newpage

\problem\pts{15} We extend the ``divides'' relation to real numbers as
follows: for $a,b \in \reals$, we say $a \mid b$ iff $ak = b$ for some
integer $k$.  A number $c$ is a \emph{common divisor} of $a$ and $b$ iff $c
\mid a$ and $c \mid b$.
\bparts

\ppart\pts{2} Give an example of a real number which is not divisible by
1/3. \brule{0.5in}

\solution{Any rational with lowest-form denominator not equal to 1 or 3;
any irrational.}

\ppart\pts{3}  Give an example of two real numbers $a,b$ with \emph{no}
common divisor.
\[
a ::=\brule{0.7in},  b ::=\brule{0.7in}.
\]

\solution{$a=1, b= \sqrt{2}$.}

\ppart\pts{10} Prove that your choice of $a$ and $b$ is correct.

\solution{If any two numbers, $a, b \neq 0$, have some $c$ as a common
divisor, then $c = a/n$ and $c = b/m$ for some integers $m,n\neq 0$.  So
then $a/b = m/n$.  Hence, if the quotient of two nonzero numbers is not
rational, they cannot have a common divisor.  Since $\sqrt{2}/1$ is
irrational, 1 and $\sqrt{2}$ have no common divisor.}

\vfill
\eparts

\newpage
\problem\pts{20} We apply the following procedure to a digraph $G=(V,E)$:
pick two vertices $v_1 \neq v_2$ such that (1) there is an edge in $E$
from $v_1$ to $v_2$ and (2) there is also a path from $v_1$ to $v_2$ which
does \emph{not} include this edge, and then delete the edge $(v_1,v_2)$.
Keep repeating this deletion process until it is no longer possible to
delete any edge.

This procedure can be modelled as a state machine whose states are all the
subgraphs of $G$, that is, all the digraphs with vertices $V' \subseteq V$
and edges $E' \subseteq E$.  $G$ is the only start state, and the final
states are the subgraphs in which no deletions are possible.

\bparts
\ppart\pts{3}  Let $G$ be the digraph with $V=\set{1,2,3,4}$ and edges
\[
\set{(1,2),(2,1),(2,3),(3,2),(3,1),(2,4)}.
\]
List the possible final states that are reachable from the start state: 

\solution{2 states --- a cycle 1231 or a double loop 21232,
with 2 connected to 4 in each case:
\[
\set{(1,2),(2,3),(3,1),(2,4)},
\]
and
\[
\set{(1,2),(2,1),(2,3),(3,2),(2,4)}.
\]}


\ppart\pts{5} In addition to numerical derived variables, we introduce
some set-valued derived variables below.  For the set-valued derived
variables, values will be partially ordered under containment (that is,
under $\subseteq$).  So such a variable is \emph{decreasing} when its value
after a transition is strictly contained in its value before the
transition.  This also applies to relation-valued variables, since a
relation can be treated as the set of tuples of its related elements.

On the line next to each of the variables below, indicate the strongest
property which it satisfies from the following list:
\begin{center}
\begin{tabular}{ccccc}
invariant & increasing & decreasing & nonincreasing & nondecreasing
\end{tabular}
\end{center}
The derived variables are:
\begin{enumerate}

\item[i)] the set of vertices, \brule{1.5in}

\solution{invariant}

\item[ii)] the set of edges, \brule{1.5in}

\solution{decreasing}

\iffalse
\item minimum number transitions to reach a final state, \brule{1in}

\solution{nonincreasng? fluctuates?}
\fi

\item[iii)] the connectedness relation, $\succeq$, \brule{1.5in}\\
(remember for vertices $u,v$:\
$u \succeq v$ iff $u=v$ or there is a path from $u$ to $v$),

\solution{invariant}

\item[iv)] the set of final states reachable from the current state,
\brule{1.5in}

\solution{nonincreasing; part (a) shows that it is not invariant.}
\iffalse

\item[v)] the number of simple cycles. \brule{1.5in}
\fi

\item[v)] the minimum length of a path in the graph. \brule{1.5in}

\solution{invariant.  This was a trick question, and it tricked too many
people, indicating not that they were foolish, but that the question was
not a good one.

\medskip
The reason for invariance is that the minimum length of a path is one, as
long as the graph has at least one edge, since an edge is a length one
path.  Also, a graph with at least one edge will never have all its edges
deleted, so the minimum length is invariant in this case.  If the graph
has no edges, then the minimum length is either undefined or zero as a
matter of convention; either way it's invariant.  Of course this is a
silly variable to consider, and that may have encouraged people to look
for other meanings.

\medskip
A less silly derived variable of this kind would be \emph{Max} defined to
be the \emph{maximum} length of a path in the graph --- when there is a
maximum length.  Define \emph{Max} to be -1 when there is no bound on the
length of paths.  Now \emph{Max} is an invariant, and it is genuinely
interesting: \emph{Max} $= -1$ precisely when the graph has a cycle, and
when the graph is a DAG, we know its value is the minimum length of
schedule when edges are interpreted as scheduling precedence constraints.

\medskip
Some people chose \emph{nondecreasing}, perhaps because they
misinterpreted the problem as asking about the minimum length path between
\emph{any given pair of vertices} rather than the minimum length among
\emph{all} pairs.  Indeed, for any given pair which are connected by some
path, the length of the minimum length path between them will never
decrease as a result of deleting edges, and it can increase.}

\end{enumerate}

\ppart\pts{5} Prove that the procedure terminates and that the final
digraph has the same connectedness relation as $G$.

\solution{Since the edge set is decreasing so is the number of edges.
Since it must be a natural number, by the Well-ordering Principle it
cannot decrease forever, and the procedure terminates when it can no
longer be decreased.  The final graph has the same connectedness relation
as $G$ because the relation is an invariant.  (Many people included a
proof of invariance; we did not require this and allowed invariance to be
taken as known from part (b)).}

\ppart\pts{7} Does it also follow from the indicated properties of the
derived variables that the final graph has the minimum number of
edges among all graphs with the same connectedness relation as $G$?
Briefly explain.

\solution{No!  Having the minimum number of edges does not follow because
it isn't true, eg, from part (a), one final state has five edges and the
other has the same connectedness with four edges,

\medskip
Another example is the one vertex graph with a self-loop; anyone picky
enough to spot this degenerate case should get full credit.}

\vfill

\eparts

\newpage
\problem\pts{15}
There is a number $a$ such that $\sum_{i=1}^\infty i^p$ converges iff $p < a$.

\bparts

\ppart\pts{5} What is the value of $a$? \brule{0.7in}

\solution{$-1$}

\ppart\pts{10} Prove it.

\solution{For $p=-1$, the sum is the
harmonic series which we know does not converge.  Since the term $i^p$ is
increasing in $p$ for $i>1$, the sum will be larger, and hence also diverge
for $p>-1$.

By the integral method, the sum is $\Theta$ of the integral from
1 to $\infty$ of $x^p$.  For $p<-1$, the indefinite integral is $x^{p+1}/(p+1) =
\Theta(1/x^\epsilon)$ for $\epsilon = -1 - p > 0$, so the integral
evaluates to a constant.  Hence the sum is bounded above, and since it is
increasing, it has a finite limit, i.e., it converges.}

\vfill
\eparts


\problem\pts{15} For $i \in \naturals$, define the function
\[
f_i(n) ::= (n+i) \bmod 3.
\]
Prove that none of $f_0,f_1,f_2$ is $O()$ of the others.  That
is, $f_i = O(f_j)$ implies $i = j$ for $0\leq i,j \leq 2$.

\solution{Suppose $0 \leq i \neq j \leq 2$.  To show $f_j \neq O(f_i)$, we
must show that for any $c,n_0>0$, there is a $k > n_0$ such that $f_j(k) >
cf_i(k)$.  But just choose $k$ to be the one number among $n_0+1, n_0+2,
n_0+3$ which is $\equiv -i \mod 3$.  Then $f_i(k) = 0$ and $f_j(k) > 0$, so
$f_j(k) > 0 = c\cdot 0 = cf_i(k)$. \qed}

\vfill


\end{problems}

\end{document}


\end{problems}

\end{document}
