\documentclass[11pt, twoside]{article}

\def\handouttype{problemset}

\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}{sol4-5}
  \newcommand{\handouttitle}{Problem Set 4.5 Solutions}
  \newcommand{\handoutdate}{March 3, 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}{ps4-5}
  \newcommand{\handouttitle}{Problem Set 4.5}
  \newcommand{\handoutdate}{February 29, 2000}
  \newcommand{\duedate}{NEVER}
  \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 \label{puzzleProblem}
%[[[Pset 4.5]]]

This problem is repeated from last Friday's tutorial, slightly
rewritten.

Math Moose has been given a new puzzle: a $3 \times 3$ grid of
squares, where each square contains one of the
digits in the set $\set{1, 2, 3, 4, 5, 6, 7, 8, 9}$, each digit
appearing exactly once in the puzzle.  Each row can be rotated right
or left and each column can be rotated up or down.  The effects of
such rotations are demonstrated in the following figure.

\begin{figure}[htbp]
  \begin{center}
    \leavevmode

\[
\begin{array}{|c|c|c|}
\hline
2 & 3 & 6 \\ \hline
7 & 8 & 9 \\ \hline
5 & 4 & 1 \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
5 & 3 & 6 \\ \hline
2 & 8 & 9 \\ \hline
7 & 4 & 1 \\ \hline
\end{array}
\rightarrow
\begin{array}{|c|c|c|}
\hline
5 & 3 & 6 \\ \hline
8 & 9 & 2 \\ \hline
7 & 4 & 1 \\ \hline
\end{array}
\]

  \end{center}
  \caption{Examples of puzzle row and column rotations.}
  \label{fig:roteg}
\end{figure}

The first picture shows the initial configuration of the puzzle.  The
leftmost column is then rotated downward to give the middle picture.
The $2$ and $7$ move down and the $5$ rotates back up to the top.
Then, the middle row is rotated leftward to produce the final picture.
The $8$ and $9$ move left and the $2$ rotates back around to the
right.

Since discovering the puzzle, Math Moose has spent hours trying
to obtain the following configuration, starting of course from the
initial configuration of Figure~\ref{fig:roteg} and using legal row
and column rotations.

\[
\begin{array}{|c|c|c|}
\hline
1 & 2 & 3 \\ \hline
4 & 5 & 6 \\ \hline
7 & 8 & 9 \\ \hline
\end{array}
\]

Sad to say, Math Moose has failed miserably.
He is beginning to suspect that the puzzle might be designed in a
way that makes this configuration impossible, no matter what sequence
of row and column rotations one attempts.

\begin{problemparts}

  \problempart Model the puzzle as a state machine.

\omitsolution{%
\begin{solution}

The puzzle can be modeled by the state machine $M$ defined as follows:

\begin{itemize}

\item The set of states $Q$ consists of all arrangements of the digits
  in the set $\set{1, 2, 3, 4, 5, 6, 7, 8, 9}$ on a $3 \times 3$ grid
  where each digit appears exactly once.

\item The set of start states $Q_0$ consists of the single arrangement
  236 789 541.

\item The relation $\delta \subseteq Q \times Q$ consists of all pairs of
  states $(q_1, q_2)$ such that $q_2$ can be obtained from $q_1$ by a
  row or column rotation.

\end{itemize}
  \end{solution}%
  }

\problempart Given the initial configuration of the puzzle indicated
above, namely 236 789 541, prove that Math Moose can never obtain
the configuration 123 456 789.

