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

\input{macros-course}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}

\askaboutsolutions

\begin{document}
\pset{5}{October 3, 2000}{2:35pm in lecture, Thursday, October 12, 2000}

\textbf{Be sure to indicate your TA's name clearly on the solutions
your turn in}.

-----------------------------------------------------------------------------\\

\textbf{Self-study: Simple algorithms and pseudocode}
Read: Rosen Section 2.1
Self-study problems (not to be handed in): 1, 3, 5, 7, 9, 11, 19
%[[[Miniquiz for tut5: 11]]]

-----------------------------------------------------------------------------\\

\textbf{Reading:}
Lecture notes;  Rosen 2.1, 3.5 (skim)

\paragraph{Policy on collaboration}
If you collaborated with someone on the problem sets, you should mention their names on top of the problem set. If you did not collaborate with anyone, you should explicitly say so. As a reminder, the write-up of your solutions should be entirely your own.
 
\medskip
\begin{problems}

\problem
% 1
% Covers:  Puzzle state machine, modular arith, irrationals
In ancient times, the downtown section of Verona was laid out in a 1000
by 1000 meter square.
Romeo lived at grid point $(0,0)$ of the square, and Juliet lived at
grid point $(0,1000)$. 
Of course, Romeo and Juliet wanted to meet, at {\em exactly\/} the same point
in the square.
However, both were restricted by their rather strange families to move
according to very particular rules:
Romeo could only move 3 units, parallel to either the $x$ axis or $y$
axis or at a 45 degree angle to both axes.
Juliet could only move $3$ units, and only parallel to either
the $x$ axis or $y$ axis.

\ppart
Model Romeo and Juliet and their possible moves as a (single) state
machine.

\ppart
Can they meet, by some sequence of moves?

\ppart
If your answer to ... is yes, then give such a sequence of moves.
If your answer to ... is no, then prove formally that they cannot, by
finding and proving an appropriate invariant of your state machine.


\problem
% 2
% Sequential algorithm
The following weird algorithm is used to multiply two natural numbers
$x$ and $y$ using only multiplication and division by $3$.
The answer is accumulated in variable $a$; variables $r$ and $s$ are
for temporary storage.
[[[Base this on Problem 5 of last term's pset 4.  But now there are
three cases instead of two:
if s = 0 mod 3 then multiply r by 3 and divide s by 3
if s = 1 mod 3 then add r to a, multiply r by 3, divide s-1 by 3, 
if s = 2 mod 3 then add 2r to a, multiply r by 3, divide s-2 by 3, 

The parts of the question can be the same:
(a) model...
(b) list steps of some suitable execution ... you can use inputs x = 5
and y = 10, e.g.
(c) invariant---same as before?
(d) termination

\problem
% 3
% Sequential algorithm
[[[This one needs writing in nice English.  I'll just outline it.]]]
Recall the double induction example from lecture...
Recast this as a nondeterministic algorithm, where the start state has
all the (n,0) and (0,k) entries already filled in (set to 1).
(Yes, I know that's an infinite amount of information.  That's allowed.)
The algorithm has only one kind of step:
for any location $(n,k)$ that isn't filled in, but for which both the left
location $(n,k-1)$ and the lower location $(n-1,k)$ are filled in,
fill in the new location with the sum.

\ppart
The main correctness property we are interested in is that any value
that is filled in is in fact equal to n! / k! (n-k)!
Prove this using the Invariant Theorem.

\ppart
What can you say about termination?


\problem
% 4
% Caching 

[[[caching problem from last year's pset 4.5, problem 6.  About
   hybrid caching scheme.]]]

[[[I'm not happy with using so many problems (3) from last year's pset
4.5.  If we could think of some variations on these, that would be nice.]]]

\problem
% 5
% Matching
[[[Fix up English.]]]
Suppose that $n$ girls and $m$ boys show up one evening for MIT
Ballroom Dancing, where $n > m$.  Suppose they use the same matching
algorithm that we studied in class. 
What happens?
Prove your answer.

\problem
% 6
% Matching
[[[Problem 7 from spring 00 pset 4.5
[[[This is hard.  May want some hints...???]]]

\problem
% 7
% Graph algorithm, state machine, invariant, Invariant Theorem,
% Termination Theorem
[[[Problem 7 of Spring 00 Quiz 1
This is the one about red and blue coloring.
It has 5 parts.  Note that part (c) refers to a fact from the previous
problem.  We can just give them that fact.]]]

\end{problems}
\end{document}

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

Tutorial:

Miniquiz:  Problem 11 from the self-study reading 

1. [[[final exam from Fall 98, problem 2]]]

[[[This one is about an extension of the GCD algorithm done in class.]]]

2. [[[Problem 1 or Problem 4 from pset 4.5, spring 00]]]

3. Suppose we are given a particular state machine $M =
(Q,Q_0,\delta)$, and we are told that $Q$ is a finite set.
Suppose that we are also given a particular state $q' \in Q$.
(a) Describe an algorithm that determines whether or not $q'$ is a
reachable state of $M$.
(b) Express this algorithm as another state machine. 

[[[The idea would be to write some kind of searching algorithm in an
iterative style.  E.g., keep track of all the states known to be
reachable, and of a set of states from which it is still
necessary to explore.]]]
















