\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 tasks
and constraints. Assume that each task takes the same amount of time
(1 hour) to do.

% 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 situation can be modelled as a directed graph.
Describe what the nodes are and what the directed edges represent.

\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 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 hours it will take to complete all $n$
tasks correctly if 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 hours required to
complete all $n$ tasks correctly if Radhika can enlist TAs to do the
tasks in parallel and each task takes 1 hour.  Assume that a single TA
can do an unlimited number of tasks, but no more than one per
hour. Fill in the 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 may need as many as \brule{1.2cm} TAs.  But even in the best case, she
knows she will need at least \brule{1.2cm} TAs.

\solution{$n-t+1$, $n/t$.  Worst case all of the tasks form one long
antichain, except for the tasks that are already part of the chain.
However even in the best case, some antichain will end up $\geq n/t$
elements, because there are $n$ tasks there is no way we can make all
antichains have fewer than $n/t$ elements.}
\end{problemparts}

\end{problem}


