\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$: \\
  Note that $\odot$ means boolean product. Use matrix multiplication, but 
cap the values at one:\  $1+1 = 1 \cdot 1 = 1$
\[
\left[
\begin{array}{ccc}
1 & 1 & 1 \\
1 & 1 & 1 \\
1 & 0 & 1 \\
\end{array}
\right]
\]
  \end{enumerate}

  \end{solution}
  }

\end{enumerate}

\newpage
\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage
\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

\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)
     \]
     Note that in the $n^{th}$ year, you have not yet gotten the $n^{th}$
raise. You should always check your boundary cases -- in this case, the
salary in the first year.
  \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. We also could have started
with:
\begin{eqnarray*}
\mbox{Hvd}_n & = & \sum_{i=1}^{n} 
(salary\textrm{-}in\textrm{-}ith\textrm{-}year)\cdot
(inflation\textrm{-}adj\textrm{-}for\textrm{-}ith\textrm{-}year)\\
 & = & \sum_{i=1}^{n} (40000+ 20000(i-1))r^{i-1}\\
 & = & \sum_{i=0}^{n-1} (40000+ 20000i)r^i
\end{eqnarray*}
which is equivalent. A good thing to check for here, besides the boundary cases,
is the number of items you are summing. If the summation were from $0$ to $n$, that
would be $n+1$ years -- clearly a mistake.)

  \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 2\%.  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 are ``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}

  \textbf{Solution:} \\
	Loosely,
\begin{eqnarray*}
\sum_a^b g(x) \delta x & = & \sum_{x=a}^{b-1} g(x) \\
 & = & \sum_{x=a}^{b-1} \left[ f(x+1) \; - \; f(x) \right] \\
 & = & \sum_{x=a}^{b-1} f(x+1) \; - \; \sum_{x=a}^{b-1} f(x) \\
 & = & \sum_{x=a+1}^{b} f(x) \; - \; \sum_{x=a}^{b-1} f(x) \\
 & = & f(b) \; + \; \sum_{x=a+1}^{b-1} f(x) \; - \; \sum_{x=a+1}^{b-1} f(x) \; - \; f(a) \\
 & = & f(b) \; - \; f(a) 
\end{eqnarray*}

	A more formal proof can be done using induction. Note, however, that using
induction does not help if you cannot guess the correct formula. Manipulating the
summations will give you a feel for that.

 Fix arbitrary $a$, 
and induct over the values of $b$. Take as the base case $b=a$, for which
the given equation trivially holds -- there are no terms in the summation,
and $f(a) - f(a) = 0$.

	Now, assuming $\sum_a^b g(x) \delta x = f(b)-f(a)$, prove
$\sum_a^{b+1} g(x) \delta x = f(b+1)-f(a)$.
\begin{eqnarray*}
\sum_a^{b+1} g(x) \delta x & = & \sum_a^{b} g(x) \\
 & = & g(b) \; + \; \sum_a^{b-1} g(x) \\
 & = & g(b) \; + \; \sum_a^{b} g(x) \delta x \\
 & = & g(b) \; + \; f(b) \; - \; f(a) \;\;\;\;\; \mathbf{(IH)} \\
 & = & \Delta f(b) \; + \; f(b) \; - \; f(a) \\
 & = & f(b+1) \; - \; f(b) \; + \; f(b) \; - \; f(a) \\
 & = & f(b+1) \; - \; f(a) 
\end{eqnarray*}
  \end{solution}
  }


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

\omitsolution{%
  \begin{solution}
  
  \medskip
  \textbf{Solution:} \\
\begin{eqnarray*}
\Delta h (n) & = & h(n+1) \; - \; h(n) \\
 & = & \sum_{k=0}^{n+1} f(k) \; - \; \sum_{k=0}^{n} f(k) \\
 & = & f(n+1) \; + \; \sum_{k=0}^{n} f(k) \; - \; \sum_{k=0}^{n} f(k) \\
 & = & f(n+1)
\end{eqnarray*}
  \end{solution}
  }


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

