\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 7, 2000}
  \newcommand{\duedate}{March 14, 2000}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}
    \centerline{{\bf Due  Date: \duedate.}}
    \vspace*{\baselineskip}}
%
%%\fi

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

\begin{document}


\titlebar

\reading{%
\mbox{} \\
\mbox{}\vspace*{-3\baselineskip}

\begin{description}\itemsep 0\baselineskip
\item[Self-study:] \mbox{} \\
Please review Rosen Section 2.6, on matrices.

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

\item[Reading:] \mbox{} \\[-\baselineskip]
\vspace*{-0.5\baselineskip}
\begin{description}\itemsep 0\baselineskip
\item[Notes on Computational Processes:] \mbox{} \\ %
  Installment 3
\item[Rosen, \textit{Discrete Mathematics and Its Applications}:] \mbox{} \\ %
  Sequences and Summations: Section 1.7;
%  Generating Functions: Section 5.4;
%%%% Should that be included??
\item[6.042 Fall 97 Lecture notes (available from course page):] \mbox{} \\ %
  Lecture 8
\end{description}
%
%\begin{itemize}\itemsep 0\baselineskip
%\item Notes on Computational Processes, Installment 3.
%\item Rosen, \textit{Discrete Mathematics and Its Applications}: \mbox{} \\ %
%  Sequences and Summations: Section 1.7;
%  Generating Functions: Section 5.4;
%%%% Should that be included??
%\item 6.042 Fall 97 Lecture notes (available from course page):
%  Lecture 8
%\end{itemize}

\end{description}
}

\section*{Problems:}

\begin{problems}

%%%%%%%%%%%%%%%%%%%
%%% Problem 1

\problem 

Suppose you were about to enter college today and a college loan
officer offered you the following deal: \$25,000 at the start of each
year for four years to pay for your college tuition and an option of
choosing one of the following repayment plans:

\begin{description}\itemsep 0\baselineskip
\item[Plan A:] Wait four years, then repay \$$20,000$ at the start of
  each year for the next ten years.
\item[Plan B:] Wait five years, then repay \$$30,000$ at the start of
  each year for the next five years.
\end{description}

Suppose the annual interest rate is currently 7\% and does not change
in the future.  

\begin{itemize}\itemsep 0\baselineskip
\item[a)] Which repayment plan would you choose?
\item[b)] What is the loan officer's effective profit (in today's
  dollars) on the loan?
\end{itemize}

%%%%%%%%%%%%%%%%%%%
%%% Problem 2

\problem
Consider the following summation:
\[\sum_{k=2}^n {\frac{1}{k(k-1)}}\] 

\begin{problemparts}
\problempart
Find a closed form solution for this summation.

\hint Try using partial fractions to break $\frac{1}{k(k-1)}$
into a difference of two terms.

\problempart Use induction to verify your closed form solution (i.e.,
prove that it is correct).

\end{problemparts}


%%%%%%%%%%%%%%%%%%%
%%% Problem 3

\problem Find closed-form expressions for the following sums:

\mbox{}

\begin{problemparts}

\problempart
\vspace{-2\baselineskip}
\[
\sum_{k=0}^n \frac{8^k - 5^k}{9^k}
\]


\problempart
\vspace{-2\baselineskip}
\[
\sum_{i=1}^n \sum_{j=0}^{\infty} i^{7/16} \cdot \left(1 - \frac{1}{4 i^{9/16}}\right)^j
\]

\end{problemparts}

%%%%%%%%%%%%%%%%%%%
%%% Problem 4

\problem

\textit{Note: This problem is only worth one point.  Give it some
  thought but don't exhaust yourself on it.}

Consider the sum of the following sequence:
\[1 - 1 + \frac{1}{2} - \frac{1}{2} + \frac{1}{3} - \frac{1}{3}
 + \frac{1}{4} - \frac{1}{4} + \frac{1}{5} - \frac{1}{5} + \ldots \]

To sum it, suppose we rearrange the terms and write it as:
\begin{eqnarray*}
 & (1 + \frac{1}{2} - 1) & +  \\
 & (\frac{1}{3} + \frac{1}{4} - \frac{1}{2}) & +  \\
 & (\frac{1}{5} + \frac{1}{6} - \frac{1}{3}) & +  \\
 & (\frac{1}{7} + \frac{1}{8} - \frac{1}{4}) & +  \\
 & \ldots & 
\end{eqnarray*}

which we can write as a summation as:
\[%
a = \sum_{n=1}^{\infty} \left( \frac{1}{2n-1} + \frac{1}{2n} - \frac{1}{n} \right) %
  = \sum_{n=1}^{\infty} \frac{1}{2n(2n-1)} %
\]

On the other hand, we arrange the original summation as
\begin{eqnarray*}
 & (1 - 1 - \frac{1}{2}) & +  \\
 & (\frac{1}{2} - \frac{1}{3} - \frac{1}{4}) & +  \\
 & (\frac{1}{3} - \frac{1}{5} - \frac{1}{6}) & +  \\
 & (\frac{1}{4} - \frac{1}{7} - \frac{1}{8}) & +  \\
 & \ldots &
\end{eqnarray*}
\[%
b = \sum_{n=1}^{\infty} \left( \frac{1}{n} - \frac{1}{2n-1} - \frac{1}{2n} \right) %
  = \sum_{n=1}^{\infty} \frac{-1}{2n(2n-1)} %
  = - a
\]

How is this possible?  Choose the correct response from the options
below. Be prepared to back up your answer.

%\begin{problemparts}
%\problempart
%I find the above somewhat disturbing, but I can't resolve it.
%\problempart
%Don't toy with me. Your petty tricks are no match for my superior mathematical skills.
%\problempart
%It's 4 am tuesday morning. I'm not even coherent enough to be disturbed.
%\end{problemparts}

\begin{itemize}
\item[\textbf{a)}] \ I find the above somewhat disturbing, but I can't
resolve it.
\item[\textbf{b)}] \ Don't toy with me. Your petty tricks are no match 
for my superior mathematical skills.
\item[\textbf{c)}] \ It's 4am Tuesday morning. I'm not even coherent enough
to be disturbed.
\end{itemize}


