\documentclass[12pt,twoside]{article}

\def\handouttype{problemset}

\usepackage{psfig}

\input{macros-course}

\def\cent{{\not\!\mathrm{c}}}

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

\typein[\answer]{Include solutions? (y/n) }
\def\yes{y}
\ifx\answer\yes
  \typeout{}
  \typeout{Solutions *INCLUDED*.} 
  \newcommand{\reading}[1]{}
  \newcommand{\omitsolution}[1]{#1}
  \usepackage[dark,first,bottom]{draftcopy}
  \draftcopyName{Solutions}{155}
\else 
  \typeout{}
  \typeout{Solutions *NOT INCLUDED*.} 
  \newcommand{\reading}[1]{#1\vfill\mbox{}\newpage}
  \newcommand{\omitsolution}[1]{\vspace*{0.5in}}
\fi
\typeout{}

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

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut6}
\newcommand{\tutnum}{6}
\newcommand{\tutdate}{March 9, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{\tutref}{Mini-Quiz \tutnum}{\tutdate}

\begin{enumerate}
\item Write your name:

\bigskip

\item (Rosen, Sec. 2.6, Ex. 29)
Let 
\begin{eqnarray*}
A & = &  
\left[
\begin{array}{ccc}
1 & 0 & 1 \\
1 & 1 & 0 \\
0 & 0 & 1 \\
\end{array}
\right]
\\
 & & \\
B & = &  
\left[
\begin{array}{ccc}
0 & 1 & 1 \\
1 & 0 & 1 \\
1 & 0 & 1 \\
\end{array}
\right]
\\
\end{eqnarray*}

  Find the following:

  \begin{enumerate}
  \item $A \Or B$
  \item $A \And B$
  \item $A \odot B$
  \end{enumerate}


\omitsolution{%
  \begin{solution}
  
  
  \medskip
  \textbf{Solution:} \\

  \begin{enumerate}
  \item $A \Or B$: \\
\[
\left[
\begin{array}{ccc}
1 & 1 & 1 \\
1 & 1 & 1 \\
1 & 0 & 1 \\
\end{array}
\right]
\]
  \item $A \And B$: \\
\[
\left[
\begin{array}{ccc}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{array}
\right]
\]
  \item $A \odot B$: \\
\[
\left[
\begin{array}{ccc}
1 & 1 & 1 \\
1 & 1 & 1 \\
1 & 0 & 1 \\
\end{array}
\right]
\]
  \end{enumerate}

  \end{solution}
  }

\end{enumerate}

\newpage

\begin{problems}

\problem Is a Harvard degree really worth more than an MIT degree?!  Let
us say that a person with a Harvard degree starts with \$40,000 and gets a
\$20,000 raise every year after graduation, whereas a person with an MIT
degree starts with \$30,000, but gets a 20\% raise every year.  Assume
inflation is a fixed $8\%$ every year.  That is, \$1.08 a year from now is
worth \$1.00 today.  (You'll need a calculator to get final answers; if
one is not available, it's ok to express the answer as a closed form
numerical expression.)

\bparts

\ppart % added this in to jump-start the slower groups!
How much will a person with a Harvard degree be making in the $n^{th}$ year?

\omitsolution{%
  \begin{solution}
  
  \medskip
  \textbf{Solution:} \\
     \[
       40000 + 20000(n - 1)
     \]
  \end{solution}
  }

\ppart
How much will a person with an MIT degree be making in the $n^{th}$ year?

\omitsolution{%
  \begin{solution}
  
  \medskip
  \textbf{Solution:} \\
     \[
       30000(1.2^{n-1})
     \]
  \end{solution}
  }

\ppart How much is a Harvard degree worth today if the holder will work
for $n$ years following graduation? \hint In Lecture 8 a closed formula
for $\sum_{i=0}^{n} ir^i$ was derived.

\omitsolution{%
  \begin{solution}
  
  \medskip
  \textbf{Solution:} \\

One dollar after year $i$ is worth $r^i$ in today's currency, where
\[
r= \frac{1}{1.08} = 0.925\, 925\, 925 \dots.
\]
So 
\begin{eqnarray*}
\mbox{Hvd}_n & = & \sum_{i=0}^{n-1} (40000+ 20000i)r^i\\
        & = & 40000\sum_{i=0}^{n-1} r^i + 20000\sum_{i=0}^{n-1} i r^i.
\end{eqnarray*}

But we know from Lecture Notes 8 that
\[
\sum_{i=0}^{n} ir^i = \frac{{r - (n+1) r^{n+1} + n r^{n+2}}}{(1-r)^2},
\]
so 
\begin{equation*}
\mbox{Hvd}_n  =  40000 \frac{(1- r^{n})}{1 - r}  + 
                   20000 \frac{(r - n r^{n} + (n-1) r^{n+1})}{(1-r)^2}, 
\end{equation*}
and for $n=20$,
\begin{equation*}
\mbox{Hvd}_{20}  = \$1,916,483.
\end{equation*}
(As indicated in the first two parts, we have avoided counting
the $n+1$ year, in which we do not actually work.)

  \end{solution}
  }

\ppart How much is an MIT degree worth in this case?

\omitsolution{%
  \begin{solution}
  
  \medskip
  \textbf{Solution:} \\

\begin{eqnarray*}
\mbox{MIT}_n & = & 30000\sum_{i=0}^{n-1} {1.2}^i r^i\\
        & = & 30000\sum_{i=0}^{n-1} (1.2r)^i\\
        & = &  \frac{{30000(1 - (1.2r)^{n})}}{1 - 1.2r} 
\end{eqnarray*} 
and for $n=20$,
\begin{eqnarray*}
\mbox{MIT}_{20} & = &  \frac{{30000(1 - (1.2r)^{20})}}{1 - 1.2r} = \$1,950,821. \hfill
\end{eqnarray*}

  \end{solution}
  }

\ppart If you plan to retire after twenty years, which degree would
be worth more?

\omitsolution{%
  \begin{solution}
  
  
  \medskip
  \textbf{Solution:} \\

The MIT degree is more valuable -- as if you couldn't guess \texttt{:-)}
 -- but only by about 5\%.  But if you were persistent enough to work 30
years, you would find the MIT degree was worth more than twice as much.

  \end{solution}
  }

\eparts

\clearpage
\problem There ``sum'' and ``difference'' operators that play the same
role in discrete math as integral and derivative operators place in
calculus.  
% pause as the students cringe upon hearing this. Savor.
In particular, the difference operator $\Delta$ is defined by
\[
\Delta f(x) = f(x+1)-f(x)
\]
and the summation operator
\[
\sum_a^b g(x) \delta x  = \sum_{x=a}^{b-1} g(x)
\]
This sum operator is a bit annoying, as many sloppy mathematicians
will use the left hand side to denote a sum up to $b$, rather than
$b-1$.  But let's work with it for today.

\begin{problemparts}
\ppart Suppose that $g(x) = \Delta f(x)$.  Prove that
\[
\sum_a^b g(x) \delta x = f(b)-f(a)
\]

\omitsolution{%
  \begin{solution}
  
  \medskip
  \textbf{Solution:} \\

  \end{solution}
  }


\ppart Suppose that $h(n) = \sum_{k=0}^n f(k)$.  What is $\Delta h (n)$?

\omitsolution{%
  \begin{solution}
  
  \medskip
  \textbf{Solution:} \\

\[ f(n+1) \]

  \end{solution}
  }


\ppart Prove that 
\[
\Delta(u(x)v(x)) = u(x)\Delta v(x) + v(x+1) \Delta u(x)
\]

\omitsolution{%
  \begin{solution}
  
  \medskip
  \textbf{Solution:} \\

  \end{solution}
  }


\ppart The \emph{falling power} function is defined by the equation
\[
x^{\underline m} = x(x-1)\cdots(x-m+2)(x-m+1).
\]
In other words, just like $x^m$, it is a product of $m$ terms, but
they fall away from $x$.  Prove that
\[
\Delta x^{\underline m} = m x^{\underline{m-1}}
\]

\omitsolution{%
  \begin{solution}
  
  \medskip
  \textbf{Solution:} \\

  \end{solution}
  }


\ppart Find the value of
\[
\sum_{x=a}^b x^{\underline m}
\]

\omitsolution{%
  \begin{solution}
  
  \medskip
  \textbf{Solution:} \\

  \end{solution}
  }


\end{problemparts}


\problem

Consider the caching system given in lecture as a lebeled state machine>


\begin{itemize}
\item \textbf{Caching system} 

\emph{
The memory can be updated at any time. 
This may leave one or both of the caches out-of-date. 
Also, at any time, the latest value may be copied from the memory to a
cache, overwriting any older value that's there. 
Also, at any time, a value may be dropped from a cache. 
} \\

State machine: 

$Q$: $\{ (memory, cache1, cache2) \mbox{ of the types described above}\}$. \\
$Q_0$: memory is arbitrary, caches map everything to $\ms{null}$. \\
%$\delta$: 
$L$:

Input Labels:

\begin{itemize}
\item $\ms{request-read}(x,1)$ is an input from client $1$ requesting to
read the value in address $x$ from his local cache ($\ms{cache1}$).
\item $\ms{request-read}(x,2)$ same, for client $2$.
\item $\ms{request-write}(x,v,1)$, $\ms{request-write}(x,v,2)$ are requests
by the two clients to write value $v$ in location $x$ in memory (not
cache).
\end{itemize}

Output Labels:

\begin{itemize}
\item $\ms{return-read}(v,1)$, $\ms{return-read}(v,2)$
\item $\ms{return-write}(``OK'',1)$, $\ms{return-write}(``OK'',2)$.
\end{itemize}

Internal Labels:

\begin{itemize}
\item $\ms{compute-read}$ does the actual read from a local cache, after
it's been requested and the value is non-null.
\item $\ms{compute-write}$ does the actual write to memory, after it's been
requested.
\begin{itemize}
\item \textbf{Strong cache: }
cleans out the location in both caches.
\item \textbf{Weak cache: }
cleans out the location in only 1 cache.
\end{itemize}
	
\item $\ms{copy}$ copies a value from memory to a cache.
\item $\ms{drop}$ drops a value from a cache.
\end{itemize}

%$(\ms{memory}, \ms{cache1}, \ms{cache2}) \rightarrow 
% (\ms{memory}', \ms{cache1}', \ms{cache2}')$ \\
%where (five kinds of steps): 
%\begin{enumerate}
%\item New memory is same as old memory except that at most one of the addresses
%gets a new value. Caches unchanged. \\
%$\ms{memory}(a) :=$ arbitrary $\ms{value}$ (not null).
%
%\item One address in $\ms{cache1}$ gets updated from memory. \\ 
%$\ms{cache1}(a) := \ms{memory}(a)$ 
%
%\item One address in $\ms{cache2}$ gets updated from memory. \\ 
%$\ms{cache2}(a) := \ms{memory}(a)$ 
%
%\item One value gets dropped from $\ms{cache1}$. \\
%$\ms{cache1}(a) := \ms{null}$ 
%
%\item One value gets dropped from $\ms{cache2}$. \\
%$\ms{cache2}(a) := \ms{null}$ 
%\end{enumerate}


\end{itemize}

\problempart

Try to prove, as carefully as you can, that the strong caching system
labeled state machine described in the lecture notes in fact
implements the centralized memory labeled state machine.

This proof can be done using ad hoc methods, starting from any
execution of the caching system and constructing the
(possibly infinite) execution of the centralized memory machine.
The construction can proceed by structural induction on the definition
of the execution of the caching system.


\problempart
Prove by induction that the trace of the nth finite prefix of the
execution of the cache system is the same as the trace of the
corresponding finite prefix of the centralized memory machine. 


\omitsolution{%
  \begin{solution}
  
  \medskip
  \textbf{TA note:} \\

If time allows, show them the Abstraction Theorem and show how the
proof could be made very systematic using this theorem.

  \end{solution}
  }





\end{problems}

\end{document}

\endinput


\end{document}

\endinput
