\documentstyle{article}
\input{macros-course}

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

\begin{document}

\pset{9}{April 8, 1997}{April 15, 1996}

{\bf Reading:} Rosen 1.7--1.8, 5.1--5.3, 7.5.

\begin{problems}

  \problem Suppose we have a baseball league with 21 teams, and
  we are given a schedule in which each team plays 14 games.
\bparts
\ppart
Assuming all
teams are in different cities, prove that we can arrange for each team
to play the same number of home and away games).
\ppart Prove we can split the season into two halves (one before and
  one after the all-star break) in which each team plays seven games.
\eparts


\vspace{-.3in}
\problem For a simple undirected graph with edges $e_1,\ldots,e_m$,
consider the following algorithm:
\begin{tabbing}
else \= else \= else \= else \= \kill
initially, unmark every edge\\
{\bf for} $i=1$ to $m$\\
\>   {\bf if} there does not exist a path of marked edges between the  endpoints of $e_i$\\
\> \> mark edge $e_i$\\
\end{tabbing}
\vspace*{-.2in}
Prove that when the algorithm finishes, the set of marked edges forms
a spanning forest of the input graph.  (Hint: it may help to consider
the graphs consisting of the edges $e_1,\ldots,e_k$ for various values
of $k$.)

\vspace{-.2in}
\problem Consider the following state machine on a graph
$G$.  A state is specified by labeling each vertex of $G$ as {\em
  uncolored}, {\em red}, or {\em blue}.  Initially, all vertices are
uncolored except for one vertex $v$ which is red.
\vspace{-.3in}
\iocode{
\prcef{$\ms{make-blue}(w)$}
{% Precondition: \\
   a neighbor of $w$ is red}
{% Effect: \\
   $w$ becomes blue}
}{
\prcef{$\ms{make-red}(w)$}
{% Precondition: \\
   a neighbor of $w$ is blue}
{% Effect: \\
   $w$ becomes red}

}

\bparts
\ppart Prove that if $G$ is bipartite and the above code reaches a state
where all vertices are colored, then the coloring is a legal coloring
(that is, all neighbors of a red vertex are blue, and vice versa).
You'll want to use some facts from the last homework to do this.  

\ppart For
what kinds of bipartite graphs is it possible to reach a state in
which all vertices are colored?  A brief explanation without proof
is sufficient.
\eparts

\vspace{-.3in}
\problem
Which of the following assertions is true?
Prove your answer.
\begin{enumerate}
 \item 
  If $f$ is $O(g)$ then $\ln f$ is $O(\ln g)$.
 \item    
  If $\ln f$ is $O(\ln g)$ then $f$ is $O(g)$.
 \item 
  If $f$ is $O(g)$ and $g$ is never zero then $1/g$ is $O(1/f)$.
\end{enumerate}

\vspace{-.3in}
\problem
A college loan officer offers you the following deal.
He will give you \$25,000 at the start of each year for four years
starting today to pay for your college tuition.
In return, you must pay \$15,000 at the start of each year for fifteen years
starting in four years.  Suppose the annual interest rate is 5\%.
Is this a good deal? Explain.
\newpage
\vspace{-.3in}
\problem The integral method
\bparts
\ppart
Find tight ($\Theta$) asymptotic bounds for the summation
$\displaystyle
\sum_{i=n}^{\infty}{\frac{1}{i^2}}
$
where $n > 0$.
\ppart
Give tight ($\Theta$) bounds for 
$\displaystyle \sum_{i=1}^n \frac{1}{\sqrt{i}}$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vspace{-.3in}
\problem
Find a closed form expression $f(n)$ for 
$\displaystyle\sum_{i=1}^n i^2 x^i$.


\vspace{-.3in}
\problem By manipulating summations, without recourse
to induction, prove that
\[
\sum_{k=1}^n H_k = (n+1)H_n-n
\]


\vspace{-.3in}
\problem
Apparently, a standard model used by lobster fishermen is the following:
the number of lobsters caught in a given year is the average of the
number caught in the previous two years.  Let's try out this model
in the following hypothetical fishing community --- 
in year $0$, there were $100$ lobsters 
caught, and in year $1$, there were $300$ lobsters caught.  

\bparts
\ppart
Let $f(i)$ denote the number of lobsters caught in year $i$.
Write a recurrence relation for $f(i)$ and obtain a closed-form
solution.
\ppart
Now let's consider the following variation on this model: the number
of lobsters caught in a given year is the average of the number
caught in the previous {\em three} years.  To start things off,
suppose that $100$ were caught in year $0$, $300$ in year $1$, and
$200$ in year $2$.

Let $g(i)$ denote the number of lobsters caught in year $i$ under
this model.  Again, write a recurrence relation for $g(i)$ and 
obtain a closed-form solution.

\eparts

\vspace{-.3in}
\problem Consider the following recurrence:
\[
T(n)=aT(n/2)+n^2\log_2 n, \quad T(1)=1.
\]
\vspace*{-.3in}
\bparts
\ppart Using plug and chug, derive a solution to this recurrence in
summation form.
\ppart Prove that the recurrence satisfies this summation form
\ppart By manipulating sums, derive a (simple) closed form for the
summation in the case $a=2$.
\ppart Derive a (messy) closed form for the summation when $a \ne 2$.
\eparts

%\vspace{-.3in}
%\problemopt Available on the web, http://theory.lcs.mit.edu/classes/6.042/

\vspace{-.2in}
\problemopt ``Finite Calculus'' works with sums the way standard
calculus works with integrals.  Just like standard calculus has an
inverse to the integral, namely the derivative, finite calculus has an
inverse to summation,  namely the {\em difference} operator
\[
\Delta_x f(x) = f(x+1)-f(x).
\]
We can modify the summation notation to be more like integration, writing
\[
\Sigma_a^b g(x) \delta x = \sum_{x=a}^{b-1} g(x).
\]
\vspace*{-.2in}
\bparts
\ppart Prove that $\Delta_x \Sigma_a^x f(y) \delta y = f(x)$ (analogue
to $D\int_a^{x} f(y) dy = f(x)$).
\ppart Prove that $\Sigma_a^b (\Delta_x g(x)) \delta x = f(b)-f(a)$
(analogue to $\int_a^b (Df(x)) dx = f(b)-f(a)$)
\ppart Define $x^{\underline m} = x(x-1)(x-2)\cdots(x-m)$. Prove that
$\Delta_x x^{\underline m} = mx^{\underline{m-1}}$
\ppart Prove that $\sum_{0}^n x^{\underline m}\, \delta x = \frac{n^{\underline{m+1}}}{m+1}$
\eparts

\end{problems}
\end{document}


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




