\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 
\usepackage{eepic}

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
\renewcommand{\coursecopyrightnames}{Dr.~Radhika~Nagpal}

\begin{document} 
\inclassproblems{3, Fri}            % !! start the paper


{\em Definition:} The \emph{composition} of relations $R \subseteq A
\times B$ and $S \subseteq B \times C$ is the relation

$S \circ R =\{(a,c) \mid \exists b \mbox{ such that } 
(a,b) \in R \wedge (b,c) \in S \}.$

% Made this up (RAD)
% based on Bassethound problem from last year (fall 01, pset3)
\begin{problem}

Recently MIT students have been taking a hard look at the haphazard
building layout, and have been asking some hard questions. As always
they know they can use their superior mathematical skills to get some
real answers to those hard questions.

They decide to express the MIT building layout as a relation. Let $C$
be the set of all building numbers and let $R$ be the relation on the
set $C$ such that $(a,b) \in R$ if building $a$ and building $b$ are
physically adjacent and there is a door between $a$ and $b$ (more
importantly, one doesn't have to go outside to get from $a$ to
$b$). Note that if $(a,b) \in R$, then $(b,a)$ is also in $R$, so $R$
is a symmetric relation. For convenience, they also define a building
to be related to itself, so $(a,a) \in R$.

\begin{problemparts}

\problempart For this part only, let $C$ be the set of MIT buildings
10,13,12,4,8,26. Then $R$ looks like this:

\input{figures/cp3F-figure1.latex}

% \begin{verbatim}
%                    26
%         13   12    |
%         |    |     |
%         10---4-----8
% \end{verbatim}

Compute $R^2 = R \circ R$. \newline
Compute $R^3 = R \circ R^2$.


\solution{

$R^2$ consists of all pairs of buildings that are connected via exactly
one building. Since there are self-loops in the connectivity graph (each
building is connected to itself), $R^2$ includes everything which is in
$R$ as well. For example, $(13,10)$ which is in $R$ must also be in
$R^2$ because you can go from building $13$ to building $10$ ``via one
building'' by just going around building $13$ once and then moving on to
building $10$. That said, we conclude that
\[R^2 = R \union \Big\{(13,4),(4,13),
(10,12),(12,10),(10,8),(8,10),(12,8),(8,12),(4,26),(26,4)\Big\}
\]

Similarly, $R^3$ contains everything which is in $R^2$ (because of the
self-loops), plus all the extra pairs that we get by allowing
connections via \emph{two} intermediate buildings. So we have:$$R^3=
R^2 \union
\Big\{(13,12),(12,13),(10,26),(26,10),(13,8),(8,13),(26,12),(12,26)\Big\}
$$
%\input{cp3M-1.pic}
}

\problempart Let $R$ be the map for all of MIT. What does the relation
$R^2$ represent in terms of connectivity between numbered buildings?
Can you generalize this?

\solution{
$R^2$ is the set of all pairs of buildings that are connected
via exactly 1 building. Similarly $R^3$ is the set of all
pairs of buildings that are connected via exactly 2
buildings. This notion can be generalized to $R^n$, where $(a,b)$ is in
$R^n$ iff $a$ and $b$ are connected via exactly $n-1$
buildings. We can recursively define $R^n$ as $R \circ R^{n-1}$.
Induction would thus be a natural way to go about proving this. It is
worth looking at the proof, which can be found both in the notes and in
Rosen.

It is important to notice that \emph{in general} it is not necessarily
true that $R^n$ must include $R^{n-1}, R^{n-2}, \ldots, R$ as well. In
our example, this was the case because the graph included self-loops and
bidirectional edges (symmetric relation), so one can meet the requirement
of going from building $a$ to building $b$ through $n-1$ intermedite
buildings by going around building $a$ as many times as necessary and
then proceeding to building $b$ (there are many similar time-wasting
ways to meet the requirement).
}

\problempart One of the important questions for course 6 students was,
is it possible to get from building 36 to building 10 without crossing
more than 5 other buildings? Write a proposition in terms of $R$,
using relational and set operators, which is true if this condition is
satisfied and false otherwise.

\solution{The key to solving this is to first write an expression for
the set of all buildings that are connected via 5 or fewer
buildings. In general, this would be $(R \union R^2 \union R^3 \union
\ldots \union R^6)$.  As explained above, in our case this is the same
as $R^6$. Then the predicate on $R$ is $(36,10) \in R^6$.  }

\problempart The MIT students would like to be able to get from any
building to any other building, without having to go outside. Write
the condition on $R$ that must be satisfied in order for this to be
true.

\solution{Let $\card{C}$ be $n$. In other words there are $n$
different buildings. The furthest apart two buildings can be, and
still be connected, is to be connected via $n-2$ other buildings
(prove this to yourself). Therefore the set $(R \union R^1 \union R^2
\union \ldots \union R^{n-1})$ represents all the pairs of buildings
that can reach one another without going outside. Because of the
self-loops, this is just $R^{n-1}$ since this set includes everything
else as well.

However we want every pair of buildings to be connected. The set of
all pairs of buildings is $C\times C$. Therefore the condition we want
to satisfy is $ C \times C\subseteq R^{n-1}$ (``the set of all
possible pairs of buildings is a subset of the set of buildings that
you can reach through $n-2$ intermediate buildings'').  }

