\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 
\usepackage{textcomp} % to get \textcent
\usepackage{epsfig}

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

\newcommand{\ra}{\rightarrow}

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


% source: spring00 ps3; F02 CP3W
% topics: critical path, DAGs, topological sort

\begin{problem} A pair of 6.042 TAs, Zardosht and Ching,
have decided to devote some of their spare time this term to
establishing dominion over the entire galaxy.  Recognizing this as an
ambitious project, they worked out the following table of tasks on the
back of Ching's copy of the lecture notes.

\begin{enumerate}
\item {\bf Devise a logo} and cool imperial theme music - 8 days.
\item {\bf Build a fleet} of Hyperwarp Stardestroyers out of eating
  paraphernalia swiped from Lobdell - 18 days.
\item {\bf Seize control} of the United Nations - 9 days, after task \#1.
\item {\bf Get shots} for Zardosht's cat, Emilios - 11 days, after task \#1.
\item {\bf Open a Starbucks chain} for the army to get their caffeine - 10 
days, after task \#3
\item {\bf Train an army} of elite interstellar warriors by dragging
people to see {\em The Phantom Menace} dozens of times - 4 days, after
tasks \#3, \#4, and \#5.
\item {\bf Launch the fleet} of Stardestroyers, crush all sentient
alien species, and establish a Galactic Empire - 6 days, after tasks \#2 and
\#6.
\item {\bf Defeat Microsoft} - 8 days, after tasks \#2 and \#6.
\end{enumerate}

\begin{problemparts}
\problempart Express the information in the task list using some type
of graph (label the vertices to reflect task lengths).

\solution{%
    The information in the table is represented in the
    Figure~\ref{fig:tasks} in the form of a directed acyclic graph.
    Each vertex represents a task, and the weight of a vertex is the
    completion time.  Each directed edge represents a dependency
    between tasks.

    \begin{figure}[htbp]
    \begin{center}
    \unitlength=0.047pt
    \input{figures/ps4-1.latex}
    \end{center}
    \caption{Graph representing the task precedence constraints.}
    \label{fig:tasks}
    \end{figure}
}

\problempart Give some valid order in which the tasks might be
completed.

\solution{
We can easily find several of them. The most natural one is valid, too:
\#1, \#2, \#3, \#4, \#5, \#6, \#7, \#8.
}

\bigskip

\noindent Zardosht and Ching want to complete all these tasks in the
shortest possible time. However, they have agreed on some constraining
work rules.
\begin{itemize}

\item Only one person can be assigned to a particular task; they can
not work together on a single task.

\item Once a person is assigned to a task, that person must work
exclusively on the assignment until it is completed.  So, for example,
Zardosht cannot work on building a fleet for a few days, run get shots
for Emilios, and then return to building the fleet.

\end{itemize}

% For each task, the table above lists the time required for completion
% and which other tasks must be finished before the given task is begun.

\problempart Zardosht and Ching want to know how long conquering the
galaxy will take.  Ching suggests dividing the total number of days of
work by the number of workers, which is two.  What lower bound on the time
to conquer the galaxy does this give, and why might the actual time
required be greater?

\solution{
\begin{eqnarray*}
\frac{8 + 18 + 9 + 11 + 10 + 4 + 6 + 8}{2} & = & 37 \text{ days}
\end{eqnarray*}

If working together and interrupting work on a task were permitted,
then this answer would be correct.  However, the rules may prevent
Zardosht and Ching from both working all the time.}

\problempart Zardosht proposes a different method for determining the
duration of their project.  He suggests looking at the duration of
the ``critical path'', the most time-consuming sequence of tasks
such that each depends on the one before.  What lower bound does this
give, and why might it also be too low?

\solution{The longest sequence of tasks is devising a logo (8 days),
seizing the U. N. (9 days), opening a Starbucks (10 days), training
the army (4 days), and then defeating Microsoft (8 days).  Since these
tasks must be done sequentially, galactic conquest will require at
least 39 days.

If there were enough workers, this answer would be correct; however,
with only two workers, Zardosht and Ching may be unable to make progress
on the critical path every day.}

\problempart What is the minimum number of days that Zardosht and Ching
need to conquer the galaxy?  No proof is required.

\solution{
40 days.  Tasks could be divided as follows:

Ching: \#1 (days 1-8), \#3 (days 9-17), \#4 (days 18-28), \#8 (days
33-40).

Zardosht: \#2 (days 1-18), \#5 (days 19-28), \#6 (days 29-32), \#7 (days
33-38).  
}
\end{problemparts}
\end{problem} 

\instatements{\newpage}
\begin{problem}

\begin{problemparts}

\problempart What are the maxim\emph{al} and minim\emph{al} elements, if
any, of the set, $\naturals$, of all natural numbers under divisibility?
Is there a minim\emph{um} or maxim\emph{um} element?

\solution{The minimum (and therefore unique minimal) element is 1 since 1
divides all natural numbers. The maximum (and therefore unique maximal)
element is 0 since all numbers divide 0.}

\problempart What are the minimal and maximal elements, if any, of the set
of integers $\ge 2$ under divisibility?

\solution{All prime numbers are minimal elements, since no numbers divide
them.  Since there is more than one minimal element, there can't be a
minimum element.

There is no maximal element, because for any $n\ge 2$, there is  a
``larger'' number under the divisibility partial order, namely,
$mn$, for any $m > 1$.}

\ppart Prove that for $\naturals$ partially ordered under divisibility,
the greatest lower bound (glb) of two numbers is precisely their $\gcd$.

