\documentclass[11pt, twoside]{article}
 
\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}

%\newcommand{\nand}{|}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

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

\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}
%
  \newcommand{\handoutlabel}{sol5}
  \newcommand{\handouttitle}{Problem Set 5 Solutions}
  \newcommand{\handoutdate}{March ??, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else 
  \typeout{}
  \typeout{Solutions *NOT INCLUDED*.} 
  \newcommand{\reading}[1]{%
    \mbox{}\\ \hrule\mbox{} \\ \bigskip %
    #1%
    \mbox{} \\ \bigskip \hrule \vfill\mbox{}\newpage}
  \newcommand{\omitsolution}[1]{}
%
  \newcommand{\handoutlabel}{ps5}
  \newcommand{\handouttitle}{Problem Set 5}
  \newcommand{\handoutdate}{March ??, 2000}
  \newcommand{\duedate}{???}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}
    \centerline{{\bf Due  Date: \duedate.}}
    \vspace*{\baselineskip}}
%
\fi

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

\begin{document}

\titlebar

\reading{%
\begin{description}\itemsep 0\baselineskip
\item[Self-study:] \mbox{} \\
Rosen, Section 2.6, on Matrices.

Self-study problems: 
Section 2,6, problems 3, 5, 11, 13, 15, 19, 23, 29, 30, 31

\item[Reading:] \mbox{} \\[-\baselineskip]
%  
\begin{itemize}\itemsep 0\baselineskip
\item Notes on Computational Processes, Installment 3.
\item [[[Robert: Ask David what they should read for his part of the
lecture material this week.]]]
\end{itemize}

\end{description}
}

\textbf{Problems:}

\vspace*{0.5\baselineskip}

\begin{problems}

\problem
% Using a sequence to implement a set.

The following labeled state machine $\ms{DSet}$ models a ``dynamic set'' of
integers.
The set starts out empty.
A client can modify the set by means of operations $\ms{add}(x)$,
which adds integer $x$ to the set, 
and $\ms{remove}(x)$, which removes integer $x$ from the set.
A client can also ask whether a particular integer $x$ is in the set,
using operation $\ms{isin}(x)$.

Formally, $\ms{DSet}$ can be defined as follows: 

$Q$: 
The states consist of components: 
$\ms{set}$, a set of integers 
$\ms{reqtype} \in \{ ``add'', ``remove'', ``isin'' \} \cup \{ \ms{null} \}$ 
$\ms{element} \in Z \cup \{ \ms{null} \}$ 
$\ms{retval} \in \{ ``OK'', \ms{null} \} \cup Boolean$

$Q_0$:
Initially, $\ms{set} = \emptyset$, and all the other components are
$\ms{null}$.

$L$:
Input labels:
$\ms{request-add}(x)$, $x \in Z$
$\ms{request-remove}(x)$, $x \in Z$
$\ms{request-isin}(x)$, $x \in Z$

Internal labels:
$\ms{compute-add}(x)$, $x \in Z$
$\ms{compute-remove}(x)$, $x \in Z$
$\ms{compute-isin}(x)$, $x \in Z$

Output labels:
$\ms{return}(``OK'')$
$\ms{return}(b)$, $b \in Boolean$

Transitions:

$\ms{request-add}(x)$
if $\ms{reqtype} = \ms{null}$ then
  $\ms{reqtype} := ``add''$
  $\ms{element} := x$

$\ms{request-remove}(x)$
if $\ms{reqtype} = \ms{null}$ then
  $\ms{reqtype} := ``remove''$
  $\ms{element} := x$

$\ms{request-isin}(x)$
if $\ms{reqtype} = \ms{null}$ then
  $\ms{reqtype} := ``isin''$
  $\ms{element} := x$

$\ms{compute-add}(x)$
Can occur if $\ms{reqtype} = ``add''$, $\ms{element} = x$, and
$\ms{retval} = \ms{null}$
Effect: 
$\ms{set} := \ms{set} \cup \{ x \}$
$\ms{retval} := ``OK''$

$\ms{compute-remove}(x)$
Can occur if $\ms{reqtype} = ``remove''$, $\ms{element} = x$, and
$\ms{retval} = \ms{null}$
Effect: 
$\ms{set} := \ms{set} - \{ x \}$
$\ms{retval} := ``OK''$