\omitsolution{%
\begin{solution}

  The idea is to keep track of the number of digit pairs that are out
  of order relative to the desired configuration 123 456 789.  For
  example, in the initial configuration, $2$ appears before $1$; this
  pair of digits is out of order, because $1$ appears before $2$ in
  the desired configuration 123 456 789.  We will refer to an
  out-of-order digit pair as an {\em inversion}.  In the initial
  configuration, there are 17 inversions:

\[
\begin{array}{ccccc}
21 & 31 & 65 & 64 & 61 \\
75 & 74 & 71 & 85 & 84 \\
81 & 95 & 94 & 91 & 54 \\
51 & 41
\end{array}
\]

The key observation is that a rotation always changes the number of
inversions by an even amount.  Since the puzzle initially has an odd
number of inversions, no sequence of rotations can reduce the number
of inversions to 0, an even number.  Consequently, there will always
be at least one pair of digits out of order.

The main challenge is to prove that a rotation always changes the
number of inversions by an even amount.  We will prove this claim in a
sequence of lemmas, and then we will prove the main result as a
theorem.

\begin{lemma}
Swapping an adjacent pair of digits changes the number of inversions
by an odd amount.
\end{lemma}

\begin{proof}
  If the digits were initially in the same order as in 123 456 789,
  then the number of inversions is increased by 1, an odd number.
  Otherwise, the digits were initially in the wrong order, and the
  number of inversions is decreased by 1, also an odd number.
\end{proof}

\begin{lemma}
Swapping any pair of digits changes the number of inversions by an
odd amount.
\end{lemma}

\begin{proof}
  We will show how to swap any pair of digits using an odd number of
  swaps of adjacent digits.  The preceding lemma says that swapping
  adjacent digits changes the number of inversions by an odd amount.
  Therefore, swapping any pair of digits changes the number of
  inversions by an odd amount, because the sum of an odd number of odd
  numbers is odd.

  All that remains is to show how to swap any pair of digits using an
  odd number of swaps of adjacent digits.  Suppose that we are
  swapping digits $x$ and $y$, where $x$ is on the left, $y$ is on the
  right, and there are $k$ stray digits between the two.  First, we
  swap $x$ with its right neighbor $k$ times.  This leaves $x$
  directly left of $y$ and leaves all the stray digits shifted one
  place to the left.  Then we swap $x$ and $y$, putting $x$ into $y$'s
  original positions.  Finally, we swap $y$ with its left neighbor $k$
  times.  This puts $y$ into $x$'s original position and shifts the
  stray digits back to their original position.  The total number of
  swaps of adjacent digits is $k + 1 + k = 2k + 1$, which is odd for
  all $k \geq 0$.
\end{proof}

\begin{lemma}\label{lem:rotate}
  Rotating any row or column changes the number of inversions by an
  even amount.
\end{lemma}

\begin{proof}
  We show below that any row or column rotation can be obtained by two
  swaps.  The preceding lemma says that every swap changes the number
  of inversions by an even amount.  Since the sum of two odd numbers
  is even, any row or column rotation changes the number of inversions
  by an even amount.

  Here is how to obtain a rotation from two swaps.  Suppose that the
  digit sequence $xyz$ appears in some row or column.  Swapping $x$
  with $y$ and then swapping $x$ with $z$ creates the sequence $yzx$,
  which corresponds to a leftward or upward rotation.  Swapping $z$
  with $y$ and then $z$ with $x$ creates the sequence $zxy$.  This
  corresponds to a rightward or downward rotation.
\end{proof}

Now define $P(q)$ to be the predicate saying that, in state $q$ of $M$,
the number of inversions in the digit sequence relative to the 123 456
789 sequence is odd. 
Let $P'(n)$, for $n \geq 0$, be the predicate that asserts $P$ for all
states that can be reached by $n$-step executions of $M$.  

\begin{theorem}
$P'(n)$ is true for all $n \geq 0$.
\end{theorem}

\begin{proof}
By induction on $n$, the length of the execution. 

  For the base case, we need to show that the property holds in the
  start state, \ie an execution of length $n = 0$.  This is true
  because in the initial configuration, the number of inversions is
  odd, in particular equal to 17.  For the inductive step, we must
  show that if $P$ holds for any configuration reachable after $n$
  steps of $M$, then $P$ holds for any configuration reachable after
  $n+1$ steps of $M$.  Fix $n \geq 0$ and let $q_0, q_1,\ldots, q_n,
  q_{n+1}$ denote any $n+1$-step execution of $M$.  $q_n$ is thus the
  final state of an $n$-step execution of $M$.  Thus, by our inductive
  hypothesis, in the state $q_n$, the puzzle has an odd number of
  inversions.  Now, consider the final step $(q_n,q_{n+1})$ of the
  $n+1$-step execution of $M$.  By Lemma~\ref{lem:rotate}, this step
  changes the number of rotations by an even amount.  It follows that
  the number of rotations of the state $q_{n+1}$ is odd.  Thus, by
  induction, we have shown that $P$ is an invariant property of $M$.
\end{proof}


\begin{corollary}
Math Moose cannot obtain the configuration 123 456 789.
\end{corollary}

\begin{proof}
This has an even number (0) of inversions.
\end{proof}

\end{solution}%
}

\end{problemparts}

%%%%%%%%%%%%%%% PROBLEM %%%%%%%%%%%%%%

\problem 
%[[[Shishir:  This is derived from problem set 4, Handout 21, Spring
%98.  Please fill in the solution.]]]
A robot wanders on a 2-dimensional grid, starting at the origin,
$(0,0)$.
In one step, he is able to move unit distance along any diagonal line,
that is, at an angle of $\pm 45$ degrees or $\pm 135$ degrees.
\begin{problemparts}
\problempart
Describe how to model the robot's behavior as a state machine.

\omitsolution{
\begin{solution}

The possible states are:
$Q = \{(x, y)\} \subset (\reals \times \reals) $

The initial state is: $Q_0 = (0, 0)$

The transitions are:
$\delta \subseteq Q \times Q = $ $\{(q1, q2)$ such that $q2$ is $\pm 45$ 
degrees or 
$\pm 135$ degrees from $q1\} $

\end{solution}
}

\problempart
Give an execution of the state machine that reaches the point
$(\frac{5 \sqrt{2}}{2}, \frac{-3 \sqrt{2}}{2})$.