\solution{
  To show the greatest lower bound of two numbers, $a$ and $b$, is its greatest common divisor, we must show two things.
  First, we must show that the greatest common divisor is a lower bound, and second, we must show that
  all other lower bounds of $a$ and $b$ precede the greatest common divisor in the partial order.

  Let the greatest common divisor of $a$ and $b$ be $n$. By definition of a greatest common divisor, we know 
  $n$ divides $a$ and $n$ divides $b$, thus $n$ is a lower bound.

  Now we must all other lower bounds precede $n$ in the partial order. Note that this does not mean we
  must show all other lower bounds are less than $n$, but rather, all other lower bounds \emph{divide} $n$, because
  the partial ordering we are considering is divisibility.

  To show this, take an arbitrary lower bound $m \neq n$. Given $m$ divides $a$ and $m$ divides $b$, we must show $m$ divides $n$.
  From lecture a few weeks ago, we know $n$ can be represented as an integer linear combination of $a$ and $b$. That is, there
  exists integers $x$ and $y$ such that $n = ax + by$. If $m$ divides $a$, it divides $ax$. If $m$ divides $b$, it divides $by$.
  Thus, if $m$ divides $a$ and $b$, it divides $n = ax + by$.


}

\end{problemparts}
\end{problem}


\instatements{\newpage}
\begin{problem}

\bparts

\ppart Write out a careful proof showing that the younger-shorter
relation---call it $\preceq$---is indeed a partial order on any set of
birthday/height pairs.  You may assume that the ``younger than'' relation
on birthdays is a total order and likewise for the ``shorter than''
relation on heights.

\ppart
Describe a sequence consisting of the integers from 1 to 10,000 in some
order so that there is no increasing or decreasing subsequence of size
101.
\solution{\[
[100 \ra 1][200 \ra 101][300 \ra 201]...[10,000 \ra 9901]
\]
}

\eparts

\end{problem}


\begin{problem}
\bparts
\ppart
What is the size of the longest chain that is guaranteed to exist in any
partially ordered set of $n$ elements?  What about the largest antichain?

\solution{
Chain size is 1 in the ``discrete'' partial order in which every two
distinct elements are incomparable.  Antichain size is 1 if the partial
order is total.
}

\ppart Describe a partially ordered set than has no minimal or maximal
elements.

\solution{$\integers$, $\reals$, etc.}

\ppart Describe a partially ordered set than has a \emph{unique minimal}
element, but no minimum element.

\solution{
$\integers \union{i}$ where $i$ is a root of $-1$, under the usual order
$\integers$.  So $i$ is incomparable to everything but itself, and is
therefore minimal.
}

\ppart Prove that every partially ordered finite set has a minimal
element.
\solution{
  We shall prove this by induction on the number of elements in the finite set. Let $P(n)$ be the proposition
  ``All partially ordered sets
  containing exactly $n$ elements have a minimal element.''
  Let $n$ be the number of elements
  in the set. For the base case $n=1$, let $x$ be the only element in the set. Clearly, $x$ is a minimal element.
  

  Now consider the inductive step. Given $P(n)$, we must show $P(n+1)$. Consider an arbitrary partially ordered set, $S$
  with $n+1$ elements, $a_1, a_2, \ldots, a_n, a_{n+1}$. Consider the set $S'$ containing elements $a_1, \ldots, a_n$. By
  the inductive hypothesis, we know some element, $m$ exists in $S'$ such that $m$ is a minimal element. Compare $m$ and $a_{n+1}$.
  If $m \preceq a_{n+1}$ or $m$ and $a_{n+1}$ are incomparable, then $m$ is a minimal element of $S$. If $a_{n+1} \preceq m$, then $a_{n+1}$
  is a minimal element of $S$. Thus, in all cases, $S$ has a minimal element. 
}


\eparts
\end{problem}

\instatements{\newpage}
\section*{Appendix}

\begin{definition*}
Let $\preceq$ be a weak (reflexive) partial order on a set, $A$.
\begin{itemize}

\item An element $a \in A$ is a \emph{lower bound} for a subset, $S
\subseteq A$ iff $a \preceq s$ for every $s \in S$.  Similarly, an element
$a \in A$ is an \emph{upper bound} for a subset, $S \subseteq A$ iff $s
\preceq a$ for every $s \in S$.

\item An element $a \in A$ is the \emph{minimum} element iff $a$ is a
lower bound on $A$.  Similarly, an element $a \in A$ is the \emph{maximum}
element iff $a$ is an upper bound on $A$.

\item An element $a \in A$ is the \emph{greatest lower bound (glb)} of a
subset, $S \subseteq A$ iff $a$ is a lower bound for $S$, and if $b \in A$
is also a lower bound for $S$, then $b \preceq a$.  Similarly for
\emph{least upper bound (lub)}.

\item An element $a \in A$ is \emph{minimal} iff there is no element in
$A$ that is $\preceq a$ except $a$ itself.  Similarly, an element
$a \in A$ is \emph{maximal} iff there is no element in $A$ that is
$\succeq a$ except $a$ itself.

\item Elements $a,b \in A$ are \emph{comparable} iff either $a \preceq b$
or $b \preceq a$.  Two elements are \emph{incomparable} iff they are not
comparable.

\item A subset, $S \subseteq A$ is \emph{totally ordered} iff every
two distinct elements in $S$ are comparable.

\item A \emph{chain} is a totally ordered subset of $A$.  

\item An \emph{antichain} is a subset of $A$, such that no two elements in
it are comparable.

\end{itemize}

\end{definition*}

\end{document}
