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

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{6}{October 20, 1994}{In recitation, October 28}

\begin{center}

{\bf Reading:\  [MR] Chapter 5, [CLR] Chapter 4 (Handout~\ref{clrchap4}).}

\bigskip\medskip
\fbox{
\parbox{6in}{
\noindent {\bf Final Exam:}  
Our final exam has ``finally'' been scheduled.  It will be held
\smallskip
%\renewcommand{\baselinestretch}{2}
\begin{center} \large \bf
Tuesday, December 20, \\ %\hspace*{.25in}
9:00 {\sc a.m}--12:00 {\sc p.m.}  \\ % \hspace*{.25in} 
in 4-370.\end{center}
}}
\end{center}

%%	Final:  12/20, 9-12, 4-370.
\bigskip

\begin{problems}

\problem
A college loan officer offers you the following deal.
He will give you \$20,000 at the start of each year for four years
starting today to pay for your college tuition.
In return, you must pay \$10,000 at the start of each year for ten years
starting in four years.  The annual interest rate is 10\%.
Is this a fair deal?

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Find a closed form expression $f(n)$ for 
$\displaystyle\sum_{i=1}^n i^3$.\\
Use one of the methods given in lecture.\\
(\hint  Don't use the method of problem 2 unless you love derivatives!)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Use iteration to find a closed form expression for the recurrence
$$T(n) = aT(n/2) + bn$$ for $n>1$ and $T(1)=b$,
where $a$ and $b$ are constants.
You may assume $n$ is a power of $2$. 
Consider separately the cases $a<2$, $a=2$, and~$a>2$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\problem
Give tight asymptotic bounds ($\Theta$) for the following recurrences.
For each, $T(1)=1$.
\bparts
\ppart $T(n) = 3T\left(\floor{n\over 3}\right) + n$.
\ppart $T(n) = 4T\left(\floor{n\over 3}\right) + n^2$.
\ppart $T(n) = 3T\left(\floor{n\over 4}\right) + n$.
\ppart $T(n)=T\left(\floor{n\over 4}\right)+T\left(\floor{n\over 3}\right)+n$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Find an exact closed form solution for the recurrence
$$T(n) = \sum_{i=1}^{n-1} T(i)$$ for $n>1$ and $T(1)=1$.
(\hint  Find a simple formula for $T(n)-T(n-1)$.)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
Find an exact closed form solution for the recurrence
$$T(n) = 4T(n-1) - 4T(n-2) + n^2$$ 
for $n>1$, and $T(0)=0$, $T(1)=1$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
{\bf The graduate-student job problem made worse.} 
Consider the following depressing scenario: 
Every year, each professor of computer science graduates one new graduate
student who holds a postdoc for one year and then goes on to become a 
professor the following year.
To compound the miseries of newly graduating students, in year $n\geq 2$,
there are $2^{n-2}$ physicists who change careers to become computer science 
professors without going to graduate school. 
Let $f(n)$ denote the number of computer science professors after $n$ years.
Assume $f(0)=0$ and $f(1)=1$.  It follows that $f(2)=2$: in year 2,
there are two CS professors, namely the one CS professor from year 1 and the 
one physicist transfer (there is also one postdoc who graduated in year 1 
and will be professor in year~3).

\bparts
\ppart
Compute $f(3)$, $f(4)$, and $f(5)$.
\ppart
Set up a recurrence relation obeyed by~$f(n)$.
\ppart
Solve your recurrence to find a closed form for~$f(n)$.

%	\problempart
%	If $g(n) = c^n$ then for what value of $c$ will the influx of
%	outsiders begin to make a significant difference to the growth rate of
%	the number of professors (and wannabes)?
\eparts


\end{problems}

\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	False inductive proof about sum of i being O(n).

Return-Path: <dbwilson@theory.lcs.mit.edu>
From: dbwilson@theory.lcs.mit.edu (David Bruce Wilson)
Date: Sun, 16 Oct 94 13:48:18 EDT
To: cel, ftl, ponzio
Subject: problem set

Hi, on the next problem set, I'd like to see them prove that
ln n! - (n ln n - n + 1/2 ln n) converges.

