\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CSU690}{Algorithms and Data}{Fall 2006}{13 October 2006}{10}

\begin{center}
\Large{\bf Problem Set 4 (due Tuesday, October 24)}
\end{center}

{\bf 1. (5 + 5 = 10 points) Uniqueness of MSTs when all weights are
distinct}
\begin{itemize}
\item 
Suppose $T_1$ and $T_2$ are distinct minimum spanning trees for graph
$G$.  Let $(u,v)$ be the lightest edge (smallest weight edge) among
all edges that are in $T_1$ and but not in $T_2$.  Let $(x, y)$ be any
edge that is in $T_2$ and not in $T_1$.  Show that $w(x, y) \ge
w(u,v)$.

\item
Prove that if the weights on the edges of a connected, undirected
graph are distinct, then there is a unique minimum spanning tree.
\end{itemize}

{\bf 2. (6 + 6 = 12 points) Bottleneck MSTs}

Chapter 4, Exercise 9, page 192.

{\bf 3. (2 + 10 = 12 points) Nesting boxes} 

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$ {\em nests}\/
within box $B_j$ if and only if box $B_i$ can be oriented so that it
is {\em strictly smaller\/} than box $B_j$ 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)$.

\begin{Itemize}
\item[{\bf (a)}] Describe an $O(1)$ time algorithm to determine
whether one box nests within another.

\item[{\bf (b)}] 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}$
nests inside $B_{i_{j+1}}$, $1\leq j<k$.  Design and analyze a
polynomial-time algorithm for the problem.  ({\em Hint:} One can use
either dynamic programming or express the problem as a shortest-path
problem in a suitably defined graph.)
\end{Itemize}

{\bf 4. (13 points) Word segmentation} 

Chapter 6, Exercise 5, page 316.

{\bf 5. (13 points) Defending against robot attacks}

Chapter 6, Exercise 8, page 319.
\end{document}