\documentstyle[12pt,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}


\examinitials{Quiz 2}{April 23, 1997}

\begin{closeitemize}
\item This quiz is closed book.  One 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 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.  I've tried to order them in increasing difficulty, but your
mileage may vary.

\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 7 problems, which
vary significantly in their point value.
You will get 5 extra points for circling
your tutorial TA and time and clearly writing your name on {\em every}
page.

\item GOOD LUCK!
\end{closeitemize}

\bigskip

\renewcommand{\arraystretch}{.3}
\begin{center}
\begin{tabular}{|c|c|c|}
\hline
& &\hspace*{1in}\\
Problem&Points&Graded by\\
& &\\
\hline
\hline
& &\\
name & 5 & \\& &\\ \hline & &\\
1 &  40 & Daniele \\& &\\\hline & & \\
2 &  15 & Alex \\& &\\\hline&  &\\
3 &  5 & Daniele, Dimitri \\& &\\\hline&  &\\
4 &  15 & Dimitri \\& &\\\hline&  &\\
5 &  20 & David\\& &\\\hline& & \\
6 &  10 & Terri\\& &\\\hline&  &\\
7 &  10 &  Prof. Karger\\& & \\
\hline
\hline
& &\\
Total & 120 & \\
& &\\
\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} Terri
 \hspace{.7in} David
 \hspace{.7in} Dimitri
\bigskip
\bigskip

\noindent Please circle your tutorial  time: 
\hspace{.5in} 1
\hspace{.5in} 2
\hspace{.5in} 3
\hspace{.5in} 7
\newpage

\begin{problems}

  \newpage \problem \points{40} Circle T or F for all questions,
even if you have to guess.

\begin{tabbing}
F \ \ \ \= The relation on the natural numbers given by
               $\{ (x,y) \mid x \geq y-2\}$ is a poset.\\
% \> The relation is not antisymmetric.  (1,2) and (2,1) are both in the relation.\\
\\
F    \> The complement of a poset is always a poset.\\
% \> Since a poset must be reflexive, and the complement is missing all of the
% reflexive pairs, the complement of a poset is not reflexive, and is therefore
% not a poset.
\\
T   \> Not all vertices in a 20 vertex tree are leaves.\\
       
\\
F    \> There is a graph with an odd number of odd degree vertices.\\
\\
F    \> Some 20-vertex tree has an Euler tour.\\
\\
T    \> A {\bf complete} graph on $n > 3$ vertices has an Euler tour iff
               $n$ is odd.\\
\\
T    \> If every vertex in a directed graph has outdegree at
               least 1, then it has a cycle.\\
\\
F    \> If a graph has more edges than vertices, then it is connected.\\
\\
T    \> An $n$-vertex graph $G$ has a spanning forest with $n-1$ edges
               iff $G$ is connected.\\
\\
T    \> If 126 students take this quiz, then two will have scores
               within 1 point of each other.\\
\\
F    \> There is a surjection $f:\naturals \rightarrow \reals$.\\
% \ppart Any binary relation on the natural numbers is countable.
\\
T    \> If a set $A$ contains an uncountable subset $B$, then $A$ is
 uncountable.\\
\\
T    \> If an uncountable set $A$ contains a countable subset $B$,
               then $A-B$ is uncountable.\\
\\
F    \> If an uncountable set $A$ contains an uncountable subset $B$,
               then $A-B$ is countable.\\
% \ppart The set of functions from $\naturals$ to $\{0,1\}$ is
% uncountable.
\\
F    \> The set of functions from $\{0,1\}$ to $\naturals$ is uncountable.\\
\\
T    \> The sum rule is a special case of inclusion-exclusion.\\
\\
T    \> The ways that four distinguishable, ordinary six-sided
dice can land\\
    \> without any number repeated correspond
to permutations from some set.\\
\\
F    \> The expansion of $(x - 1)^{120}$ has three identical nonzero
coefficients.\\
\\
T    \> If $p > 5$ is prime, then $p \mid {p \choose {p-4}}$.\\
\\
T    \> The number of topological sorts of a poset is at least the
product of the number\\
    \> of topological sorts of the upper bounds and the lower bounds
of an arbitrary element.\\
\\
\end{tabbing}


\newpage \problem  \points{15} Short analyses.  No need to show your work.  {\bf
  Be careful} to look at the summation indices.

\begin{problemparts}

\ppart 
What is the product of the first $n$ odd powers of two:
$\Pi_{k=1}^n2^{2k-1}$?

