        \problemdata       % Takes 5 *mandatory* arguments
        {galaxy-dom}             % latex-friendly label for the prob.
        {relations}  % The topic(s) of the problem content.
        {}               % Source (if known)
        {F01 tut4-1, S00 PS3} %Usage (list ones you are aware of).
        {}        % Last revision info (author, date).

\begin{problem}
A pair of 6.042 students, Eleni and Paris,
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 Paris' copy of the notes for tutorial 3.

\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 Eleni'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}

\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}
%      \centerline{\resizebox{!}{3.0in}{\includegraphics{figures/ps4-1.latex}}}
    \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

Eleni and Paris 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,
Eleni 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 Eleni and Paris want to know how long conquering the
galaxy will take.  Paris 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
Eleni and Paris from both working all the time.}

\problempart Eleni proposes a different method for determining the
duration of their project.  She 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, Eleni and Paris may be unable to make progress
on the critical path every day.}

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

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

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

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