\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{} \\
Please review Rosen Section 6.4, stopping before Warshall's algorithm.

Self-study problems: Problem 19.

Also consider some additional parts for that problem:
\begin{itemize}
\item (g) $(I \Or R)^2$
\item (h) $(I \Or R)^4$
\item (i) $(I \Or R)^*$
\end{itemize}

\item[Reading:] \mbox{} \\[-\baselineskip]
%  
\begin{itemize}\itemsep 0\baselineskip
\item Notes on Computational Processes, Installments 1, 2 and 3.
\item 6.042 Fall 97 Lecture notes (available from course page):
  Lectures 6 and 7
\end{itemize}

\end{description}
}

\textbf{Problems:}

\vspace*{0.5\baselineskip}

\begin{problems}



\problem
Consider an ``abstract object'' that maintains a dynamic polynomial $\ms{poly}$.
This polynomial has variable $x$, and integer coefficients.
Initially, the polynomial is just the $0$ polynomial (no terms).
The polynomial supports operations:
\begin{itemize}
\item $add-term(c,e)$, which is supposed to add the term $c x^e$ to the
maintained polynomial.
\item $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 $ADP$.
The state should keep track of the polynomial
(a value that is simply a mathematical polynomial---you don't have to
think about how to 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.

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