\[
\Pi_{k=1}^n2^{2k-1} = 2^{\sum_{k=1}^n{2k-1}}
= 2^{2\sum_{k=1}^n k-\sum_{k=1}^n 1}
= 2^{n(n+1) - n}
= 2^{n^2}
\]


\ppart What is $\sum_{k = 0}^\infty (1/3)^k$?

\[
\sum_{k = 0}^\infty (1/3)^k =
\lim_{k \rightarrow \infty} \frac{1 - (\frac{1}{3})^{k+1}}{1-\frac{1}{3}} =
\frac{1}{\frac{2}{3}} = 
\frac{3}{2}
\]

\ppart What is $\sum_{k=a}^b k$?

\[
\sum_{k=a}^b k = 
\sum_{k=1}^b k - \sum_{k=1}^{a-1} k = 
\frac{b(b+1)}{2} - \frac{a(a-1)}{2}
\]



\ppart Give asymptotic $(\Theta)$ bounds for $\sum_{k=n/2}^n 1/k$.

\[
\\sum_{k=n/2}^n \frac{1}{k}  =
\Theta(\int_{n/2}^n \frac{1}{k} dk)
\]

\[
\int_{n/2}^n \frac{1}{k} dk = 
\log (k) \mid_{n/2}^n  = 
\log (\frac{n}{n/2}) =
\log (2)
\]

Since $\log(2)$ is a constant, 
\[
\sum_{k=n/2}^n 1/k  = \Theta(1)
\]

\ppart Give asymptotic $(\Theta)$ bounds for $\sum_{k=n/2}^n k^5$.

\[
\sum_{k=n/2}^n k^5=
\Theta (\int_{n/2}^n k^5 dk) =
\Theta (\frac{k^6}{6} \mid_{n/2}^n) = 
\Theta (\frac{n^6}{6} - \frac{n^6}{2^6 \cdot 6}) =
\Theta(n^6)
\]

\ppart How many subsets of $\{1,\ldots,10\}$ are there?

The power set has size $2^{10}$


\ppart You open a savings account with an initial deposit of $s$ dollars.

At the end of every year, the bank
pays into the account interest of $p$ dollars on every dollar in the
account at that time.  You then immediately (after the interest is paid)
deposit $d$ dollars.
Give (but do not solve) a recurrence for the amount of money $M(n)$ in
your account right after you make your deposit at the end of the $n$th
year.

$M(n) = (1+p) M(n-1) +d$ with the initial condition $M(1) = s$ (or $M(0) = s$).

\end{problemparts}


\def\blank{\rule[-2pt]{.5in}{.5pt}}


\newpage \problem \points{5} Fill in the blank with the most accurate choice from
$o,\Theta, \mbox{and } \omega$.  Remember that $o$ means $O$ but not
$\Theta$, while $\omega$ means $\Omega$ but not $\Theta$.

\begin{problemparts}
\ppart $(\log n)^{10}=o(n)$.

Recall that one way of determining if $f(x) = o(g(x))$, is to find the limit,
as $x \rightarrow \infty$, of the ratio of the functions.

If $\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = \infty$, then $f(x) 
= \omega(g(x))$.

If $\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} = 0$, 
then $f(x)=o(g(x))$.

If $\lim_{x \rightarrow \infty} \frac{f(x)}{g(x)} =$ constant, 
then $f(x)=\Theta(g(x))$.

Note that these are not proofs in themselves, but they tell us which one
will grow faster.

Show that $(\log n)^{k}=o(n)$:


\[
\lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} =
\lim_{n \rightarrow \infty} \frac{(\log n)^{k}}{n}
\]
Applying L'Hopital's rule, multiple times we get that

\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{(\log n)^{k}}{n} & = &
\lim_{n \rightarrow \infty} \frac{k(\log n)^{k-1} \frac{1}{n}}{1} \\
& = & \lim_{n \rightarrow \infty} \frac{k(\log n)^{k-1}}{n} \\
& = & \lim_{n \rightarrow \infty} \frac{k(k-1)(\log n)^{k-2}}{n} \\
& \cdots & \\
& = & \lim_{n \rightarrow \infty} \frac{k!}{n} \\
& = & 0 \\
\end{eqnarray*}

So, $(\log n)^{k}=o(n)$, and more specifically, $(\log n)^{10}=o(n)$.


\ppart $\log (n!) = \Theta (n \log n)$.


\[
\lim_{n \rightarrow \infty} \frac{\log (n!)}{n \log n} =
\lim_{n \rightarrow \infty} \frac{\sum_{i=1}^{n} \log i}{n \log n}
\]

Applying L'Hopital's rule, 

