\documentclass[12pt]{article}
\usepackage{light}

%\hidesolutions
\showsolutions

\newcommand{\edge}[2]{#1\text{---}#2}
\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}

\begin{document}

\recitation{9}{October 8, 2004}

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

\begin{problem}
Give a description of the equivalence classes associated with each of
the following equivalence relations.

\bparts

\ppart Integers $x$ and $y$ are equivalent if $x \equiv y \pmod{3}$.

\solution[\vspace{0.5in}]{
\[
\begin{array}{l}
\set{\ldots, -6, -3, 0, 3, 6, \ldots } \\
\set{\ldots, -5, -2, 1, 4, 7, \ldots } \\
\set{\ldots, -4, -1, 2, 5, 8, \ldots }
\end{array}
\]}

\ppart Real numbers $x$ and $y$ are equivalent if $\lceil x \rceil =
\lceil y \rceil$, where $\lceil z \rceil$ denotes the smallest integer
greater than or equal to $z$.

\solution[\vspace{0.5in}]{For each integer $n$, all the real numbers
$r$ such that $n - 1< r \leq n$ form an equivalence class.}

\ppart Vertices $x$ and $y$ in the graph $G$ are equivalent if there
is a path from $x$ to $y$.

\solution[\vspace{0.5in}]{The vertices in each connected component of
$G$ form an equivalence class.}

\eparts

\end{problem}

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

\begin{problem}
Show that neither of the following relations is an equivalence
relation by identifying a missing property (reflexivity, symmetry, or
transitivity).

\bparts

\ppart The ``divides'' relation on the positive integers.

\solution[\vspace{0.5in}]{This relation is reflexive (since $a \mid
a$) and transitive (since $a \mid b$ and $b \mid c$ implies $a \mid
c$), but not symmetric (since $3 \mid 6$, but not $6 \mid 3$).}

\ppart The ``implies'' relation on propositional formulas.

\solution[\vspace{0.5in}]{This relation is reflexive since $p \implies
p$.  It is also transitive, since if $p \implies q$ and $q \implies
r$, then $p \implies r$.  However, it isn't symmetric since, for
example, $\texttt{false} \implies \texttt{true}$, but not
$\texttt{true} \implies \texttt{false}$.}

\ppart The ``intersects'' relation on nonempty subsets of
$\mathbb{N}$.

\solution[\vspace{0.5in}]{The relation is reflexive, since every
nonempty subset $A$ of $\mathbb{N}$ intersects itself.  The relation
is symmetric, because if $A$ intersects $B$, then $B$ intersects $A$.
However, the relation is not transitive; for example, $\set{1, 2}$
intersects $\set{2, 3}$ and $\set{2, 3}$ intersects $\set{3, 4}$, but
$\set{1, 2}$ does not intersect $\set{3, 4}$.}

\eparts

\end{problem}

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

\insolutions{

\section*{Parallel Scheduling}

Let's return to the problem of getting dressed.  Suppose that you have
an unlimited number of robotic assistants.  Each robot can add one
garment in one time step, subject to the ordering constraints.  How
should the various tasks be scheduled?  Here is one possibility:

\mfigure{!}{2in}{getting-dressed2}

\noindent All tasks are completed in four steps using this schedule.
There is no hope of doing better, because there is a sequence of four
tasks (underwear, pants, belt, and jacket), each of which must be
completed before the next one can begin.

Let's generalize these ideas.  In a poset $(S, \preceq)$:

\begin{itemize}

\item a \term{chain} is a subset $C \subseteq S$ such that for all $x,
y \in C$, either $x \preceq y$ or $y \preceq x$.

\item an \term{antichain} is a subset $A \subseteq S$ such that for
all $x, y \in A$ with $x\ne y$, neither $x \preceq y$ nor $y \preceq x$.

\end{itemize}

\noindent So \textit{at most one} task in a chain can be completed
during a step, but \textit{all} the tasks in an antichain can be
completed in the same step.  Thus, the number of steps required to
complete a poset of tasks is \textit{at least} the size of the largest
chain.  The following theorem says that this number of steps is
sufficient as well.

\begin{theorem}
Let $(S, \preceq)$ be a poset in which the largest chain has size $t$.
Then $S$ can be partitioned into antichains $A_1, \ldots, A_t$ such $x
\in A_i$ precedes a different element $y \in A_j$ only if $i < j$.
\end{theorem}

Looking back, our schedule for getting dressed was a partition of all
tasks into four such antichains.  Given such a partition, we can do
the tasks in $A_1$ during the first step, tasks in $A_2$ during the
second step, and so forth, and complete all of the tasks within $t$
steps.

\begin{proof}
Assign $x \in S$ to set $A_i$ where $i$ is the size of the longest
chain with $x$ as a maximal element.

Suppose $x \in A_i$ precedes a different element $y \in A_j$; that is,
$x \preceq y$.  There is a chain of length $i$ with $x$ as a maximal
element by definition of $A_i$.  Adding $y$ gives a chain of length $i
+ 1$ with $y$ as a maximal element.  Thus, $j$, the size of the
longest chain with $y$ as a maximal element, is at least $i + 1 > i$.

As a special case, no element $x \in A_i$ precedes a different element
$y \in A_i$, so the sets $A_i$ are antichains.
\end{proof}
}

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

