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

\input{/pub/www/classes/6.042/fall99/inputs/macros-course}


\newcommand{\solution}[1]{\smallskip \textbf{Solution:} #1 \textbf{endsoln}}

\begin{document}

\tutn{9}{10/14/99}{October 11, 1999}

\begin{problems}


\problem \textbf{ Conquering the Galaxy.} A pair 6.042 students, Wendy and
Steve, 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 Steve's copy of Team Problems 9.

\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
paraphenalia swiped from Lobdell - 18 days.
\item {\bf Seize control} of the United Nations - 9 days, after task \#1.
\item {\bf Get shots} for Wendy's cat, Muffy - 7 days, after task \#1.
\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 and \#4.
\item {\bf Launch the fleet} of Stardestroyers, crush all sentient
alien species, and establish a Galactic Empire - 6 days, after tasks \#2 and
\#5.
\item {\bf Defeat Microsoft} - 8 days, after tasks \#2 and \#5.
\end{enumerate}

Wendy and Steve want to complete all these tasks in the shortest possible
time.  Of course they can't do a task until the tasks which come before it
are done.  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.

\begin{problemparts}
\problempart What type of graph seems appropriate to express the
information in this task list?  Draw it.

\solution{ The information in the table is represented below 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 dependence between tasks.  (The diagram has a mistake: the edge from
``build fleet'' to ``sieze control'' should be omitted.)

\bigskip
\centerline{\resizebox{!}{3.0in}{\includegraphics{conquest.eps}}}
\bigskip
}

\problempart Steve suggests dividing the total number of days of work by
two, because the two of them will both be working on the project.  What
lower bound on the time to conquer the galaxy does this give?  How could
it be achieved?

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

As long as they both are always busy on tasks, this answer would be
correct.  By working together on whatever tasks can be done, they can
accomplish this.}

\eparts

In fact, to avoid arguments, they have agreed on some work rules.

\begin{itemize}

\item Only one person can be assigned to a particular task; they cannot
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,
Wendy cannot work on building a fleet for a few days, run get shots
for Muffy, and then return to building the fleet.

\end{itemize}

\bparts

\problempart Wendy proposes now a different method for determining the
duration of their project.  She suggests looking at the duration of the
``critical path'', the longest sequence of tasks such that each depends on
the one before.  What lower bound does this give?  Why is it too low?

\solution{The longest sequence of tasks is devising a logo (8 days),
seizing the U. N. (9 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 29 days.

If there were enough workers, this answer would be correct; however, with
only two workers, Wendy and Steve won't be able to make progress on the
critical path every day because they sometimes will both have to work on
prerequisite tasks off the critical path.}

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

\solution{
Galactic conquest will require a minimum of 36 days.
}

\end{problemparts}

\problem \textbf{Counting Numbered Trees.}  A \emph{numbered tree} is a
tree whose vertex set is $\set{1,2,\dots,n}$ for some $n \geq 2$.  We
define the \emph{code} of the numbered tree to be a sequence of $n-2$
integers from 1 to $n$ obtained by the following recursive process:
\begin{quotation}\noindent
If $n=2$, stop---the code is the empty sequence.  Otherwise, write down
the \emph{father} of the largest leaf, delete this \emph{leaf}, and
continue the process on the resulting smaller tree.
\end{quotation}
For example, the codes of a couple of numbered trees are shown in the
attached figure.

\bparts

\ppart Describe a procedure for reconstructing a numbered tree from its
code.

\solution{

The key observation is that, given a code of length $n-2$, the numbers
between 1 and $n$ which \emph{do not appear} in the code must be leaves of
the tree.  Hence, the largest missing number is a leaf attached to the
first number of the code.  The rest of the tree can now be reconstructed
by deleting the first number in the code, henceforth ignoring the largest
leaf, and proceeding recursively on the rest of the code.  (We're using
the obvious fact that what's left after deleting a leaf from a tree is
another tree.)

More precisely, the reconstruction procedure applies to any finite tree
whose vertex set consists of distinct real numbers.  The procedure takes
\emph{two} parameters: the vertex set $V \subset \reals$ and a length
$\card{V}-2$ ``code'' sequence, $S$, whose elements are numbers in $V$.
If $l$ is the largest number in $V$ which does not appear in $S$, and $f$
is the first element of $S$, then the reconstructed tree is obtained by
adding edge $(l,f)$ to the tree reconstructed by calling the procedure
recursively with first argument $V-\set{l}$ and second argument equal to
the code obtained by erasing the initial $f$ from $S$.  The procedure
terminates when $\card{V}=2$, returning the edge between the two numbers
in $V$.

To justify the key observation, note that any vertex that gets deleted by
the process and was not a leaf to begin with, must have been the father of
a previously deleted leaf, which means it would appear in the code.  So
the missing integers must have been leaves to begin with or must be one of
the two undeleted vertices left when the coding process terminates.  But
by the end of the process the two remaining vertices are leaves, and if
they weren't leaves to begin with, they must have become leaves by having
their sons deleted, which means they would not have been missing from the
code.  So the two vertices remaining at the end must also have been leaves
ofthe original tree.
}

\ppart How many numbered trees with $n$ vertices are there?

\solution{

$n^{n-2}$.

The coding process on trees of length $n$ and the tree reconstruction
procedure from codes of length $n-2$ define mutually inverse functions, so
each is a bijection.  Therefore the number of numbered trees with $n$
vertices is the same as the number of length $n-2$ sequences of integers
between 1 and $n$.  By the Product rule, this is $n^{n-2}$.}

\eparts 

\end{problems}

\end{document}