\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{\sum_{i=1}^{n} \log i}{n \log n}
&=& \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^{n} \frac{1}{i}}
{n \cdot \frac{1}{n} + \log n} \\
&=& \lim_{n \rightarrow \infty} \frac{\sum_{i=1}^{n} \frac{1}{i}}
{1 + \log n} \\
&  \approx &\lim_{n \rightarrow \infty} \frac{\log n}
{1 + \log n} \\
&=& 1 \\
\end{eqnarray*}

So, $\log (n!) = \Theta (n \log n)$.

\ppart $\log n = \Theta (H_n)$.

Recall from class that $H_n = \sum_{i=1}^{n} \frac{1}{i}$ can be approximated
by $\log n$, so $\log n = \Theta (H_n)$.

\ppart ${n \choose 3} = o(n^4)$

\[
{n \choose 3} = \frac{n!}{3! (n-3)!} = \frac{n(n-1)(n-2)}{6}  = \Theta(n^3)
\]

Since $n^3 = o(n^4)$, ${n \choose 3} = o(n^4)$.



\ppart $2^n = \omega (n^2)$ 

This is a common problem in computer science:  we want our algorithms to
run in polynomial time $n^k$, not exponential time $k^n$.

By applying L'Hopital's rule twice, we get:

\begin{eqnarray*}
\lim_{n \rightarrow \infty} \frac{2^n}{n^2} &=&
\lim_{n \rightarrow \infty} \frac{2^n \ln 2}{2n} \\
&=&\lim_{n \rightarrow \infty} \frac{2^n (\ln 2)^2}{2}  \\
&=& \infty\\
\end{eqnarray*}

So $2^n = \omega (n^2)$.

\end{problemparts}

\newpage \problem  \points{15} Solve the following recurrences.  You must show your
derivation, but do not have to prove your answer correct.
\begin{problemparts}

\ppart $T(n)=T(n-1)+6T(n-2)$, $T(0)=2$, $T(1)=1$.

Let $T(n) = c \alpha^n$.  Substituting for $T$ we get

\[ c \alpha^n = c \alpha^{n-1} + 6 c \alpha^{n -2}  \]
\[\alpha^2 - \alpha - 6  = 0 \]
\[ (\alpha -3) (\alpha + 2) = 0 \]
\[ \alpha  = 3, - 2 \]

So, $T(n) = a3^n + b(-2)^n$.

Using our initial conditions:
\[ T(0) = 2 = a+b \]
\[ T(1) = 1 = 3a-2b \]
From these we get, $a=1$ and $b=1$, so 

So, $T(n) = 3^n + (-2)^n$.


\ppart $T(n)=4(T(n-1)-T(n-2))$, $T(0)=1$, $T(1)=0$.

Let $T(n) = c \alpha^n$.  Substituting for $T$ we get
\[ c \alpha^n -4 c \alpha^{n-1} + 4 c \alpha^{n -2} = 0 \]
\[ \alpha^2 - 4 \alpha +4   = 0  \]
\[ (\alpha -2)^2 = 0  \]
\[ \alpha  = 2 \]

Since we have a double root, we choose $T(n) = a2^n + b n 2^n$.
For $T(0)$:
\[  T(0) = 1 = a  \]
\[  T(1) = 0 = 2a + 2b   \]
From these we get, $a=1$ and $b=-1$, so $T(n) = 2^n - n 2^n$.

\ppart $T(n)=9T(n/3)+n^3$, $T(1)=1$, where $n$ is a power of 3 (an
asymptotic bound is sufficient here). 

\[ T(n) = 9T(\frac{n}{3}) + n^3 \]
Let $n = 3^k$
\[ T(3^k) = 9T(3^{k-1}) + 3^{3k} \]

Let $ S (k) = T(3^k)$, $S(0)=1$.

\begin{eqnarray*}
 S(k) &= & 9 S(k-1) + 3^{3k} \\
 &= &  3^{3k} + 9(3^{3(k-1)} + 9(3^{3(k-2)} +\cdots + 9S(0) )) \\
 &= &  3^{3k} + 3^{3k-1} + 3^{3k-2} + \cdots + 3^{2k+1} +9^k S(0)  \\
 &= &  \sum_{i=2k+1}^{3k} 3^{i} + 9^k\\
 & & =   \sum_{i=1}^{3k} 3^{i} - \sum_{i=1}^{2k} 3^{i} + 9^k \\
 &= &  \frac{1- 3^{3k+1}}{1-3} - \frac{1- 3^{2k}}{1-3} + 9^k  \\
 & = & \frac{3^{3k+1} - 3^{2k}}{2} +9^k\\