\instatements{\newpage}

\begin{problem}
Here is prerequistite information for some MIT courses:
%
\begin{align*}
18.01 & \to 6.042 & 18.01 & \to 18.02 \\
18.01 & \to 18.03 & 6.046 & \to 6.840 \\
8.01 & \to 8.02 & 6.001 & \to 6.034 \\
6.042 & \to 6.046 & 18.03, 8.02 & \to 6.002 \\
6.001, 6.002 & \to 6.003 & 6.001, 6.002 & \to 6.004 \\
6.004 & \to 6.033 & 6.033 & \to 6.857
\end{align*}
\end{problem}

\bparts

\ppart Draw a Hasse diagram for the corresponding partially-ordered
set.  (A \term{Hasse diagram} is a way of representing a poset $(A,
\preceq)$ as a directed acyclic graph.  The vertices are the element
of $A$, and there is generally an edge $u \to v$ if $u \preceq v$.
However, self-loops and edges implied by transitivity are omitted.)
You'll need this diagram for all the subsequent problem parts, so be
neat!

\solution[\vspace{3in}]{

\mfigure{!}{2.5in}{rec9-hasse}
}

\ppart Identify a largest chain.  (A \term{chain} in a poset $(S,
\preceq)$ is a subset $C \subseteq S$ such that for all $x, y \in C$,
either $x \preceq y$ or $y \preceq x$.)

\solution[\vspace{0.5in}]{
\[
8.01 \preceq 8.02 \preceq 6.002 \preceq 6.004 \preceq 6.033 \preceq 6.857
\]
}

\ppart Suppose that you want to take all the courses.  What is the
minimum number of terms required to graduate, if you can take as many
courses as you want per term?

\solution[\vspace{0.5in}]{Six terms are necessary, because at most one
course in the longest chain can be taken each term.  Six terms are
sufficient by a theorem proved in lecture.}

\ppart Identify a largest \textbf{antichain}.  (An \term{antichain} in
a poset $(S, \preceq)$ is a subset $A \subseteq S$ such that for all
$x, y \in C$ with $x\ne y$, neither $x \preceq y$ nor $y \preceq x$.)

\solution[\vspace{0.5in}]{There are several five-element antichains.
One is:
%
\[
\set{18.02, 6.042, 18.03, 8.01, 6.001}
\]
 }

\ppart What is the maximum number of classes that you could possibly
take at once?

\solution[\vspace{0.5in}]{Classes you are taking simultaneously must
form an antichain, so you can take at most five at once.}

\ppart Identify a topological sort of the classes.  (A
\term{topological sort} of a poset $(A, \preceq)$ is a total order of
all the elements such that if $a_i \preceq a_j$ in the partial order,
then $a_i$ precedes $a_j$ in the total order.)

\solution[\vspace{1in}]{Many answers are possible.  One is 18.01,
8.01, 6.001, 18.02, 6.042, 18.03, 8.02, 6.034, 6.046, 6.002, 6.840,
6.004, 6.003, 6.033, 6.857.}

\ppart Suppose that you want to take all of the courses, but can
handle only two per term.  How many terms are required to graduate?

\solution[\vspace{1.5in}]{ There are 15 courses, so at least 8 terms
are necessary.  The schedule below shows that 8 terms are sufficient
as well:

\begin{center}
\begin{tabular}{rcc}
1: & 18.01 & 8.01 \\
2: & 6.001 & 18.02 \\
3: & 6.042 & 18.03 \\
4: & 8.02 & 6.034 \\
5: & 6.046 & 6.002 \\
6: & 6.840 & 6.004 \\
7: & 6.003 & 6.033 \\
8: & 6.857
\end{tabular}
\end{center}
}

\ppart What if you could take three courses per term?

\solution[\vspace{1.5in}]{In part (c) we argued that six terms are
required even if there is no limit on the number of courses per term.
Six terms are also sufficient, as the following schedule shows:

\begin{center}
\begin{tabular}{rccc}
1: & 18.01 & 8.01 & 6.001 \\
2: & 6.042 & 18.03 & 8.02 \\
3: & 18.02 & 6.046 & 6.002 \\
4: & 6.004 & 6.003 & 6.034 \\
5: & 6.840 & 6.033 \\
6: & 6.857 \\
\end{tabular}
\end{center}
}

\ppart Stanford's computer science department offers $c$ courses,
limits students to at most $l$ classes per term, and has its own
complicated prerequisite structure.  Describe two different lower
bounds on the number of terms required to complete all the courses.
One should be based on your answers to parts (b) and (c) and a second
should be based on your answer to parts (g).

\solution[\vspace{0.75in}]{One lower bound is the length of the
longest chain and another is $\lceil c / l \rceil$.}

(\term{Brent's Theorem} implies that the \textit{sum} of these two
lower bounds is an \textit{upper bound} on the number of terms
required to complete all courses.  You'll prove Brent's theorem for
homework.)

\eparts

\end{document}
