\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; Radhika can only drink coffee (a necessity
for any exam) after someone has purchased coffee beans from Au Bon Pain,
\dots.  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 followed by 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 the necessary 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 as many as $t$ consecutive
tasks, but only one at a time.  Let $n$ and $t$ be \textbf{fixed}, that
is, you can assume $1 \leq t \leq n$, but not any particular values of $n$
or $t$.  Fill the missing formulas in $n$ and $t$ in the two blanks below:

   \begin{quote}
   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{1in} TAs.  But even in the best case, she
   knows she will have to have \brule{1in} TAs.
   \end{quote}

\solution{$n-t+1$, $\ceil{n/t}$.

The worst case for number of TA's needed to achieve time $t$ occurs when
there is a single chain of $t$ tasks, all of the other tasks are pairwise
incomparable, and the second element of the chain (if any) depends on each
of these other tasks.  So to achieve time $t$, all the $n-t$ tasks not in
the chain, as well as the first task in the chain, have to be done in
parallel in the first time unit.

The best case is when there is a single chain of $t$ tasks, and the
remaining tasks are pairwise incomparable.  The schedule that finishes in
time $t$ using the minimum number of TA's assigns an equal number of tasks
to be done in each time unit.  Under this schedule, at most $\ceil{n/t}$
TA's perform parallel tasks.
}

\end{problemparts}

\end{problem}


