\documentclass[11pt]{article}
\usepackage{fullpage,amsmath,hyperref,graphicx,xcolor}
\newcommand{\eps}{\varepsilon}
\newcommand{\fig}[2]{\begin{figure}[h]\begin{center}%
\includegraphics[scale=#2]{#1.pdf}\end{center}%
\end{figure}}
\newlength{\mylength}
\newcommand{\scratch}[1]{\makebox[0in][l]{#1}\settowidth{\mylength}{#1}{\color{red}\rule[.6ex]{\mylength}{1pt}}}
\begin{document}
\begin{center}\Large\bf
CS/ECE 374 A (Spring 2024)\\
{\Large Homework 7} (due Mar 21 Thursday at 10am)
\end{center}
\medskip\noindent
{\bf Instructions:} As in previous homeworks.
\begin{description}
\bigskip
\item[Problem 7.1:]
%cover trees by paths
Given a binary tree $T$ with $n$ nodes,
we want to find a collection of paths, each with 1, 2, or 3 nodes,
such that every node is in exactly one path, while minimizing
the number of paths.
\fig{hw7fig1}{0.8}
\vspace{-2ex}
Design and analyze an efficient dynamic programming algorithm for computing the minimum
number of paths.
Include the following steps: (i) first define your subproblems precisely, (ii)~then
derive the recursive formula (including base cases) with brief justifications,
(iii)~specify a valid evaluation order, and (iv)~analyze the running
time. For this problem, you do not need to write pseudocode if your recursive formula
and evaluation order are described sufficiently clearly. And you do not need to
output the optimal collection of paths.
(Hint: the example on independent sets in trees that will be covered in 3/7 Thursday's lecture
might be helpful. See also Problem Old.7.1 in \href{https://courses.grainger.illinois.edu/cs374al1/sp2024/secure/past_hw7.pdf}{Past HW7}
for another similar example.)
%\newpage
\bigskip
\item[Problem 7.2:]
%perfectly separable rectangles
An (axis-parallel) rectangle in 2D can be represented
by four real numbers: the min and max $x$-coordinates and the min and max $y$-coordinates.
We define the notion of a \emph{perfectly separable} set of rectangles inductively as follows:
\begin{itemize}
\item A set with just one rectangle is perfectly separable.
\item If $S_1$ is a perfectly separable set and $S_2$ is a perfectly separable set and
there is a vertical line $\ell$ such that all rectangles of $S_1$ are completely to the left of $\ell$
and all rectangles of $S_2$ are completely to the right of $\ell$, then $S_1\cup S_2$ is perfectly separable.
\item If $S_1$ is a perfectly separable set and $S_2$ is a perfectly separable set and
there is a horizontal line $\ell$ such that all rectangles of $S_1$ are completely below $\ell$
and all rectangles of $S_2$ are completely above $\ell$, then $S_1\cup S_2$ is perfectly separable.
\item Only sets satisfying the above are perfectly separable.
\end{itemize}
\newpage
In the examples below, (i) is perfectly separable, but (ii) is not.
\fig{hw7fig2}{0.8}
\vspace{-2ex}
(Remark: It has been conjectured that any set of $n$ non-overlapping rectangles contains
a subset of at least $n/c$ rectangles that is perfectly separable, for some constant $c$.
This conjecture is still open\ldots)
Consider the following problem: given a set $S$ of $n$ (possibly overlapping) rectangles,\footnote{
You may assume that all $x$- and $y$-coordinates are distinct.
}
find a largest subset $T\subseteq S$ such that $T$ is perfectly separable.
Design and analyze a polynomial-time dynamic programming algorithm to compute the optimal size.
Include the following steps: (i) first define your subproblems precisely, (ii)~then
derive the recursive formula (including base cases) with brief justifications,
(iii)~specify a valid evaluation order, and (iv)~analyze the running
time. For this problem, you do not need to write pseudocode if your recursive formula
and evaluation order are described sufficiently clearly. And you do not need to
output the optimal subset.
\fig{hw7fig2_2}{0.8}
\vspace{-2ex}
(Hint: create $O(n^4)$ subproblems: for each $x,x',y,y'$, define a subproblem restricted to
input rectangles that are inside
$[x,x']\times [y,y']$\ldots)
(Another Hint: As you can see from the pictures above and the recursive
definition of a perfectly separable set, a feasible solution has a binary-tree-like structure where
each node corresponds to a vertical or horizontal cut. The example in \href{https://courses.grainger.illinois.edu/cs374al1/sp2024/labs/lab_08_b.pdf}{Lab 8b} and Problem Old.7.1 in \href{https://courses.grainger.illinois.edu/cs374al1/sp2024/secure/past_hw7.pdf}{Past HW7} also involve a binary-tree-like structure, and so might be helpful.)
\end{description}
\end{document}