\documentclass{pset}

\psnum{3}
\psdue{Monday, July 15}

\begin{document}
\maketitle
\standardadvice

\begin{problem}[10 points]
Problem 6.8 from the text.
\end{problem}

\begin{problem}[10 points]
Problem 4.4 from the text.
\end{problem}

\begin{problem}[15 points]
A \emph{Matryoshka box} is a set of rectangular boxes that are nested with
their faces aligned parallel. Rigorously, a Matryoshka box of cardinality $k$
is a set of boxes $b_1, \ldots, b_k$ where $b_i$ contains $b_j$ for all $i<j$.
We say a box $b_1$ contains $b_2$ if it is possible to rotate $b_2$ so that the
length of each side of $b_1$ is strictly greater than the corresponding side of
$b_2$. For example, a box with side lengths $(10, 11, 12)$ contains a box with
side lengths $(11, 10, 9)$, but not $(1, 11, 11)$. Our goal is to choose a
Matryoshka box with the maximum cardinality from a given set of boxes. Given
$n$ boxes and the lengths of their three sides, design an efficient algorithm
that finds a maximum-cardinality Matryoshka box.
\end{problem}

\end{document}