$\ms{compute-isin}(x)$
Can occur if $\ms{reqtype} = ``isin''$, $\ms{element} = x$, and
$\ms{retval} = \ms{null}$
Effect: 
if $x \in \ms{set}$ then $\ms{retval} := \ms{true}$ 
else $\ms{retval} := \ms{false}$

$\ms{return}(``OK'')$
Can occur if $\ms{retval} = ``OK''$
Effect:
$\ms{reqtype}, \ms{element}, \ms{retval} := \ms{null}$

$\ms{return}(b)$, $b \in Boolean$
Can occur if $\ms{retval} = b$
Effect:
$\ms{reqtype}, \ms{element}, \ms{retval} := \ms{null}$

[[[Robert:  Lots of formatting work needed]]]

\ppart
Which of the following are traces of $\ms{DSet}$?

[[[Robert: List a few candidates---short sequences of request and return
actions that are and are not traces.]]]

\ppart
One way to implement $\ms{DSet}$ is to represent the set by a finite
sequence of integers.
The $\ms{add}$ operation appends the new element to the end of the
sequence if and only if the element is not already in the sequence. 
The $\ms{remove}$ operation removes the element from the sequence if
it there. 
The $\ms{isin}$ operation returns the answer to whether or not the
element is in the sequence. 

Define a state machine $\ms{Seq}$ corresponding to this
implementation.
In implementing the operations, you should not try to represent
individual search steps that try to locate an element in the sequence.
Instead, let each operation perform its main computation in one
large-granularity step, which involve the entire sequence all at once.

[[[Robert:  Improve the explanation?]]]

\ppart
Prove that your $\ms{Seq}$ state machine implements
the $\ms{DSet}$ labeled state state machine,
that is, that any trace of $\ms{Seq}$ is a trace of $\ms{DSet}$. 

[[[Robert:  This can be done by an informally-described construction,
starting from an execution of $\ms{Seq}$ and saying how to construct
the corresponding execution of the abstract object.  
The fact that the implementation's steps do the whole operation at
once should make this easier than if we had them describe the
individual steps.

The proof consists of the construction (justifying if necessary why
the construction is possible), plus an argument of some kind saying
that the traces correspond. 

It is also possible to solve this using the formally-stated
Abstraction Theorem.  So, it's probably a good idea to include this
kind of proof too.
The relation $R$ just says that $\ms{DSet}.\ms{set}$ is equal to the
set of elements in the sequence maintained in $\ms{Seq}$.
Plus the obvious sort of correspondence between bookkeeping
components.
]]]

\ppart
$\ms{DSet}$ can be implemented using a sequence of integers in another
way. 
The $\ms{add}$ operation could append the new element to the end of
the sequence {\em whether or not it already appears in the
sequence\/}.
The $\ms{remove}$ and $\ms{isin}$ operations then have to be modified
to accommodate this new behavior on the part of $\ms{add}$.

Define a state machine $\ms{Seq1}$ corresponding to this
implementation.
If you like, you can just describe the differences between $\ms{Seq1}$
and your $\ms{Seq}$. 

\ppart
Prove that any trace of $\ms{Seq1}$ is a trace of $\ms{DSet}$. 

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