%%%%%%%%%%%%%%%%%%%
%%% Problem 5

\clearpage

\problem 
% Using a sequence to implement a set.

The following labeled state machine $\ms{DSet}$ models a ``dynamic set'' of
integers. (Remember that a set, unlike a multiset, can only contain
one element of any particular object).
The set starts out empty.

A client can modify or inspect the set by means of the following
operations:
\begin{itemize}\itemsep 0\baselineskip
\item $\mathbf{add}(x)$, \ which adds an integer $x$ to the set.
\item $\mathbf{remove}(x)$, \ which removes integer $x$ from the set.
\item $\mathbf{isin}(x)$, \ which tells if the element $x$ is in the set.
\end{itemize}

Formally, $\ms{DSet}$ can be defined as a collection of the following components: 

\begin{itemize}
\item 
$Q$: 
The states consist of the components: 
  \begin{itemize}
  \item $\ms{set}$, \ a set of integers 
  \item $\ms{reqtype} \in \{ ``add", ``remove", ``isin" \} \cup \{ \ms{null} \}$ 
  \item $\ms{element} \in \ints \cup \{ \ms{null} \}$ 
  \item $\ms{retval} \in \{ ``OK", \ms{null} \} \cup \ms{Boolean} $
  \end{itemize}
  
\item 
$Q_0$:
Initially, $\ms{set} = \emptyset$, and all the other components are
$\ms{null}$. (Note that $\ms{null}$ is a special symbol, not the 
empty set $\emptyset$).

\item 
$L$:
  \begin{itemize}
  \item[] Input labels:
    \begin{itemize}
    \item[] $\mathbf{request\textrm{-}add}(x)$, \ \ $x \in \ints$
    \item[] $\mathbf{request\textrm{-}remove}(x)$, \ \ $x \in \ints$
    \item[] $\mathbf{request\textrm{-}isin}(x)$, \ \ $x \in \ints$
    \end{itemize}

  \item[] Internal labels:
    \begin{itemize}
    \item[] $\mathbf{compute\textrm{-}add}(x)$, \ \ $x \in \ints$
    \item[] $\mathbf{compute\textrm{-}remove}(x)$, \ \ $x \in \ints$
    \item[] $\mathbf{compute\textrm{-}isin}(x)$, \ \ $x \in \ints$
    \end{itemize}

  \item[] Output labels:
    \begin{itemize}
    \item[] $\mathbf{return}(``OK")$
    \item[] $\mathbf{return}(b)$, \ \ $b \in Boolean$
    \end{itemize}
  
  \end{itemize}

\item 
Transitions ($\delta$):
  \begin{itemize}
  \item[] $\mathbf{request\textrm{-}add}(x)$ \\
if $\ms{reqtype} = \ms{null}$ then \\
  $\ms{\;\;\;\;reqtype} := ``add"$ \\
  $\ms{\;\;\;\;element} := x$ 

  \item[] $\mathbf{request\textrm{-}remove}(x)$ \\
if $\ms{reqtype} = \ms{null}$ then \\
  $\ms{\;\;\;\;reqtype} := ``remove"$ \\
  $\ms{\;\;\;\;element} := x$ 

  \item[] $\mathbf{request\textrm{-}isin}(x)$ \\
if $\ms{reqtype} = \ms{null}$ then \\ 
  $\ms{\;\;\;\;reqtype} := ``isin"$ \\
  $\ms{\;\;\;\;element} := x$ 

  \item[] $\mathbf{compute\textrm{-}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"$ 

  \item[] $\mathbf{compute\textrm{-}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"$ 

  \item[] $\mathbf{compute\textrm{-}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}$

  \item[] $\mathbf{return}(``OK")$ \\
Can occur if $\ms{retval} = ``OK"$ \\
%Effect: \\
$\ms{\;\;\;\;reqtype}, \ms{element}, \ms{retval} := \ms{null}$ 

  \item[] $\mathbf{return}(b)$, $b \in Boolean$ \\
Can occur if $\ms{retval} = b$ \\
%Effect: \\
$\ms{\;\;\;\;reqtype}, \ms{element}, \ms{retval} := \ms{null}$ 

  \end{itemize}

\end{itemize}
 
\begin{problemparts}

\problempart

Which of the following are valid traces of $\ms{DSet}$? For any
incorrect ones, indicate what is wrong.

%% add in candidates instead. !!!

\begin{enumerate}
\item Start with the sole element of $Q_0$.
        \begin{itemize}
        \item $\mathbf{request\textrm{-}add}(7)$
        \item $\mathbf{return}(``OK")$
        \item $\mathbf{request\textrm{-}isin}(7)$
        \item $\mathbf{return}(\ms{true})$
        \item $\mathbf{request\textrm{-}remove}(7)$
        \item $\mathbf{return}(``OK")$
        \item $\mathbf{request\textrm{-}remove}(7)$
        \item $\mathbf{return}(``OK")$
        \end{itemize}

\item Start with the sole element of $Q_0$.
        \begin{itemize}
        \item $\mathbf{request\textrm{-}add}(7)$
        \item $\mathbf{return}(``OK")$
        \item $\mathbf{request\textrm{-}remove}(4)$
        \item $\mathbf{return}(\ms{false})$
        \item $\mathbf{request\textrm{-}add}(7)$
        \item $\mathbf{return}(``OK")$
        \end{itemize}

\item Start with the sole element of $Q_0$.
        \begin{itemize}
        \item $\mathbf{request\textrm{-}add}(4)$
        \item $\mathbf{request\textrm{-}add}(6)$
        \item $\mathbf{return}(``OK")$
        \item $\mathbf{request\textrm{-}isin}(6)$
        \item $\mathbf{request\textrm{-}isin}(4)$
        \item $\mathbf{return}(\ms{true})$
        \end{itemize}

\item Start with the sole element of $Q_0$.
        \begin{itemize}
        \item $\mathbf{request\textrm{-}add}(3)$
        \item $\mathbf{request\textrm{-}remove}(3)$
        \item $\mathbf{return}(``OK")$
        \item $\mathbf{request\textrm{-}isin}(3)$
        \item $\mathbf{return}(\ms{false})$
        \item $\mathbf{request\textrm{-}remove}(1)$
        \item $\mathbf{return}(``OK")$
        \end{itemize}

\end{enumerate}

\problempart

\textbf{High-level implementation:}

One way to implement $\ms{DSet}$ is to represent the set by a finite
sequence of integers.  The $\mathbf{add}$ operation could append the new
element to the end of the sequence {\em whether or not it already
  appears in the sequence\/}.  The $\mathbf{isin}$ operation returns the
answer to whether or not any copy of the element is in the sequence.
The $\mathbf{remove}$ operation removes the element from the sequence at
every place that it occurs.

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 involves the entire sequence. Thus,
this description will still be rather abstract.


\problempart

Prove that your $\ms{Seq}$ state machine implements the $\ms{DSet}$
labeled state machine; that is, prove that any trace of $\ms{Seq}$ is
a trace of $\ms{DSet}$. Remember that a trace is a listing of only the
input and output labels during an execution~---~the externally visible
behavior. You may use the Abstraction Theorem.

\problempart

\textbf{Low-level implementation:}

Give an implementation called $\ms{SeqLow}$ that relies on lower-level
operations for performing the searches and removals (operate at the
element-level).


\problempart

Give an informal argument that $\ms{SeqLow}$ implements $\ms{Seq}$.

\end{problemparts}


%%%%%%%%%%%%%%%%%%%
%%% Problem 6

\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 $\mathbf{add\textrm{-}term}(c,e)$, which adds the term $c x^e$
  to the maintained polynomial.
\item $\mathbf{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 (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.

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

  \problempart Describe in words an implementation of your state
  machine $\ms{ADP}$.  The state of this implementation should involve
  lower-level mathematical objects like numbers, matrices, sequences,
  etc.

  \problempart Formalize your implementation as a labeled state
  machine $\ms{Imp}$.  It should have the same external labels as your
  labeled state machine $\ms{ADP}$.

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

\end{problemparts}


%%%%%%%%%%%%%%%%%%%
%%% Problem 7

\problem Attached to this problem set are some students' solutions
from a previous problem set.  Mark up these solutions, indicating
things that are incorrect or unclear, and if possible show how the
solution can be made completely correct and clear.  Please refer to
the 6.042 course webpage for more readable versions of the students'
solutions.

\clearpage%
\problempart Problem Set 4, Problem 1

\centerline{\resizebox{\textwidth}{!}{\includegraphics{figures/ps5student2.ps}}}

\clearpage%
\problempart Problem Set 4, Problem 2

\centerline{\resizebox{\textwidth}{!}{\includegraphics{figures/ps5student1.ps}}}

\end{problems}

\end{document}