\omitsolution{
\begin{solution}

Starting at $Q_0$ make the following transitions: 
\begin{enumerate}
\item $-45$ degrees: New state is $(\frac{\sqrt{2}}{2}, \frac{- \sqrt{2}}{2} )$
\item $-45$ degrees: New state is $(\frac{2 \sqrt{2}}{2}, \frac{- 2 \sqrt{2}}{2} )$
\item $-45$ degrees: New state is $(\frac{3 \sqrt{2}}{2}, \frac{- 3 \sqrt{2}}{2} )$
\item $45$ degrees: New state is $(\frac{4 \sqrt{2}}{2}, \frac{- 2 \sqrt{2}}{2} )$
\item $-45$ degrees: New state is $(\frac{5 \sqrt{2}}{2}, \frac{- 3 \sqrt{2}}{2} )$
\end{enumerate}
\end{solution}
}

\problempart
Prove (using induction on the length of the execution) that the robot
cannot reach the point $(5,5)$. 

\omitsolution{
\begin{solution}

We will prove a stronger theorem first and then apply it to our special
case.

\begin{theorem*} 
After any n step execution (starting at $Q_0$), the $x$ and $y$ coordinates of
the final state are both multiples of $\frac{\sqrt{2}}{2}$.
\end{theorem*}

\begin{proof} Let $P(n)$ be the predicate that after $n$ steps, the  $x$ and
the $y$ coordinates of the current state are both multiples of 
$\frac{\sqrt{2}}{2}$.

\begin{description}\itemsep 0ex
\item[Base Case:~~] $P(0)$ is true since 
$Q_0 = (0,0)$ and $0$ is a multiple of $\frac{\sqrt{2}}{2}$.
\item[Inductive Step:~~] We must show that for any positive integer $n$,
$P(n) \implies P(n+1)$. We can do this by picking an arbitrary $n$ step
execution and enumerating all the possibilities for the $(n+1)$th step. 
By the inductive hypothesis, after our $n$ step execution, the current $x$ and
$y$ coordinates are both multiples of 
$\frac{\sqrt{2}}{2}$.
Therefore, we can pick integers $k$ and $j$ and call our current state:
$(\frac{k \sqrt{2}}{2} , \frac{j \sqrt{2}}{2} )$

Now there
are 4 possible transitions to the new state, $Q_{n+1}$:
\[
\begin{array}{rccccccccc}
45~degrees: & Q_{n+1} & = & (
\frac{k \sqrt{2}}{2} + \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} + \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k+1)\sqrt{2}}{2}, 
\frac{(j+1)\sqrt{2}}{2}
) \\
%
-45~degrees: & Q_{n+1} & = & ( 
\frac{k \sqrt{2}}{2} + \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} - \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k+1)\sqrt{2}}{2}, 
\frac{(j-1)\sqrt{2}}{2}
) \\
%
135~degrees: & Q_{n+1} & = & ( 
\frac{k \sqrt{2}}{2} - \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} + \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k-1)\sqrt{2}}{2}, 
\frac{(j+1)\sqrt{2}}{2}
) \\
%
-135~degrees: & Q_{n+1} & = & ( 
\frac{k \sqrt{2}}{2} - \frac{\sqrt{2}}{2},
\frac{j \sqrt{2}}{2} - \frac{\sqrt{2}}{2}) 
& = & (
\frac{(k-1)\sqrt{2}}{2}, 
\frac{(j-1)\sqrt{2}}{2}
) \\
\end{array}
\]
In all four situations, our resulting state still satisfies the
predicate. Therefore, we have $P(n) \implies P(n+1)$.

\end{description}

Finally, since the $x$ and $y$ coordinates of any reachable state are always
multiples of
$\frac{\sqrt{2}}{2}$, $(5,5)$ is not reachable.
      
\end{proof}

\end{solution}
}
\end{problemparts}

\problem
%[[[Taken from spring99, handout26, pset 4]]]
Suppose that the following procedure is used to
raise a real number $x$ to the non-negative integral power $y$.  
\begin{itemize}
\item Do the assignments $a := x, b := y, p := 1$.
\item Repeat the following steps:
  \begin{itemize}
  \item If $b$ is 0, output $p$ and terminate.
  \item If $b$ is even, do the assignment $a := a^2$ (that is, set the next
        value of $a$ to be the square of the current value), and also do
        $b := b/2$.
  \item If $b$ is odd, do $p := p \cdot a$ and $b := b - 1$.
  \end{itemize}
\end{itemize}

%[[[Shishir:  I pulled in the solution from the old handout, editing it
%slightly.  But I did this quickly.  Please read carefully,
%including checking that the presentation is consistent with the way the
%material is being presented in lecture this year.  My notes are in
%files ``lecture7, lecture 8, lecture9'' in the lectures directory.
%Also, formatting of solutions isn't consistent with what we're doing
%this year---please fix.  Same comments for the rest of this pset.]]]