&= & \frac{3 \cdot 27^k - 9^k}{2} + 9^k\\
\end{eqnarray*}

Now, substitute back for $k = \log_3 n$, and $T(3^k) = S(k)$.

\begin{eqnarray*}
T(3^k) = S(k) &= & \frac{3 \cdot 27^{(\log_3 n)} + 9^{(\log_3 n)}}{2} \\
T(n) &= & \frac{3 n^3 + n^2}{2} \\
& = & \Theta(n^3) \\
\end{eqnarray*}

\end{problemparts}

\underline{comments:}

\begin{itemize}

\item Some people tried to solve the linear difference equation as a 
recurrence and vice-versa.
\item Some people found the correct substitution of variables for part (b)
but the kept trying to solve the problem by expanding the recurrence instead
of solving the difference equation.

\end{itemize}

\newpage \problem \points{20} Consider the relation $R$ on $\{2,\ldots,100\}$ defined by
$aRb$ if $a \mid b$.

\begin{problemparts}
\problempart Prove that $R$ is a poset

Let $S = \{ 2, \ldots, 100\}$.
Posets are reflexive, antisymmetric, and transitive.
Recall that 
\begin{itemize}
\item reflexive means $\forall a \in S, (a,a) \in R$, 

\item antisymmetric means that $(a,b) \in R \wedge (b,a) \in R \rightarrow a = b$, 
and

\item transitive means that $(a,b) \in R \wedge (b,c) \in R \rightarrow (a,c) \in R$.)
\end{itemize}

$R$ is reflexive: $ \forall a \in \{2, \ldots, 100\}$, $a \mid a$.

$R$ is antisymmetric: $(a \mid b) \wedge (b \mid a)$  can only be true if
$a=b$ since if $a \mid b$ then $b = a k_1 $, $k \in \naturals, k\geq 1$, but
if $b \mid a$, then, $a = bk_2$, so $b = b \cdot k_1 \cdot k_2$, but since
$k_1$ and $k_2$ are integers, $k_1 = k_2 = 1$, so $a=b$.

Transitivity: If $(a \mid b) \wedge (b \mid c)$, then $b = ak_1$, and
$c = bk_2$, so $c = a k_1 k_2 = a k_3$, so $a \mid c$, and $(a,c) \in R$.

\problempart Draw the Hasse diagram for $R$ on the numbers $2,\ldots,10$.

\begin{picture}(500, 150)(-100, -20)
\put(0,-5){2}
\put(50,-5 ){3}
\put(0,50 ){4}
\put(100,-5){5}
\put(40,50){6}
\put(150,-5){7}
\put(0,100){8}
\put(60,50){9}
\put(45,100){10}

\put(3,7){\line(0,1){40}}
\put(3,60){\line(0,1){35}}

\put(3,7){\line(1,2){43}}
\put(100,7){\line(-1,2){43}}

\put(53,7){\line(-1,5){8}}
\put(53,7){\line(1,5){8}}

\put(3,7){\line(4,5){33}}

\end{picture}

\problempart What (1 word) are the minimal elements of this particular
poset called?

primes

\problempart What is the greatest lower bound of two elements in this
poset called?

GCD

\problempart What is the longest chain in $R$ (over $\{2,\ldots,100\}$)?

$ \floor{\log_2 100}=5 $ ($ 2 \rightarrow 4 \rightarrow 8 \rightarrow 16 
\rightarrow 32 \rightarrow 64$)

\problempart What does the previous part imply about the largest antichain?
Why?



Recall that Dilworth's theorem says:\\
$\forall t$, every poset with $n$ elements must have a
chain of size $ > t$ or an antichain of size $\geq \frac{n}{t}$.

So, since there is a chain of size 6, there must be an antichain of size
$\geq \floor{\frac{99}{5}} = 19$.


\problempart Prove that $\{51,\ldots,100\}$ is an antichain and that
no set strictly containing it is an antichain.

$Q = \{ 51, \cdots, 100 \}$ is an antichain since if any distinct
$s_1 \in Q$ and  $s_2 \in Q$,  had $s_1 | s_2$, then $s_2 = k s_1$ but
the minimum $k$ is 2 if $s_1 \neq s_2$, so $s_2 = 2 s_1$, but
$2s$ for any $s \in Q$ is between 102 and 200.

No set containing $Q$ can be an antichain, since it would contain 
some number, $n$ where $2 \leq n \leq 50$, but we can find some
integer $k$ such that $51 \leq k n \leq 100$ for all $2 \leq n \leq 50$.