\omitsolution{%
  \begin{solution}

  \textbf{Solution:} \\
	We can work left to right and make it look like magic, introducing a
zero-sum pair out of the void. Or we can work right to left:
\begin{eqnarray*}
u(x)\Delta v(x) \; + \; v(x+1) \Delta u(x) & = &  
	u(x)\left(v(x+1) \; - \; v(x)\right) \; + \; v(x+1)\left(u(x+1) \; - \; u(x)\right) \\
 & = & u(x)v(x+1) \; - \; u(x)v(x) \; + \; v(x+1)u(x+1) \; - \; v(x+1)u(x) \\
 & = & v(x+1)u(x+1) \; - \; u(x)v(x) \\
 & = & \delta(u(x)v(x))
\end{eqnarray*}
  \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
\[
\Delta x^{\underline m} = m x^{\underline{m-1}}
\]

\omitsolution{%
  \begin{solution}

  \textbf{Solution:} \\
\begin{eqnarray*}
\Delta x^{\underline m} & = & (x+1)^{\underline m} \; - \; x^{\underline m} \\
 & = & (x+1)\mathbf{(x)(x-1)\cdots(x-m+2)} \\
 &   & \; - \;\;\;\;\;\;\; \mathbf{(x)(x-1)\cdots(x-m+2)}(x-m+1) \\
 & = & (x+1)x^{\underline {m-1}} \; - \; (x-m+1)x^{\underline {m-1}} \\
 & = & mx^{\underline {m-1}}
\end{eqnarray*}
  \end{solution}
  }


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

\omitsolution{%
  \begin{solution}

  \textbf{Solution:} \\
We can use 
\[
\delta x^{\underline m} = m x^{\underline{m-1}}
\rightarrow x^{\underline{m}} = \frac{1}{m+1}\Delta x^{\underline {m+1}}
\]
\begin{eqnarray*}
\sum_{x=a}^b x^{\underline m} & = & 
   \sum_{x=a}^b \frac{1}{m+1}\Delta x^{\underline {m+1}} \\
 & = & \frac{1}{m+1}\sum_{x=a}^b \Delta x^{\underline {m+1}} \\
 & = & \frac{1}{m+1}\sum_{x=a}^b \left[ (x+1)^{\underline {m+1}} 
   \; - \; x^{\underline {m+1}} \right] \\
 & = & \frac{1}{m+1} \left[ \sum_{x=a}^b (x+1)^{\underline {m+1}} 
   \; - \; \sum_{x=a}^b x^{\underline {m+1}} \right] \\
 & = & \frac{1}{m+1} \left[ \sum_{x=a+1}^{b+1} x^{\underline {m+1}} 
   \; - \; \sum_{x=a}^b x^{\underline {m+1}} \right] \\
 & = & \frac{1}{m+1} \left[ (b+1)^{\underline {m+1}} \; + \; \sum_{x=a+1}^{b} x^{\underline {m+1}} 
   \; - \; a^{\underline {m+1}} \; - \; \sum_{x=a+1}^b x^{\underline {m+1}} \right] \\
 & = & \frac{ (b+1)^{\underline {m+1}} \; - \; a^{\underline {m+1}} }{m+1}
 \end{eqnarray*}
  \end{solution}
  }


\end{problemparts}

\clearpage
\problem

Consider the Strong Caching system given in lecture as a labeled state machine:

%%%%%%%%%%%%%%%%%%%%%%%% begin SC

\textbf{Caching system (strong)} 

%\small{
\begin{small}

\emph{
The system is composed of a main memory store that is accessed by two 'clients'.
Each client accesses the memory through a cache. When the memory is updated,
the caches are cleaned out.
} \hfill \\

State machine: 

  \begin{itemize}
\item
$Q$: 
For every $x \in addresses$:
  \begin{itemize}
  \item $\ms{memory(x)}$, \ an element of $data$ 
  \item $\ms{cache_1(x)}$, \ an element of $\ms{data} \cup \{ null \}$
  \item $\ms{cache_2(x)}$, \ an element of $\ms{data} \cup \{ null \}$
  \end{itemize}
And a number of doubled structures (one for each client/cache):
  \begin{itemize}
  \item $\ms{req_1}$, \ an element of $\{ ``read'', ``write'' \} \cup \{ \ms{null} \}$ 
  \item $\ms{reqaddr_1}$, \ an element of $\ms{addresses} \cup \{ \ms{null} \}$ 
  \ \ (used for both reads and writes)
  \item $\ms{reqval_1}$, \ an element of $\ms{data} \cup \{ \ms{null} \}$ 
  \ \ (used for writes only)
  \item $\ms{ret_1}$, \ an element of $\{ ``OK'', \ms{null} \} \cup \ms{data} $

  \item $\ms{req_2}$, \ an element of $\{ ``read'', ``write'' \} \cup \{ \ms{null} \}$ 
  \item $\ms{reqaddr_2}$, \ an element of $\ms{addresses} \cup \{ \ms{null} \}$ 
  \ \ (used for both reads and writes)
  \item $\ms{reqval_2}$, \ an element of $\ms{data} \cup \{ \ms{null} \}$ 
  \ \ (used for writes only)
  \item $\ms{ret_2}$, \ an element of $\{ ``OK'', \ms{null} \} \cup \ms{data} $
  \end{itemize}

\item 
$Q_0$:
$\ms{memory}$ arbitrary, caches all $\ms{null}$, all other components $\ms{null}$. 
%(Note that $\ms{null}$ is a special symbol, not the empty set $\emptyset$).

\item 
$L$: 
All are for $i \in \{ 1,2 \}$ (each client). Note that, for each label, the italicized text 
is just a description of the intended purpose.
  \begin{itemize}
  \item[] Input labels:
    \begin{itemize}
    \item[] $\mathbf{req\textrm{-}read_i}(x)$, \ \ $x \in \ms{addresses}$ \\
	\emph{ \ \ an input from client $i$ requesting to read the value in address $x$
	 from $\ms{cache_i}$.}
    \item[] $\mathbf{req\textrm{-}write_i}(x, v)$, \ \ $x \in \ms{addresses}$,
         $v \in \ms{data}$ \\
	\emph{ \ \ a request by client $i$ to write value $v$ in location $x$ in memory 
	 (not cache).}
    \end{itemize}

  \item[] Internal labels:
    \begin{itemize}
    \item[] $\mathbf{comp\textrm{-}read_i}(x)$, \ \ $x \in \ms{addresses}$ \\
	\emph{ \ \ actually performed the read that was requested and stored the result. }
    \item[] $\mathbf{comp\textrm{-}write_i}(x, v)$, \ \ $x \in \ms{addresses}$,
         $v \in \ms{data}$ \\
	\emph{ \ \ actually performed the write that was requested. }
    \item[] $\mathbf{copy_i(x)}$, \ \ $x \in \ms{addresses}$ \\
	\emph{ \ \ copied the value at $x$ from memory into $cache_i$. }
    \item[] $\mathbf{drop_i(x)}$, \ \ $x \in \ms{addresses}$ \\
	\emph{ \ \ dropped the value at $x$ from $cache_i$. }
    \end{itemize}

  \item[] Output labels:
    \begin{itemize}
    \item[] $\mathbf{ret\textrm{-}read_i}(v)$, \ \   $v \in \ms{data}$ \\
	\emph{ \ \ signal result of a read request and computation for the value at $x$.}
    \item[] $\mathbf{ret\textrm{-}write_i}(``OK'')$ \\
	\emph{ \ \ signal completion of a write request and computation. }
    \end{itemize}
  \end{itemize}
\item 
$\delta$:
  \begin{itemize}
  \item[] $\mathbf{req\textrm{-}read_i}(x)$ \\
Can occur anytime\\
if $\ms{req_i} = \ms{null}$ then \\
  $\ms{\;\;\;\;req_i} := ``read''$ \\
  $\ms{\;\;\;\;reqaddr_i} := x$ 

  \item[] $\mathbf{req\textrm{-}write_i}(x, v)$ \\
Can occur anytime\\
if $\ms{req_i} = \ms{null}$ then \\
  $\ms{\;\;\;\;req_i} := ``write''$ \\
  $\ms{\;\;\;\;reqaddr_i} := x$  \\
  $\ms{\;\;\;\;reqval_i} := v$ 

  \item[] $\mathbf{ret\textrm{-}read_i}(v)$ \\
Can occur if $\ms{retval_i} \in \ms{values}$ \\
  $\ms{\;\;\;\;req_i} := $\ms{null}$ \\
  $\ms{\;\;\;\;reqaddr_i} := $\ms{null}$ \\
  $\ms{\;\;\;\;reqval_i} := $\ms{null}$ \\
  $\ms{\;\;\;\;retval_i} := $\ms{null}$

  \item[] $\mathbf{ret\textrm{-}write_i}(``OK'')$ \\
Can occur if $\ms{retval_i} = ``OK''$ \\
  $\ms{\;\;\;\;req_i} := $\ms{null}$ \\
  $\ms{\;\;\;\;reqaddr_i} := $\ms{null}$ \\
  $\ms{\;\;\;\;reqval_i} := $\ms{null}$ \\
  $\ms{\;\;\;\;retval_i} := $\ms{null}$

  \item[] $\mathbf{comp\textrm{-}read_i}(x)$ \\
Can occur if $\ms{req_i} = ``read''$, $\ms{reqaddr_i} = x$,
$\ms{cache_i}(x) \neq \ms{null}$, and $\ms{retval_i} = \ms{null}$ \\
  $\ms{\;\;\;\;retval_i} := \ms{cache_i}(x)$

  \item[] $\mathbf{comp\textrm{-}write_i}(x, v)$ \\
Can occur if $\ms{req_i} = ``write''$, $\ms{reqaddr_i} = x$,
$\ms{reqval_i}(x) = v$, and $\ms{retval_i} = \ms{null}$ \\
  $\ms{\;\;\;\;memory}(x) := v$ \\
  $\ms{\;\;\;\;retval_i} := ``OK''$ \\
  $\ms{\;\;\;\;cache_1}(x) := \ms{null}$ \\ 
  $\ms{\;\;\;\;cache_2}(x) := \ms{null}$ 

  \item[] $\mathbf{copy_i}(x)$ \\
Can occur anytime \\
  $\ms{\;\;\;\;cache_i}(x) := \ms{memory}(x)$ 

  \item[] $\mathbf{drop_i}(x)$ \\
Can occur anytime \\
  $\ms{\;\;\;\;cache_i}(x) := \ms{null}$ 

  \end{itemize}

\end{itemize}

%}  
\end{small}

%%%%%%%%%%%%%%%%%%%%%%%% end SC



Also consider a simple Centralized Memory system as a labeled state machine:

%%%%%%%%%%%%%%%%%%%%%%%% begin CM

\textbf{Centralized memory system} 

%\small{
\begin{small}

\emph{
The system is composed of a main memory store that is accessed by two 'clients'.
Each client accesses the memory directly.
} \hfill \\

State machine: 

  \begin{itemize}
\item
$Q$: 
For every $x \in addresses$:
  \begin{itemize}
  \item $\ms{memory(x)}$, \ an element of $data$ 
  \end{itemize}
And a number of doubled structures (one for each client):
  \begin{itemize}
  \item $\ms{req_1}$, \ an element of $\{ ``read'', ``write'' \} \cup \{ \ms{null} \}$ 
  \item $\ms{reqaddr_1}$, \ an element of $\ms{addresses} \cup \{ \ms{null} \}$ 
  \ \ (used for both reads and writes)
  \item $\ms{reqval_1}$, \ an element of $\ms{data} \cup \{ \ms{null} \}$ 
  \ \ (used for writes only)
  \item $\ms{ret_1}$, \ an element of $\{ ``OK'', \ms{null} \} \cup \ms{data} $

  \item $\ms{req_2}$, \ an element of $\{ ``read'', ``write'' \} \cup \{ \ms{null} \}$ 
  \item $\ms{reqaddr_2}$, \ an element of $\ms{addresses} \cup \{ \ms{null} \}$ 
  \ \ (used for both reads and writes)
  \item $\ms{reqval_2}$, \ an element of $\ms{data} \cup \{ \ms{null} \}$ 
  \ \ (used for writes only)
  \item $\ms{ret_2}$, \ an element of $\{ ``OK'', \ms{null} \} \cup \ms{data} $
  \end{itemize}

\item 
$Q_0$:
$\ms{memory}$ arbitrary, all other components $\ms{null}$. 
%(Note that $\ms{null}$ is a special symbol, not the empty set $\emptyset$).

\item 
$L$: 
All are for $i \in \{ 1,2 \}$ (each client). Note that, for each label, the italicized text 
is just a description of the intended purpose.
  \begin{itemize}
  \item[] Input labels:
    \begin{itemize}
    \item[] $\mathbf{req\textrm{-}read_i}(x)$, \ \ $x \in \ms{addresses}$ \\
	\emph{ \ \ an input from client $i$ requesting to read the value in address $x$
	 from $\ms{memory}$.}
    \item[] $\mathbf{req\textrm{-}write_i}(x, v)$, \ \ $x \in \ms{addresses}$,
         $v \in \ms{data}$ \\
	\emph{ \ \ a request by client $i$ to write value $v$ in location $x$ in memory. }
    \end{itemize}

  \item[] Internal labels:
    \begin{itemize}
    \item[] $\mathbf{comp\textrm{-}read_i}(x)$, \ \ $x \in \ms{addresses}$ \\
	\emph{ \ \ actually performed the read that was requested and stored the result. }
    \item[] $\mathbf{comp\textrm{-}write_i}(x, v)$, \ \ $x \in \ms{addresses}$,
         $v \in \ms{data}$ \\
	\emph{ \ \ actually performed the write that was requested. }
    \end{itemize}

  \item[] Output labels:
    \begin{itemize}
    \item[] $\mathbf{ret\textrm{-}read_i}(v)$, \ \   $v \in \ms{data}$ \\
	\emph{ \ \ signal result of a read request and computation for the value at $x$.}
    \item[] $\mathbf{ret\textrm{-}write_i}(``OK'')$ \\
	\emph{ \ \ signal completion of a write request and computation. }
    \end{itemize}
  \end{itemize}
\item 
$\delta$:
  \begin{itemize}
  \item[] $\mathbf{req\textrm{-}read_i}(x)$ \\
Can occur anytime\\
if $\ms{req_i} = \ms{null}$ then \\
  $\ms{\;\;\;\;req_i} := ``read''$ \\
  $\ms{\;\;\;\;reqaddr_i} := x$ 

  \item[] $\mathbf{req\textrm{-}write_i}(x, v)$ \\
Can occur anytime\\
if $\ms{req_i} = \ms{null}$ then \\
  $\ms{\;\;\;\;req_i} := ``write''$ \\
  $\ms{\;\;\;\;reqaddr_i} := x$  \\
  $\ms{\;\;\;\;reqval_i} := v$ 

  \item[] $\mathbf{ret\textrm{-}read_i}(v)$ \\
Can occur if $\ms{retval_i} \in \ms{values}$ \\
  $\ms{\;\;\;\;req_i} := $\ms{null}$ \\
  $\ms{\;\;\;\;reqaddr_i} := $\ms{null}$ \\
  $\ms{\;\;\;\;reqval_i} := $\ms{null}$ \\
  $\ms{\;\;\;\;retval_i} := $\ms{null}$

  \item[] $\mathbf{ret\textrm{-}write_i}(``OK'')$ \\
Can occur if $\ms{retval_i} = ``OK''$ \\
  $\ms{\;\;\;\;req_i} := $\ms{null}$ \\
  $\ms{\;\;\;\;reqaddr_i} := $\ms{null}$ \\
  $\ms{\;\;\;\;reqval_i} := $\ms{null}$ \\
  $\ms{\;\;\;\;retval_i} := $\ms{null}$

  \item[] $\mathbf{comp\textrm{-}read_i}(x)$ \\
Can occur if $\ms{req_i} = ``read''$, $\ms{reqaddr_i} = x$,
 and $\ms{retval_i} = \ms{null}$ \\
  $\ms{\;\;\;\;retval_i} := \ms{memory}(x)$

  \item[] $\mathbf{comp\textrm{-}write_i}(x, v)$ \\
Can occur if $\ms{req_i} = ``write''$, $\ms{reqaddr_i} = x$,
$\ms{reqval_i}(x) = v$, and $\ms{retval_i} = \ms{null}$ \\
  $\ms{\;\;\;\;memory}(x) := v$ \\
  $\ms{\;\;\;\;retval_i} := ``OK''$

  \end{itemize}

\end{itemize}

%}  
\end{small}

%%%%%%%%%%%%%%%%%%%%%%%% end CM

\problempart

Try to prove, as carefully as you can, that the strong caching system
labeled state machine 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.
%% I am not sure that this is strictly true, although I am probably wrong.
%% It would seem that by induction you can show it true for an infinite 
%% number of finite executions, since each stage in the induction is
%% clearly dealing with a finite execution (by trivial induction).
%%
%% It would be similar to showing the problem of all nodes being numbered
%% as the average of their neighbors for a more limited case of graphs
%% isomorphic to a line. You can define the graph structurally, even, and show
%% that any such graph must have all nodes of the same weight. However,
%% this is clearly not true for a line of infinite extent.
%%
%% Perhaps the structural nature saves you in this case.

%Prove by induction that the trace of the $n^{th}$ 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}
  
  \bigskip
  \textbf{TA note:} \\