\problempart MIT administration, however, wants to keep the number of
connections between building as small as possible. In other words, MIT
wants the size, $\card{R}$, of $R$ to be as small as possible. What is
the smallest $R$ that satisfies the requirement in part (d)?  Is the
smallest $R$ unique?

\solution{The smallest graph such that all the buildings are connected
would be to connect them in a straight line. The number of edges in
that graph is $n-1$. How do we know that this is the smallest number
of edges? Next week we will learn a theorem that says that the
smallest connected graph with vertices $n$ has at least $n-1$
edges. Each edge contributes two pairs therefore $\card{R} = 2(n-1)$.

The smallest graph is not unique, for starters we can connect the
buildings in a different order in the line. But there are many other
connected graphs with $n$ vertices and $n-1$ edges (any tree with $n$
nodes in fact satisfies this constraint, as we shall see next week).}

\end{problemparts}
\end{problem} 

%------------------------------------------------------------
% from the notes, roughly (Rad)

\begin{problem}
A relation $R$ from $A=\{a_1, a_2, \ldots, a_m\}$ to $B=\{b_1, b_2,
\ldots, b_n\}$ can be represented as a boolean matrix $M_R$, where
$M_R(i,j)=1$ if the pair $(a_i,b_j) \in R$ and $M_R(i,j)=0$ if the
pair $(a_i,b_j)$ is not in $R$.

We define boolean matrix multiplication to be the same as regular
matrix multiplication except that ``$+$'' is replaced by $\vee$
(Boolean OR) and ``$\times$'' is replaced by $\wedge$ (Boolean AND).

\begin{problemparts}
\problempart We have a student set $stud=\{Adrian,Min,Josh\}$, a class set $class=\{6.042,6.046\}$ and a lecture set $lect=\{Albert, Charles, Radhi\}$. The relation $K$ ``is taking class'' as a subset of $stud \times class$ is defined by the list: 
$\{(Adrian,6.042),(Min,6.046),(Josh,6.042),(Josh,6.046)\}$
and the relation $L$ ``is lectured by''as a subset of $class \times lect$ is defined by the list: 
$\{(6.042,Albert),(6.042,rahdi),
$\\

$(6.046,Charles)\}$. 
The relation $T$ ``is taught by'' is the composition of relations $K$ and $L$. Represent relation $T$ in boolean matrix and compare it with the boolean matrix multiplication of relation $K$ and relation $L$.

\solution{The relation $T$ is represented by the matrix
\begin{displaymath}
  \begin{array} {r|ccc} 
          &Albert& Charles& Radhi \\
    \hline
    Adrian&  1   &    0   &   1   \\
    Min   &  0   &    1   &   0   \\
    Josh  &  1   &    1   &   1   \\
  \end{array}
\end{displaymath}
}

\problempart Let $M_P$ be the boolean multiplication of $M_R$ and $M_S$, where $R \subseteq A \times B$ and $S \subseteq B \times C$. Write down the formula of the boolean matrix multiplication of $M_P(i,j)$ in terms of $M_R$ and $M_S$. \footnote{Recall that the \emph{composition} of relations
$R \subseteq A \times B$ and $S \subseteq B \times C$ is the relation
$S \circ R =\{(a,c) \mid \exists b \mbox{ such that } (a,b) \in R
\wedge (b,c) \in S \}$}

\solution{Suppose set $B$ has $n$ elements,
\[
M_P (i,j) = [M_R(i,1) \wedge M_S(1,j)] \vee [M_R(i,2) \wedge M_S(2,j)] \vee 
\ldots \vee [M_R(i,n) \wedge M_S(n,j)]
\]
}

\problempart Prove that boolean multiplication of $M_R$ and $M_S$ is
equal to $M_{S \circ R}$.


\solution{Let $M_P$ be the boolean product of $M_R$ and $M_S$, what
we want to prove is that
\[
(a_i,c_j) \in S\circ R  \Longleftrightarrow  M_P (i, j)=1
\]

Recall that by the definition of composition, $(a_i,c_j) \in S\circ R $
iff there exists a $k$ such that $(a_i,b_k) \in R$ and $(b_k,c_j) \in
S$. (We assume that set $B$ has $n$ elements.) Also, we have already got 

\[
M_P (i,j) = \underbrace{\left[M_R(i,1) \wedge
M_S(1,j)\right]}_{b_1 \text{ is the ``link''}} \vee 
\underbrace{\left[M_R(i,2) \wedge
M_S(2,j)\right]}_{b_2 \text{ is the ``link''}}\vee 
\ldots \vee\underbrace{\left[M_R(i,n) \wedge
M_S(n,j)\right]}_{b_n \text { is the ``link''}}
\]

\begin{description}
\item[Case 1:($\Longrightarrow$)] If $(a_i, c_j) \in S\circ R$, then for
at least one $k$, $1 \leq k \leq n$, $(a_i,b_k) \in R$ and $(b_k,c_j) \in
S$. Consequently, $M_R(i,k)=1$ and $M_S(k,j)=1$. This turns
$\left[M_R(i,k) \wedge M_S(k,j)\right]$ true, and hence $M_P(i,
j)=1$.

\item[Case 2: ($\Longleftarrow$)] If $M_P(i, j)=1$ then there is at least one
$k$, $1 \leq k \leq n$, for which $\left[M_R(i,k) \wedge
M_S(k,j)\right] =1$. This means that both $M_R(i,k)=1$ and $M_S(k,j)=1$.
Since $M_R$ and $M_S$ are the matrix representations of $R$ and $S$, we
can conclude that $(a_i,b_k)\in R$ and $(b_k,c_j)\in S$, and so, by the definition
of composition, $(a_i,c_j)\in S\circ R$ 
\end{description}
 
}