\begin{problemparts}
\problempart Model the procedure with a state machine.

\omitsolution{
\begin{solution}

The state can be represented with a triple of numbers $a,b,p$:
\[Q = \{a, b, p\} \subset
(\reals \times \naturals \times \reals)
\]
The initial state is
\[
q_0 = (x,y,1)
\]
There are two transitions:
\begin{eqnarray*}
(a, b, p) &\rightarrow& (a^2, b/2, p) \,\,\mbox{ if $b$ is even and $b > 0$}
\\
(a, b, p) &\rightarrow& (a, b-1, ap) \,\,\mbox{ if $b$ is odd}
\end{eqnarray*}
The terminating condition is $b=0$, and then the state machine outputs~$p$.
\end{solution}
}



\problempart Formulate an invariant relating $a, b, x, y$, and $p$ that
holds in every state.  Your invariant should imply that if
$b = 0$, then $p = x^y$.

\omitsolution{
\begin{solution}

The invariant is expressed by the following predicate $P(\cdot)$ which
takes a state of the machine as an argument:
\[
P(a,b,p)=\mbox{``\,\,$a^bp=x^y$\,\,''}
\]
Note that if $b=0$ and $P(a,b,p)$ then $a^bp=p=x^y$.
\end{solution}
}


\problempart Prove that the invariant holds.

