\documentclass[11pt, twoside]{article}

\input{macros-course}

\newcommand{\nand}{|}
\renewcommand{\implies}{\longrightarrow}

\askaboutsolutions

\begin{document}
\pset{4}{September 26, 2000}{2:35pm in lecture, October 3, 2000}

\textbf{Be sure to indicate your TA's name clearly on the solutions
your turn in}.

-----------------------------------------------------------------------------\\

\textbf{Self-study:  Matrices}
Read: Rosen \S 2.6 \\
Self-study problems (not to be handed in): 
Rosen \S 2.6, Exercises 1, 3, 5, 9, 13, 15, 23, 29, 31 \\

%[[[Miniquiz for tut4:  Use Exercise 29]]]

-----------------------------------------------------------------------------\\

\textbf{Reading:}
Rosen, Chapters 7 and 8 \\
% [[[This might be too much in Chapter 8---we can prune some of this
% out after I finish planning lecture 7.  We will probably not do much
% on tree-based algorithms.]]]

[[[George:  Please type out all problems completely.]]]

\medskip
\begin{problems}

\problem
% Task scheduling or Dilworth
At last count, our 6.042 class contains 180 students.
Prove that the class must contain either:
(a) A set $S$ of 15 students such that, if they line up in size
places, they are also arranged in increasing order of age,
or
(b) A set $T$ of 13 students such that, if they line up in size
places, they are also arranged in decreasing order of age.

%[[[The idea here is supposed to be similar to the increasing sequence
%or decreasing sequence example that is suppressed in the lecture
%notes, under Dilworth's theorem material.  Order the students in the
%entire class by height.  Then use the argument about increasing or
%decreasing sequence.]]]

\problem
% digraphs, path counting and matrices
Rosen 7.4, problem 11 but change the graph in Exercise 2 at least a
little (because problem 11 has a solution in the back of Rosen).
Type in the new problem.
Also, we don't need 6 parts---maybe just three, the number of paths of
length 3, 5, and 7

\problem
% Digraphs
An {\em Euler path\/} in a digraph $G$ is a path that traverses all the
edges of $G$, each edge exactly once.  Unlike an Euler circuit, it
need not end up at the same vertex where it started.

Say whether each of the following digraphs has an Euler path, an
Euler circuit, both, or neither.
Justify your answers by exhibiting the circuits and paths that you say
exist, and proving that the others don't exist.

[[[Put the actual graphs here, without giving them the citation from
Rosen.]]]

\bparts
\ppart
[[[Digraph from Rosen section 7.5 ex. 24]]]
\ppart
[[[Digraph from Rosen section 7.5 ex. 26]]]
\ppart
[[[Digraph from Rosen section 7.5 ex. 28]]]
\eparts

\problem
% graph coloring
For each of the following graphs, (a) find the chromatic number, and
(b) say whether it is possible to decrease the chromatic number by
removing a single vertex and all edges incident with it.
Justify your answers.
\bparts
\ppart
The graph in Rosen Section 7.8, exercise 4.
\ppart
The graph in Rosen Section 7.8, exercise 6.
\ppart
The graph in Rosen Section 7.8, exercise 8.
\eparts
%[[[George:  You might want to reduce this, e.g., to 2 parts instead
%of 3.]]]

\problem 
% connectivity
Prove that in any simple undirected graph, there is a path from any
vertex of odd degree to some other vertex of odd degree.

\problem
Euler or Ham. circuits in undirected graphs
Rosen section 7.5, exercise 44.

\problem
% trees
%Rosen section 8.1, exercise 18
Either draw a full $m$-ary tree with $76$ leaves and height $3$ where
$m$ is a positive integer, or show that no such tree exists.


\problem 
% trees
[[[I'm not yet sure what I'm going to cover on trees.  Haven't
finished L07.  Possibilities are:  
Decision trees, which could be covered by Rosen 8.2 exercise 8.
Spanning trees, which could be covered by Rosen 8.5 exercise 12 (b).
\end{problems}
\end{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

tutorial4:

1. Course scheduling:
Leftover problem from tut3

\problem \textbf{Scheduling Courses}
% source: fall98/tutorials/H19-rec4.tex, beginning

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!]
	%graphic is from  /a/class/6.042/spring00/archive/lectures/
 \centerline{\resizebox{!}{2.0in}{\includegraphics{../handouts/figures/dag}}}

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

\problempart What's the length of a critical path; find such a path.
\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{
\medskip
\textbf{Solution:}\\
The answer is suggested by the way Figure~\ref{fig:dag} is drawn.
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, there is no way to finish in fewer than six terms, since each
term the student can take at most one course in the six-course sequence
18.01, 18.03, 6.002, 6.004, 6.033, 6.857.  Notice that this sequence
constitutes the longest directed path in the graph.
}

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

2. % Digraphs
Show that every tournament graph has a Hamiltonian path.
[[[This should be a quick exercise, basically deciphering definitions
and reviewing a previous proof done in tutorial, about tournaments.
I think it's the same question as constructing a ``nice'' ordering.]]]

3. % Undirected graphs, wrong proof
Problem 1 from Spring 2000 tutorial 4 (about line graphs)
[[[As an alternative, there's a cute set of proofs about ``tangled''
and ``mangled'' graphs.  I think this was used last spring also, but
in a pset instead of tutorial.  Take a look and see which you like better.]]]


4. [[[Something about trees?]]]






