\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.

Assume that each task takes the same amount of time (one 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] Describe how you would model this situation as a directed
graph. In particular, describe what the nodes are and what the edges
represent.

\solution[\vspace*{3cm}]{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}
For each of the statements, choose the relational term that best
corresponds to the statement and write its number in the blank space.

\begin{problemparts}
\parbox{5in}{ \problempart[1] A set of tasks that do not depend on
each other.}
\hspace*{1cm}\brule{1cm}
\solution{5}

\parbox{5in}{ \problempart[1] 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.}
\hspace*{1cm}\brule{1cm}
\solution{2}

\parbox{5in}{\problempart[2] 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.}
\hspace*{1cm}\brule{1cm}
\solution{8}

\textbf{Relational Term Choices:} (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.

\vspace*{.5cm}

\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. Assume that a single TA can do an unlimited number
of tasks, but no more than one per hour. \newline
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 less $n/t$ elements}
\end{problemparts}
\end{problem}


