\problemdata                                                             
        {Scheduling Courses} % latex-friendly label for the prob.
        {DAGS, critical paths} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Tutorial 4, 1; F98, Rec. 4} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
We consider a simple kind of scheduling problem --- for MIT courses with
prerequisites.  The problem is to determine how a student could complete
all of the courses in the fewest terms, under the simplifying, if
unlikely, assumption that there is no limit on the number of courses a
student can take in a term as long as their prerequisites have all been
met.  We model this problem with a digraph.  An example is shown in
Figure~\ref{fig:dag}.

\begin{figure}[htbp!]
 \centerline{\resizebox{!}{2.0in}{\includegraphics{dag.eps}}}

  \caption{This is a picture of a directed acyclic graph.  Vertices
    are labeled with course numbers.  An edge from $u$ to $v$
    indicates that course $u$ is a prerequisite for course $v$.}

  \label{fig:dag}
\end{figure}

\begin{problemparts}

\problempart What's the length of a critical path; find such a path.

\solution{
The sequence 18.01, 18.03, 6.002, 6.004, 6.033, 6.857 constitutes
a critical path since it is the longest directed path in the graph.}

\problempart 
How many terms are necessary and sufficient to complete
all of the courses in Figure~\ref{fig:dag}, assuming prerequisites are
observed, but course load is no issue? Prove your answer (both
necessary and sufficient).

\solution{
The answer is suggested by the way Figure~\ref{fig:dag} is drawn---each
horizontal row is an antichain.
Each term the student could take all the courses in a horizontal row,
starting with the first row and working down.  All of the courses in
each row are incomparable, and all the necessary prerequisites are in
previous rows.  Since there are six rows, the student can finish in
six terms. Furthermore, since there is a critical path of length six,
there is no way to finish in less than six terms.}

%\problempart Show that there is a schedule for taking courses
%which achieves the minimum number of terms, $t$.  
%the previous question includes this direction

%\solution{
%\medskip
%\textbf{Solution:}\\
%    The solution to the previous part implies that $t$ terms are
%    sufficient.  In term $i$, the student should take the set of
%    courses in the $i$th block.  Since the edges into any block come
%    from an earlier block, all the prerequisites of courses in a block
%    have been taken by the time the block is scheduled to be taken.
%    And since the blocks partition the set of all courses, the student
%    will complete every course.
%  }      
  
\end{problemparts}
\end{problem}
                                 