[[[The following is the previous problem.  It's pretty much the same
idea, but the students have to write the abstract state machine too.
Shishir started to write out a solution.
The style might or might not be the same as what I've been using.]]]

\problem
% Using a sequence of pairs to implement a polynomial.

Consider an abstract ``dynamic polynomial'', with one variable, $x$,
and integer coefficients. 
The polynomial starts out being just the $0$ polynomial. 
A client can perform the following operations: 
\begin{itemize}
\item $\ms{add-term}(c,e)$, which is supposed to add the term $c x^e$ to the
maintained polynomial.
\item $\ms{coeff}(e)$, which asks for the coefficient of the $x^e$ term.
\end{itemize}

\begin{problemparts}

\problempart
Model this object by a labeled state machine $\ms{ADP}$.
The state should keep track of the polynomial as an abstract
polynomial; don't represent it using lower-level
mathematical objects like numbers, matrices, sequences, etc.
The state will also need some bookkeeping information to keep track of
operations in progress.
The labels should include inputs reflecting the requests and outputs
reflecting the responses.
Your machine should ignore requests that arrive while an operation is active.

[[[I did not go over the solution.  In fact, I have to stop here, for
now.]]]

\omitsolution{
\begin{solution}
\begin{description}
\item[$Q$: ] 
\\
$ p \in \{polynomials\} $ \\
$ current\_op \in \{ (type, args, retval) ~|~  $  
\\
\hspace*{1in}
\(
\begin{array}{lll}
type \in \{``add-term'', ``coeff''\} \cup \{null\}, \\
args \in (\integers \times \naturals) \cup \naturals \cup \{null\}, \\
retval \in ``OK'' \cup \integers\} \cup \{null\}   \\
\} \\
\end{array}
\)

\item[$Q_0$: ] 
\\
$p := 0$ 
\\
$current\_op := (null, null, null);$

\item[$\delta$: ] 

    \begin{description}
    \item[1. add-term(c,e): ]

        \begin{description}
        \item 
        \item $if~current\_op.type = null~then$
            \begin{description}
            %\item 
            \item $current\_op := (``add-term'', (c, e), null)$ 
            \item $p := p + c x^e$ 
            \item $current\_op := (null, null, ``OK'')$ 
            \end{description}
        \end{description}
    
    \item[2. coeff(e): ]

        \begin{description}
        \item 
        \item $if~current\_op.type = null~then$
            \begin{description}
            %\item 
            \item $current\_op := (``coeff'', c, null)$ 
            \item $current\_op := (null, null, coefficient~of~x^e~in~p )$ 
            \end{description}
        \end{description}
    \end{description}
\end{description}
\end{solution}
}

\problempart
List some (4-5) traces that are exhibited by your state machine $DP$.
Include at least one that involves a request arriving when it is not
supposed to.

\omitsolution{
\begin{solution}
\\
Start with $Q_0$:

\[
\begin{array}{lll}
add-term(1,1) & \longrightarrow & return (``OK'')  \\
add-term(2,2) & \longrightarrow & return (``OK'')  \\
coeff(2)      & \longrightarrow & return (2)  \\
add-term(2,1) & \longrightarrow & return (``OK'')  \\
coeff(1)      & \longrightarrow & return (3)  \\
\end{array}
\]

Start with $Q_0$:

\[
\begin{array}{lllllll}
add-term(1,1) & \longrightarrow & return (``OK'')  \\
add-term(2,2) & \longrightarrow & coeff(2)        & \longrightarrow & return(``OK'') \\
coeff(2)      & \longrightarrow & add-term(3,2)   & \longrightarrow & return(2) \\
coeff(2)      & \longrightarrow & return(2) \\
\end{array}
\]

\end{solution}
}

\problempart
Describe in words two different implementations of your $DP$.
These implementations should have, in their state, lower-level
mathematical objects like numbers, matrices, sequences, etc.

\omitsolution{
\begin{solution}
\item[Using Arrays: ] Keep an array such that the $i$th entry holds the coefficient 
of $x^i$ in $p$
\item[Using Ordered Pairs: ] Keep a set of ordered pairs $(i, c)$ mapping the $i$th entry 
to the coefficient of $x^i$ in $p$
\end{solution}
}

\problempart
Formalize one of your implementations as a labeled state machine $Imp$.
It should have the same external labels as your $ADP$ labeled state machine.

\omitsolution{
\begin{solution}

Using arrays, our state is the same except that instead of the polynomial $p$ we have the array 
$poly-array$. Also, our start state is to have $poly-array$ be filled with zeros.

Our operations become:
\begin{description}
\item[add-term(c,e): ] $poly-array[e] := poly-array[e] + c$
\item[coeff(e): ] $return poly-array[e]$
\end{description}

\end{solution}
}

\problempart
Argue that your implementation $Imp$ is correct, in the sense that every trace
of $Imp$ is also a trace of $ADP$.

\omitsolution{
\begin{solution}



\end{solution}
}

\end{problemparts}


\end{problems}
\end{document}