\omitsolution{
\begin{solution}
We use the Invariant Theorem.
Clearly, $P(q_0)$ holds:
\[
P(q_0)=\mbox{``\,\,$(x^y)*1=x^y$\,\,''}
\]
Now, we show that if $P(q)$ and $(q,q')$ is a valid transition then
$P(q')$: 

Take some $q=(a,b,p)$ and assume $P(q)$, i.e. that $a^bp=x^y$.  $q'=(a',b',p')$
could be a state following $q$ if one of the two cases holds:
\begin{itemize}
\item 
If $b>0$ and $b$ even then $(a',b',p')=(a^2,b/2,p)$, and then
\[
(a')^{b'}p'=(a^2)^{(b/2)}p=a^bp=x^y
\]
where the last equation follows from $P(q)$.  Hence, in this case
$P(q')$ is true.
\item
If $b$ odd then $(a',b',p')=(a,b-1,ap)$, and then
\[
(a')^{b'}p'=a^{b-1}ap=a^bp=x^y
\]
where again, the last equation follows from $P(q)$.  Hence, in this case
$P(q')$ is true as well.
\end{itemize}
\end{solution}
}


\problempart Prove that the procedure terminates.

\omitsolution{
\begin{solution}

We need to show that in any live execution, $b$ eventually reaches
$0$, because that's the termination condition.  Let's argue the
following facts:
\begin{enumerate}
\item 

It is an invariant of this state machine that $b$ is an integer.  It
starts as an integer $y$, and the two transitions preserve that: If
$b\in\integers$ and $b$ is even then $b/2\in\integers$.  Similarly,
if $b\in\integers$ then $(b-1)\in\integers$.

\item

$b$ cannot be a negative number.  We can show that by a contradiction:
If $b$ ever reached a negative number, since $b$ starts from a
nonnegative integer $y$, there must be a transition where $b$ went
below $0$, i.e. a transition from $b\geq{0}$ to $b'<0$.  But that's impossible
with our transitions:  
\begin{itemize}
\item
If $b\geq{0}$ then $b/2\not<{0}$
\item
If $b\geq{0}$ and $b\neq{0}$ then $b-1\not<0$.
\end{itemize}

\item
$b$ decreases in every transition (obviously, if $b>0$ than $b/2<b$
and $b-1<b$).
\end{enumerate}

Facts (1), (2) and (3) imply that $b$ must attain the value $b=0$ and
trigger the state machine to terminate.

Formally, it the the well-ordering principle that we use here: From
facts (1) and (2) it follows that for any execution of this state
machine, the set of values of variable $b$ is a subset of $\naturals$.
Therefore, from the well-ordering principle, it must have the smallest
element $b_0$. 

We claim that $b_0$ must be $0$.
If not, then since the execution is live, another step must
follow, which (by fact (3)) implies that the next value of $b$ must be
smaller.  But we have assumed that $b_0$ is the smallest value
attained by $b$.
This is a contradiction, which implies that $b_0=0$. 

Therefore, the procedure must terminate.

\end{solution}
}

\end{problemparts}


\problem
%[[[New problem]]]
The nondeterministic algorithm $NSort$ starts with a sequence $S$ of $n$
distinct integers, initially in any order.
$NSort$ describes how to sort the sequence, in place, into increasing order.
What it does is to choose, arbitrarily, any pair of adjacent numbers
that appear in the wrong order, that is, that form an ``inversion'',
as in Problem \ref{puzzleProblem}.
It corrects this inversion by interchanging these two numbers, leaving
the rest of the sequence $S$ unchanged.
$NSort$ repeats this step until no further steps can be applied.

\begin{problemparts}
\problempart
Model this as a state machine.

\omitsolution{
\begin{solution}

The state is represented by a string:
\begin{center}
$Q = \{ x_1 x_2 x_3 \cdots x_n $ such that $x_i \in \integers$ and the 
$x_i$ are all 
distinct $\}$
\end{center}

The possible start states are any random string so:
\[ Q_0 = Q \]
In other words, any state can be a starting state.

The set of transitions 
$\delta \subseteq Q \times Q$ is:
\begin{center}
$\{(q_1, q_2)\}$ such that $q_2$ is exactly the
same as $q_1$ except two adjacent positions are swapped. 
In $q_1$ these positions were
out of order (the greater one had lower index) but in $q_2$ the order is
correct.
\end{center}
\end{solution}
}

\problempart
Prove that $NSort$ eventually terminates with $S$ completely sorted.

\omitsolution{
\begin{solution}
Let us define three quantities:
\begin{description}
\item[~$N_{total}$:] Total number of out of order pairs in the string 
\item[~~~$N_{adj}$:] Number of out of order {\em adjacent} pairs in the string 
\item[$N_{nonadj}$:] Number of out of order {\em non-adjacent} pairs in the string
\end{description}
Notice that since adjacent or non-adjacent is an exhaustive set of
possibilities for a pair, for any state:
\[N_{total} = N_{adj} + N_{nonadj}\] 
Also, notice that all three quantities are by definition in $\naturals$.
The following lemma is very helpful: 

\begin{lemma}
$N_{total} = 0 \Longleftrightarrow N_{adj} = 0$
\end{lemma}

\begin{proof}

$\Longrightarrow$. For contradiction suppose $N_{adj} \neq 0$ but $N_{total}
= 0$. Then $N_{nonadj} = - N_{adj}$. Since both $N_{adj}$ and $N_{nonadj}$
are nonnegative, they must both be 0. Contradiction.

$\Longleftarrow$. For contradiction, suppose $N_{adj} = 0$ but $N_{total}
\neq 0$. Then there exists $i, j \leq n$ such that $i < j$ and $x_i >
x_j$. Let us pick $i$ and $j$ to minimize their difference. In other words,
out of the pairs that are inverted, let's pick the pair that is closest.
Since $N_{adj} =
0$, these two entries cannot be adjacent so $j > i + 1$. 
So there is some entry, $x_{i+1}$ adjacent to $x_i$. Since
no adjacent pairs are out of order,  $x_i < x_{i+1}$. Also, since $x_i$ and
$x_j$ were the closest inverted pair, $x_{i+1}$ and $x_j$ cannot be
inverted. Therefore, $x_{i+1} < x_j$. This means that $x_i < x_{i+1} < x_j$
which is a contradiction.
\end{proof}


First, we can use this lemma to prove {\bf correctness}. That is, we need to
show that when the algorithm terminates, the string is completely sorted. We
know that our algorithm terminates when there are no adjacent inverted
pairs. Applying our lemma, this means that there are no inverted pairs at
all. A string with no inverted pairs is a sorted string. QED.

Second, we can use this lemma to prove {\bf termination}. Consider the
following facts:
\begin{enumerate}
\item

$N_{total}$ decrease with every transition. {\em (Note that $N_{adj}$ does NOT
decrease with every transition.)}
We can show this by examining our transition. 
The exchange itself decreases the number of inversions by one. However,
it may produce ``new'' adjacent inversions. But the key fact is that it can form
no {\em new} inversions. The only thing that can happen is that a previously
non-adjacent inversion can become adjacent. This is because the only items
that move are the ones being exchanged, and they are being ordered
correctly. As far as all the other items in the string are concerned, the
two items are in the same place. Thus, the total number of inversions
decreases by 1 at every transition.

\item

$N_{total}$ will eventually reach 0 in any live execution. This is because
$N_{total}$ is a nonnegative integer by definition. By the well ordering
principle, and the fact that it is decreasing at every transition, it will
eventually reach 0. 

\item

When $N_{total}$ reaches 0, the algorithm will stop. We show this by
applying our lemma. If $N_{total} = 0$ then $N_{adj} = 0$ so the algorithm
terminates by definition.
\end{enumerate}

Thus the algorithm will terminate. Also, at termination, 
$N_{total} = N_{adj} = 0$ so the string is sorted.
\end{solution}
}

\problempart
Give a good upper bound on the number of steps that $NSort$ can take
until it terminates. 

\omitsolution{
\begin{solution}

Two possibilities are:
\begin{description}
\item[Loose upper bound: ]

Every item can be exchanged with every other item at most once. So for all
$n$ items, there are $n-1$ other items that they could be exchanged with. So
$n(n-1) = O(n^2)$ is an upper bound.

\item[Tight upper bound: ]

$N_{total}$ is definitely an upper bound since it decreases by 1 at every
step until it reaches 0. Also, $N_{total}$ is upper bounded by the total
number of combinations of elements of the string. This is $\left(
\begin{array}{c} n \\ 2 \end{array} \right)$ or $\frac{n(n-1)}{2}$. Notice
that this is the same as the loose bound except it recognizes that every
pair in the loose bound is actually being counted twice.

\end{description}

\end{solution}
}

\problempart
For the special case where n = 4, give an example execution that takes
the maximum number of steps to terminate. 

\omitsolution{
\begin{solution}
The following execution takes $\frac{n(n-1)}{2} = \frac{4*3}{2} = 6$ steps:
\[
\begin{array}{rccccccc}
Start  \longrightarrow & 4 & 3 & 2 & 1 \\
Step~1 \longrightarrow & 3 & 4 & 2 & 1 \\
Step~2 \longrightarrow & 3 & 2 & 4 & 1 \\
Step~3 \longrightarrow & 3 & 2 & 1 & 4 \\
Step~4 \longrightarrow & 2 & 3 & 1 & 4 \\
Step~5 \longrightarrow & 2 & 1 & 3 & 4 \\
Step~6 \longrightarrow & 1 & 2 & 3 & 4 
\end{array}
\]
\end{solution}
}

\end{problemparts}



\problem
%[[[Based on spring97, handout 28, pset 9 solutions]]]
The algorithm $Mark$ starts with a connected, undirected graph $G =
(V,E)$, with all edges unmarked.
Then it proceeds to mark some of the edges, by repeatedly performing
the following steps: 
\begin{enumerate}
\item {\bf Choose} any edge $e \in E$ such that there is currently no path of
marked edges between the endpoints of $e$ \\
\item {\bf Mark} edge $e$\\
\end{enumerate}
Prove that when the algorithm finishes, the set of marked edges forms
a spanning tree of the input graph $G$.

(A {\em spanning tree} of $G$ is a tree whose edges are a subset of
the set $E$ of edges of $G$, and that contains an edge incident on every
vertex of $G$.)

\omitsolution{
\begin{solution}

We will need to show that the marked edges are acyclic, touch every vertex
of G, and that the algorithm does indeed finish. 

\begin{description}

\item[Marked edges are acyclic:]

Use the Invariant Theorem:

{\bf Invariant:} The marked edges form an acyclic graph. 
\begin{description}
\item[Start condition:] Initial state.  
Initially all edges are unmarked, so there are no cycles consisting of
marked edges. 

\item[Step condition:]
Consider a step $(q,q')$, where we assume that there are no cycles
consisting of marked edges in state $q$.
We show that the same condition holds in state $q'$.

In this step, the algorithm marks an edge $e$ for which there was
previously no marked path between its endpoints.
This means that, after the step, there is exactly one marked path
between the endpoints of $e$.
Thus, the new edge is not part of a cycle, in the new state $q'$.
This means that there are still no cycles in state $q'$.
\end{description}

\item[Algorithm terminates:] 
This is shown because once an edge is marked, it can never be
unmarked. Since we have a finite set of edges, and every transition
necessarily marks one edge, we will eventually run out of candidate edges
and the algorithm will terminate.

\item[Marked edges touch every vertex of G:] We can show this by
noticing that if $(v, w)$ is an edge in G then there is a path of marked
edges from $v$ to $w$. If there wasn't, then $(v, w)$ would become a
candidate edge because its endpoints are not connected by marked edges. Then
$(v,w)$ would itself be marked and thus $v$ and $w$ are indeed connected by
marked edges. 

Now we need to show that every vertex is touched by a marked edge. For
contradiction, suppose there is some $v \in G$ that is not touched by any
marked edges.  However, G is connected, so there must be at least one
$(v,w)$ edge in G. Since this edge exists, $v$ and $w$ must be connected by
marked edges, so $v$ must indeed be touched by a marked edge. Contradiction.



%[[[We must also show that when no rule can be applied, it must be the
%case that the marked edges form a spanning tree of $G$.
%Shishir?  Prove this?  The following lines appeared in the previous
%solution, but they don't look like a convincing proof to me.
%
%``Since the for-loop loops over all the edges then all the vertices of
%$G$ (that have edges) will be contained in the forest.''
%
%Basically, we have to argue that, if we reach a point where no further
%steps are enabled (a ``final state''), then any two nodes are
%connected by some path of marked edges.
%I think that this probably will use a lemma saying, in a final state,
%if $(v,w)$ is an edge of $G$ then there is a path of marked edges from
%v to w.
%Then apply this lemma in an inductive proof to show that any two nodes
%of $G$ (which are assumed to be connected in $G$ by SOME path), are
%connected in the final state by a path of marked edges.
%Probably could avoid the induction by using some kind of transitive
%closure result.
%]]]
%
\end{description}

\end{solution}
}



\problem
%[[[New problem.  Needs solutions.  Needs formatting.  Needs
%proofreading, clarifying, etc.]]]
Cache management protocol $HybridCache$ is a hybrid of the two caching
protocols presented in Installment 2 of the notes on computational
processes.
$HybridCache$ maintains a memory and two caches, as before.
Only now, an update to memory causes the value to be cleaned out of
cache1 but not out of cache2.
The intent is that cache2 is allowed to be out-of-date, but cache1 is
not.

\begin{problemparts}

\problempart
Model $HybridCache$ carefully as a state machine.

\omitsolution{
\begin{solution}

\begin{description}
\item[$Q$:] $\{ (memory, cache1, cache2) \mbox{ of the types described in Lecture 8 handouts}\}$. \\
\item[$Q_0$:] memory is arbitrary, caches map everything to $\ms{null}$. \\
\item[$\delta$:] 
$(\ms{memory}, \ms{cache1}, \ms{cache2}) \rightarrow 
 (\ms{memory}', \ms{cache1}', \ms{cache2}')$ where all steps are the same as in Lecture 8 except
the memory update step:
\begin{description}
\item[1. ] 
$\ms{memory}(a) :=$ arbitrary $\ms{value}$ (not null). \\
$\ms{cache1}(a) := \ms{null}$ 
\end{description}
\end{description}

\end{solution}
}

\problempart
State carefully an invariant saying that cache1 is always up-to-date. 

\omitsolution{
\begin{solution}

Can show, in all reachable states either
$\ms{cache1}(a) = \ms{memory}(a)$ or 
$\ms{cache1}(a) = \ms{null}$ \\
\\
In other words: 
If $\ms{cache1}(a) \neq \ms{null}$ then $\ms{cache1}(a) =
\ms{memory}(a)$. \\

Note: No such guarantees are provided for cache2.
\end{solution}
}

\problempart
Prove your invariant carefully using the Invariant Theorem.

\omitsolution{
\begin{solution}
\begin{description}
\item[Start condition:] 
Everything in cache1 is null so the invariant is trivially true.

\item[Transition condition:] 
We show all possible transitions:
\begin{description}
\item[1. Memory Update: ] 
After this step, 
the only changed value is in cache1 and is changed to null. In this case, the Invariant holds 
trivially (they only need to match if cache1 holds a value other than null).
\item[2. Cache1 Update: ] 
The only changed value is in cache1 and is changed to match the one in memory. Invariant holds.
\item[3. Cache2 Update: ] 
Only cache2 changes. Since the Invariant makes no claims about cache2, the Invariant still holds.
\item[4. Cache1 Drop Value: ] 
The only changed value is in cache1 and is changed to null. In this case, the Invariant holds 
trivially.
\item[5. Cache2 Drop Value: ]
Same as 3.
\end{description}
\end{description}

\end{solution}
}

\problempart
Now modify $HybridCache$ to a new $WrongHybridCache$ algorithm,
which is just like $HybridCache$ but includes one additional type of
step,
which allows anything to be copied from
cache2 to (the same address in) cache 1.
Model this new algorithm as a state machine.

\omitsolution{
\begin{solution}

Same as in a. except for one additional transition:
\begin{description}
\item[6. ] 
$\ms{cache1}(a) := \ms{cache2}(a)$ 
\end{description}
\end{solution}
}

\problempart
Give an execution of $WrongHybridCache$ that demonstrates that the
invariant is violated. 

\omitsolution{
\begin{solution}
\begin{description}
\item[memory\_write(1)] 
$~$\\
$\ms{memory}(a) := 1$ \\
$\ms{cache1}(a) := null$ 

\item[cache1\_update()]
$~$\\
$\ms{cache1}(a) := 1$ 

\item[cache2\_update()]
$~$\\
$\ms{cache2}(a) := 1$ 

\item[memory\_write(2)]
$~$\\
$\ms{memory}(a) := 2$ \\
$\ms{cache1}(a) := null$ 

\item[cache2\_to\_cache1()]
$~$\\
$\ms{cache1}(a) := 1$ 

\end{description}

Now cache1 holds a different value than memory in entry a. 
\end{solution}
}

\problempart
Identify precisely where your proof of the invariant for $HybridCache$
would break down if you applied it to $WrongHybridCache$.

\omitsolution{
\begin{solution}

It would break down in trying to prove the transition holds through transition 6. 
Here it is not the case that the value in cache1 is always changed to either match memory
or be null. Cache1 can take on any value from cache2, and we have no guarantees that the value in
cache2 is up to date.

\end{solution}
}

\end{problemparts}


\problem
%[[[New problem.  Comes from lecture notes from fall98---I believe
%Eric Lehmann wrote up a supplementary handout on this.  But
%beware---the old statement of this that I used in fall98 had the boys
%and girls reversed.]]]
It turns out that the stable marriage algorithm described in lecture
(Installment 2 of notes) is very unfair, in the sense that, in any
(live) execution of the algorithm:
\begin{itemize}
\item The boys end up paired up with the most preferred girl that they
possibly could get.
\item The girls end up paired up with the least preferred boy that they
possibly could get.
\end{itemize}
(So, being aggressive pays.)

More precisely, define $\ms{PP}$ (``possible pairs'') to be the set of
all (boy,girl) pairs that occur in any stable pairings.
Then, in the final state of the algorithm:
\begin{itemize}
\item If a boy $b$ likes a girl $g$ more than the partner he has received, then
$(b,g) \notin \ms{PP}$, that is, $g$ isn't even possible for him.
\item If a girl $g$ likes a boy $b$ less than the partner she has
received, then $(b,g) \notin \ms{PP}$. 
\end{itemize}

Prove these results.

\omitsolution{
\begin{solution}

\begin{description}
\item[(a) ]

You can prove as an invariant, the claim that:
``If $b$ has crossed $g$ off his list, then $(b,g) \notin \ms{PP}$.''
This statement immediately implies the claim in (a).

%[[[Shishir: 
The key step is where g rejects b, and he crosses her off
his list. 
She rejects him in favor of some other boy b'.

Now, suppose for the sake of contradiction that P is a stable pairing
containing $(b,g)$.
We can show that $(b',g)$ form an unstable pair in P:
We know that $g$ prefers $b'$ to $b$, because in this step of the
algorithm, she rejects $b$ in favor of $b'$.
We have to argue that, also, $b'$ prefers $g$ to whomever he is matched up
with in P---call her $g'$.

This is a tricky argument.
Can argue it by contradiction, using the fact that the invariant is
true before the step.
Suppose for the sake of contradiction that $b'$ prefers $g'$ to $g$.
In the pre-state, $b'$ is pursing $g$, so he must have crossed off
his higher preference $g'$.
But by the invariant in the pre-state, this means that $(b',g') \notin
\ms{PP}$, that is, $(b',g')$ do not form a possible pair.
That's a contradiction, because we've assumed that they are paired in
the stable pairing $\ms{PP}$.
%]]]

\item[(b) ]

You can prove the invariant:

``If $g$ likes $b$ less than her most-preferred boy that is currently
pursuing her, then $(b,g) \notin \ms{PP}$.''
This statement implies the claim in (b).

This can be proved without using an inductive argument (or the
Invariant Theorem), but simply by contradiction using the invariant
used for part (a). 

%[[[Shishir:  It's not so simple to keep straight.

Suppose for the sake of contradiction, that there is some reachable
state in which
$g$ likes $b$ less than her most-preferred boy that is currently
pursuing her, call him $b'$, 
but $(b,g) \in \ms{PP}$.
Fix P, some stable pairing having $(b,g) \in P$.
We can show that $(b',g)$ form an unstable pair in P:
We know that $g$ prefers $b'$ to $b$, by the assumption above.
We have to argue that also $b'$ prefers $g$ to whomever he is matched
with in $P$, call her $g'$.

Suppose he doesn't (this is going to be a contradiction within a
contradiction!), that is $b'$ prefers $g'$ to $g$.
That is, $b'$ prefers $g'$ to the girl he is currently pursuing.
This means that $b'$ has crossed $g'$ off his list in the current state.
By the previous invariant, proved for part (a), it follows that
$(b',g') \notin \ms{PP}$.  
So surely we can't have $(b',g') \in P$.
This is a contradiction, which means that $b'$ does prefer $g$ to
$g'$.
That's what we needed to show above.

So, this all says that $(b',g)$ form an unstable pair in P.
That's a contradiction to the assumption that P is a stable matching.


%Shishir:
%You might find it helpful to write this in a structured way.  This is
%exactly the sort of proof where the logic gets confusing.
%Shishir: I have a handwritten structured version at home, but it has
%the boys and girls interchanged.  I think Eric probably type-set this
%and put it into the supplementary lecture notes for fall98.]]]
\end{description}

\end{solution}
}



\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 $\mathrm{add-term}(c,e)$, which is supposed to add the term $c x^e$ to the
maintained polynomial.
\item $\mathrm{coeff}(e)$, which asks for the coefficient of the $x^e$ term.
\end{itemize}

\omitsolution{
\begin{solution}

Solution to this problem will be given out next week. The material covered in this problem 
will not be covered on the quiz.

\end{solution}
}


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

[[[Tutorial:

I suggest that we use tutorial this week to go over these problems,
except for the last one, which is based on next Tuesday's lecture.
In fact, probably we should give out the pset on Tuesday, discuss the
problems in tutorial, then hand out the solutions at the end of
tutorial.  That way, they get several days to think about the problems
without the solutions, and then get the solutions in time to study
this stuff over the weekend.

Mini-quiz: 
Rosen section 6.4, problem 19, but ask for
R^4 and (I \/ R)^4.
]]]
