\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{3390}{Analysis of Algorithms}{25 November 1998}{21}

\begin{center}
\Large{\bf Problem Set 4 (due December 9)}
\end{center}

\bigskip
{\bf 1. (6 points)} Exercise~24.1--3.

{\bf 2. (6 points)} Exercise~24.1--5.

{\bf 3. (12 points)} Prove that a minimum spanning tree of a graph $G$ is also a spanning
tree whose largest edge weight is minimum over all spanning trees of $G$.

{\bf 4. (8 points)} Exercise~23.3--8.

{\bf 5. (9 + 12 = 21 points)} Problem~23--1.

{\bf 6. (8 points)} Exercise~25.2--4.

{\bf 7. (16 points)} We are given a set of $n$ empty boxes $B_i=(h_i,w_i,\ell_i)$, $1\leq
i\leq n$, where $h_i$, $w_i$, and $\ell_i$ denote the height, width, and
length of box $B_i$.  Let us say that box $B_i$ ``fits inside'' box $B_j$ if
and only if box $B_i$ can be oriented so that it is {\em strictly smaller\/}
than box $B_i$ in each corresponding dimension.  For example, even though the
box $B_i=(5,1,1)$ is taller than the box $B_j=(2,6,3)$, $B_i$ can be placed
inside $B_j$ by orienting it as a $(1,5,1)$.

We would like to compute the maximum length $k$ of a sequence of boxes
$B_{i_1},\ldots,B_{i_k}$ such that $B_{i_j}$ fits inside $B_{i_{j+1}}$, $1\leq
j<k$.  Design and analyze an $O(n^2)$-time algorithm for the problem by
expressing it as a shortest-path problem in a suitably defined graph.

({\em Remark:}\/ Problem~25--2 of text is a generalization of the above
problem.  The above problem itself is a generalization of Problem~3 of Problem
Set~3 and can also be solved directly by dynamic programming.)

{\bf 8. (10 + 10 + 3 = 23 points)} Problem~25--1.

\end{document}