\begin{problem}[15]
The preparation for the 6.042 final examination has begun, and Radhika has
a set of $n$ tasks that must be completed before anyone can take the
final.  However some tasks must be completed before others.  For example,
the exam can be printed only after every occurrence of the word ``Theory
Pig'' has been replaced; the appendix can be released only after 50\% of
the problems have been written; and Radhika can only drink coffee (a
necessity for any exam) after someone has purchased coffee beans from Au
Bon Pain.  There are many such constraints among the $n$ tasks.

% Along with those $n$ tasks, she also had a set of constraints on which
% tasks must be completed before another task can start.  For example,
% exams can only be printed after she has verified the exam; the
% appendix can be released only after all the problems have been
% written; Radhika can only drink coffee (a necessity for staying up
% late to write to exam) after she has purchased coffee beans from Au
% Bon Pain. Assume that each task takes the same amount of time.

\begin{problemparts}

\problempart[5] This constrained scheduling problem can be modelled as a
directed graph.  Describe what the nodes are, and where the directed edges
go.

\solution[\vspace*{1.5in}]{Each node corresponds to a particular task, so
there are $n$ nodes.  There is a directed edge from node $a$ to node $b$ if
task $a$ must be completed before task $b$.}
\end{problemparts}

Below is a list of relational concepts and a list of definitions related
to Radhi's scheduling problem.
\begin{quote}
\textbf{Relational Concepts:} (1) Transitive Closure, (2)
Topological Sort, (3) Minimal Element, (4) Maximal Element, (5)
Antichain, (6) Maximal (Longest) Antichain, (7) Minimal (Shortest)
Chain, (8) Maximal (Longest) Chain.
\end{quote}
For each of the following three scheduling definitions, write in the blank
space the number of the relational concept that describes it.

\begin{problemparts}
\ppart[3]
\begin{itemize}

\item A set of tasks that do not depend on each other. \hfill\brule{1cm}

\solution{5}

\item A valid order in which Radhika can do the tasks if she has to do
them all by herself and she can only do one task at a
time. \hfill\brule{1cm}

\solution{2}

\item The minimum number of time units it will take to complete all $n$
tasks correctly, assuming that each task takes one time unit to do and
that Radhika can enlist an unlimited number of TAs to do the tasks in
parallel.\hfill\brule{1cm}

\solution{8}
\end{itemize}

\problempart[6] Let $t$ be the minimum number of time units required
to complete all $n$ tasks, assuming that each task takes one time unit
to do and that Radhika can enlist an unlimited number of TAs to do the
tasks in parallel.  Assume also that a single TA can do an unlimited
number of tasks, but only one per time unit. Fill in the two blanks
with formulas in terms of $n$ and $t$:

Radhika is trying to figure out how many TAs she needs to get all the
tasks done in the minimum amount of time.  She realizes that in the worst
case she will need \brule{1.2cm} TAs.  But even in the best case, she
knows she will have to have \brule{1.2cm} TAs.

\solution{$n-t+1$, $\ceil{n/t}$.  In the worst case all of the tasks
form one long antichain, except for the tasks that are already part of the
chain.  In the best case, an equal number of tasks, namely, $n/t$ (rounded
up or down), will be done in parallel in each of the $t$ time slots.  No
smaller number could suffice, because the elements done in parallel at the
$i$th time slot must be an anti-chain, so at least one of these $t$
anti-chains must have $\geq \ceil{n/t}$ elements.}

\end{problemparts}

\end{problem}