\problempart What does the regular multiplication of $M_R$ and $M_S$
give you?

\solution{Let $M_P$ be the regular product of $M_R$ and $M_S$.  

\[
M_P (i,j) = \underbrace{\left[M_R(i,1) \times
M_S(1,j)\right]}_{b_1 \text{ is the ``link''}} + 
\underbrace{\left[M_R(i,2) \times
M_S(2,j)\right]}_{b_2 \text{ is the ``link''}} + 
\ldots +
\underbrace{\left[M_R(i,n) \times
M_S(n,j)\right]}_{b_n \text { is the ``link''}}
\]

If $\left[M_R(i,k) \times M_S(k,j)\right]=1$, where $1 \leq k \leq n$,
both $M_R(i,k)=1$ and $M_S(k,j)=1$.  Since $M_R$ and $M_S$ are the
matrix representations of $R$ and $S$, we can conclude that
$(a_i,b_k)\in R$ and $(b_k,c_j)\in S$ and there is a path from $a_i$
to $c_j$ via $b_k$.  Therefore, $M_P(i, j)$ gives you the number of
paths from $a_i \in A$ to $c_j \in C$ via B. 


The regular multiplication gives you the number of paths from any
element in A to any element in C via B. In general many questions on
relations can be framed as operations on boolean matrices which is
very useful for programming.}

\end{problemparts}
\end{problem}

\begin{problem}
The term {\em six degrees of separation} implies that everyone knows
everyone else indirectly through at most 6 other people. Discuss how
you would write a computer program to determine if six degrees of
separation holds within our 6.042 class.

\solution{Meant to be an open ended discussion. Beyond framing the
relational question correctly, things to think about are how would you
collect data, what representation would you use, how would you make it
efficiency, etc.}
\end{problem}

%----------------------------------------------------------
% Directly from the Notes
%
%
% \begin{problem} Use induction to prove that 
%$R^n = \{(a,b) \mid \mbox{there is a length $n$ path from $a$ to $b$
%in $R$}\}$, where $R$ is a relation on a set $A$.
%
%\solution{ {\em TA Notes (remove before publishing
%solution). Optional, do only if you have alot of time left. Better to
%concentrate on having a good discussion about problem 3 - see if
%someone wants to volunteer to write a program tht would check if
%six-degrees hold...}
%
 % From Course notes 3.
%
 % By induction. Let
%  \begin{displaymath}
%    P(n) ::= \mbox{$R^n = \{(a,b) \mid \mbox{there is a length $n$ path
%        from $a$ to $b$ in $R$}\}$}.
%  \end{displaymath}
%
%  The base case is clear. There is exactly one edge from $a$ to $b$
%  for every $(a,b) \in R$. And there is exactly one pair $(a,b) \in R$
%  for every edge from $a$ to $b$, $P(1)$~is true. Note that since the
%  induction hypothesis is an equality we have to prove both sides.
%  
%  For the inductive step, suppose $P(n)$ is true.  
%
%  First consider a path $a_0,\ldots,a_{n+1}$ in $R$. This is a path
%  $a_0,\ldots,a_n$ in $R$ followed by a pair $(a_n,a_{n+1})$ of
%  $R$. By the inductive hypothesis, we can assume that $(a_0,a_n) \in
%  R^n$. And we have already mentioned that $(a_n,a_{n+1}) \in
%  R$. Therefore $(a_0,a_{n+1}) \in R^{n+1}$ by the definition of
%  composition. Thus, every path of length $n+1$ corresponds to a
%  relation in~$R^{n+1}$.
%  
%  Now consider a pair $(a,b) \in R^{n+1}$. By the definition of
%  composition, there exists a $c$ such that $(a,c) \in R^n$ and $(c,b)
%  \in R$. By the inductive hypothesis, we can assume that $(a,c)$
%  corresponds to a length $n$ path from $a$ to $c$, and since $(c,b)
%  \in R$ there is an edge from $c$ to $b$. Thus, there is a length
%  $n+1$ path from $a$ to $b$. To conclude, $P(n) \implies P(n+1)$.
%}
%\end{problem}
%
%-----------------------------------------------------------


\end{document}