\end{problemparts}

\newpage \problem \points{10} Alice, Bob, Cindy, Daniel, Ellen, and Frank work at MIT.
Alice works Monday, Tuesday, and Saturday.  Bob works Tuesday and
Wednesday.  Cindy works Sunday, Wednesday, and Thursday.  Daniel
works Thursday and Friday.  Ellen works Monday and Friday.  Frank
works Saturday and Sunday.  We want to assign each worker a single
parking space at MIT such that at most one person uses each parking
space on a given day.  Of course, people who work different days can
share a parking space.

\begin{problemparts}

\ppart Draw a conflict graph capturing the constraints on who can share
parking spaces.

\begin{picture}(500, 150)(-100, -20)


\put(-30,45){Alice}
\put(40,105) {Bob}
\put(90,105) {Cindy}
\put(150,45){Daniel}
\put(90,-10){Ellen}
\put(35,-10){Frank}

\put(0,50){\line(1,1){50}}  % A to B
\put(50,100){\line(1,0){50}} % B to C
\put(100,100){\line(1,-1){50}} % C to D
\put(150,50){\line(-1,-1){50}} %D to E
\put(0,50){\line(1,-1){50}} %A to F

\put(50,0){\line(1,2){50}} % C to F
\put(0,50){\line(2,-1){100}} % A E

\end{picture}

\ppart Give an assignment of people to spaces that uses the fewest
possible parking spaces.  

There are a variety of solutions, all involving three-colors (or parking spots),
one is: \\
Alice and Cindy \\
Bob, Frank, and Daniel \\
Ellen

\ppart Prove that you cannot do better.

To do better, we'd have to be able to color the graph with two
colors, but this would mean the graph is a bipartite.  Since it has an odd
cycle (ABCDE), it cannot be a bipartite, therefore 3 colors is the best
we can do.

\end{problemparts}

\newpage \problem \points{10} For a tree $T$, let $L(T)$ denote the number of leaves in $T$
and let $H(T)$ be the number of vertices whose degree {\bf exceeds} 2.
Prove by induction on the number of vertices in $T$ that $L(T) \ge
H(T)$.

Proof by induction the number of vertices, $n$, in the tree.

We'll start with a base case of 2 vertices since otherwise we need to
be careful about degree 0 vertices.

Base case: 2 vertices.  Graph is a single edge. \\
$L(T_1) = 2, H(T_1) = 0,$ and $ L(T_1) \geq H(T_1)$.

Inductive hypothesis:  $P(n)$: $L(T) \geq H(T)$ for any tree of
size $n$ or fewer vertices.

Show $P(n) \rightarrow P(n+1)$ \\
Given a tree, $T_{n+1}$, of size $n+1$ vertices. There must exist
a leaf (by a theorem shown in class), so remove a leaf.  
The new tree, $T_n$, must have $L(T_n) \geq H(T_n)$ by the inductive
hypothesis.  Now, by removing the vertex from $T_{n+1}$,
the node went from a state of having $X$ edges to $Y$ edges:
\begin{itemize} 
\item $ > 3$ edges to $ \geq 3$ edges \\

$H(T_{n+1}) = H(T_n), L(T_{n+1}) = L(T_n) +1$, so 
\[ H(T_{n+1}) = H(T_n) \leq L(T_n) = L(T_{n+1}) -1 \leq L(T_{n+1}) \]

\item 3 edges to 2 edges \\

$ H(T_{n+1}) = H(T_n) + 1 $ and $ L(T_{n+1}) = L(T_n) + 1 $ so 
\[ H(T_{n+1}) = H(T_n) +1 \leq  L(T_{n}) + 1 = L(T_{n+1}) \]
so $ H(T_{n+1}) \leq  L(T_{n+1})$.


\item 2 edges to 1 edge \\

$ H(T_{n+1}) = H(T_n)$, and $L(T_{n+1}) = L(T_n) + 1$, so 

\[ H(T_{n+1}) = H(T_n) \leq  L(T_n) = L(T_{n+1}) -1 \leq L(T) \]

\item 1 edge to no edges \\
$n$ must be 2 in this case.  $H(T_2) = 0 \leq L(T_2) = 2$, so
$0 = H(T_2) \leq L(T_2) = 2$.
\end{itemize} 

{ \bf Comments: }

1.  it is easier for this problem to remove a leaf
than an internal edge.  This is often the case.

2.  A lot of people didn't notice that when you remove a leaf, you
might create a new leaf.


\end{problems}
\end{document}

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