Try to show them the Abstraction Theorem and show how the
proof could be made very systematic using this theorem.

Give them direction here, depending on what the individual sections and
groups need. They should explore the abstraction issues. Interrupt them once 
or twice to have them present their ideas so far, so that no group gets too 
lost.

You may want to draw pictures of the two systems at the start, and make sure 
that everyone knows what the problem is.

Later, stop them at some point and make sure that they all understand the technique
of showing that every trace of SC can be produced by some execution of CM that will
leave the two states related by some (trivial) abstraction function.

Valid traces, with data as letters and addresses as integers:

\begin{small}
\begin{small}
$q_0$ = all memory set to `a'.
\begin{enumerate}
\vspace{-6pt}\item $req\textrm{-}write_1(7, `f')$
\vspace{-6pt}\item $ret\textrm{-}write_1(``OK'')$
\vspace{-6pt}\item $req\textrm{-}read_1(7)$
\vspace{-6pt}\item $ret\textrm{-}read_1(`f')$
\end{enumerate}

$q_0$ = all memory set to `a'.
\begin{enumerate}
\vspace{-6pt}\item $req\textrm{-}write_1(9, `x')$
\vspace{-6pt}\item $req\textrm{-}write_2(9, `y')$
\vspace{-6pt}\item $ret\textrm{-}write_2(``OK'')$
\vspace{-6pt}\item $req\textrm{-}read_2(9)$
\vspace{-6pt}\item $ret\textrm{-}read_2(`y')$
\vspace{-6pt}\item $ret\textrm{-}write_1(``OK'')$
\vspace{-6pt}\item $req\textrm{-}read_1(9)$
\vspace{-6pt}\item $ret\textrm{-}read_1(`x')$
\end{enumerate}

$q_0$ = all memory set to `a'.
\begin{enumerate}
\vspace{-6pt}\item $req\textrm{-}write_1(4, `x')$
\vspace{-6pt}\item $req\textrm{-}write_1(4, `y')$
\vspace{-6pt}\item $req\textrm{-}read_1(4)$
\vspace{-6pt}\item $ret\textrm{-}write_1(``OK'')$
\vspace{-6pt}\item $req\textrm{-}read_1(4)$
\vspace{-6pt}\item $ret\textrm{-}read_2(8)$
\vspace{-6pt}\item $ret\textrm{-}read_1(`x')$
\vspace{-6pt}\item $ret\textrm{-}read_2(`a')$
\end{enumerate}

\end{small}
\end{small}

It is helpful to figure out what sequences of transitions could have created the
above traces, for both SC and CM machines. In other words, where are the hidden
internal labels? For starters, remember that the SC machine would have to do a 
$copy$ to a cache before doing a $comp\textrm{-}read$, while the CM machine could
just do a $comp\textrm{-}read$. 

\bigskip
  \textbf{Solutions and Discussion:} \\

To sketch out the proof, we want to show that any trace of SC is a trace
of CM. In other words, any execution $\alpha$ of SC has a corresponding
execution $\beta$ in CM that produces the same externally visible
(input and output) labels.
\[
trace(\alpha) = trace(\beta)
\]
We can show this by induction on the length of $\alpha$ (the number of 
transitions in that execution). We must first strengthen our hypothesis
to include a relation between the states of SC and CM -- otherwise, we
will not have enough to go on to do the induction. This relation is
the \emph{abstraction relation}. Try the relation that $memory$ in
SC is identical to $memory$ in CM.

So, take $P(n)$: For any execution $\alpha$ of SC of length $n$, there
is an execution $\beta$ of CM that has the same trace and ends with 
all components except $cache_1, cache_2$ in SC identical to those in CM.

$P(0)$: simple. Start out with the memory equal. No transitions means
no labels in the trace, a feat easily duplicated by CM.

$P(n) \Rightarrow P(n+1)$: Take an arbitrary execution
\begin{eqnarray*}
\alpha & = & \alpha_1, \alpha_2, \ldots, \alpha_n \; , \; \alpha_{n+1}
\end{eqnarray*}
$\alpha_1$ through $\alpha_n$ form an execution of SC of length $n$. By 
the inductive hypothesis, this execution has a corresponding execution of
CM $\beta$ of some length that has the same trace as $\alpha$ and leaves 
the memories identical:
\begin{eqnarray*}
\beta & = & \beta_1, \beta_2, \ldots, \beta_m \; , \; ?
\end{eqnarray*}
All we have to show now is that for every possible transition 
$\alpha_n \rightarrow \alpha_{n+1}$ that SC can make, there is a 
corresponding sequence of transitions of CM 
$\beta_m+1 \rightarrow \beta_m+2 \rightarrow \ldots \beta_k$
that exhibits the same partial trace as the $\alpha_n \rightarrow \alpha_{n+1}$
transition and leaves the memory of CM in the same state as the memory of 
SC at $\alpha_{n+1}$.


\medskip

The possible transitions of SC are:

  \begin{itemize}
  \item $\mathbf{req\textrm{-}read_i}(x)$ 
  
	The corresponding transition for CM is also a $req\textrm{-}read_i$.
	The same input label is added to the trace, and all state elements
	are updated identically.
  \item $\mathbf{req\textrm{-}write_i}(x, v)$ 
  
	The corresponding transition for CM is also a $req\textrm{-}write_i$.
	The same input label is added to the trace, and all state elements
	are updated identically.
  \item $\mathbf{ret\textrm{-}read_i}(v)$ 
  
	The corresponding transition for CM is also a $ret\textrm{-}read_i$.
	The same output label is added to the trace, and all state elements
	are updated identically.
  \item $\mathbf{ret\textrm{-}write_i}(``OK'')$ 
  
	The corresponding transition for CM is also a $ret\textrm{-}write_i$.
	The same output label is added to the trace, and all state elements
	are updated identically.
  \item $\mathbf{comp\textrm{-}read_i}(x)$ 
  
	The corresponding transition for CM is also a $comp\textrm{-}read_i$.
	No labels are added to the trace in either case. SC reads from a cache,
	CM reads from memory. As shown in lecture, in a strong caching system
	the memory will contain the same value as the cache for non-null entries.
  \item $\mathbf{comp\textrm{-}write_i}(x, v)$ 
  
	The corresponding transition for CM is also a $comp\textrm{-}read_i$.
	No labels are added to the trace in either case. SC dumps the caches,
	but they are not reflected in our predicate (the abstraction relation
	part of it).
  \item $\mathbf{copy_i}(x)$ 
  
	The corresponding transition for CM is to perform no transition at all.
	Our predicate remains satisfied.
  \item $\mathbf{drop_i}(x)$ 
  
	The corresponding transition for CM is to perform no transition at all.
	Our predicate remains satisfied.
  \end{itemize}
  

As an aside, the \emph{Abstraction Theorem} makes this proof a little clearer. The
application is analogous to using the Termination Theorem to show that
a state machine always has finite-length executions: it allows you to
skip the induction `wrapper' because it is a general property of these
problems.

\textbf{Abstraction Relation:} \\
A relation $R$ from states of $A$ to states of $B$ is called an {\emph
abstraction relation} from $A$ to $B$ provided that the following
conditions hold:
\begin{enumerate}
\item (Start condition) \\
If $q_A$ is a start state of $A$, then there exists
a start state $q_B$ of $B$ such that $(q_A,q_B) \in R$.
\item (Step condition) \\
If $q_A$ and $q_B$ are reachable states of $A$ and $B$, respectively,
$(q_A,q_B) \in R$, and $(q_A,\ell,q'_A)$ is a step of $A$, 
then there is a sequence of ($0$ or more) steps of $B$ that: \\
-- starts with $q_B$, \\
-- has the same trace as the step of $A$, and \\
-- ends with some state $q'_B$ such that $(q'_A,q'_B) \in R$.
\end{enumerate}


\textbf{Abstraction Theorem:} \\
If there is an abstraction relation from $A$ to $B$, then $A$
implements $B$. \\


  \end{solution}
  }





\end{problems}

\end{document}

\endinput


\end{document}

\endinput
