\documentclass[12pt]{article}%
\usepackage{374} %
\usepackage{374_extra} %
\HomeworkStart%
{7} % Homework number
{9} % Week of semester submitted
{1.21} % Version
\HWInstructionsStd{}%
\noindent%
Unless stated otherwise, for all questions in this homework involving
dynamic programming, you need to provide a solution with explicit
memoization.
\begin{questions}[start=19]
\RestoreIndent%
\item \OLDHWProblem{100}{Super{}string theory.}{%
You are given a \DFA $M = (Q,\Sigma,\delta,s,A)$ with $n$
states, where $\cardin{\Sigma}=O(1)$.
For two strings $x,y \in \Sigma^*$, the string $x$ is a
\emphi{super{}string} of $y$, if one can delete characters from
$x$ and get $y$.
Let $w$ be a given input string with $m$ characters.
\begin{questions}
\item \points{25} Let $q,q' \in Q$ be two states of
$M$. Prove, that the shortest string $w''$, such that
$\delta^*(q,w'') = q'$ is of length at most $n-1$.
\item \points{25} Prove, that if there is a super{}string
$x$ of $w$, such that $x$ is accepted by $M$, then the
shortest such superstring is of length at most
$(n+1)(m+1)$, where $n=|Q|$ and $m=|w|$.
\item \points{50} Describe an algorithm, as efficient as
possible, that computes the shortest super{}string $z$ of
$w$, such that $z$ is accepted by $M$. (One can solve this
problem using dynamic programming, but this is definitely
not the only way.)
\end{questions}
}{}{}{}
\item \OLDHWProblem{100}{Stars in a tree.}%
{%
A \emph{star}, in a tree, is a vertex together with \emph{all}
the edges adjacent to it. A collection of stars is
\emphi{independent} if no two stars shares a vertex. The
\emph{mass} of an independent set of stars $S$ is the total
number of edges in the stars of $S$.
\phantom{}\hfill%
\includegraphics[page=1]{figs/tree}%
\hfill%
\includegraphics[page=2]{figs/tree}%
\hfill%
\phantom{}%
Describe an algorithm, as efficient as possible, that computes
the maximum mass of any set of independent stars in the given
tree $T$. Here the input tree $T$ has $n$ vertices. %
}{}{}
\item \OLDHWProblem{100}{Exploring Narnia.}%
{%
Three travelers had decided to travel to Narnia. Since they are
all anti-social, they do not want to travel together. Instead,
the first traveler would move from location $p_1$ to location
$p_2$, and so on till arriving to location $p_n$ (here,
$P = p_1,\ldots, p_n$). A location is just a point in the plane
(i.e., $p_i \in \Re^2$). Similarly, the second traveler is
going to move along $Q = q_1,\ldots, q_n$, and the third
traveler is going to move along $R = r_1, \ldots, r_n$. Every
day, a traveler might decide to stay in its current location,
or move to the next location (the traveling between two
consecutive locations takes less than a day).
By the evening of each day, the travelers arrive to their
desired locations for the day, which can be thought of as a
configuration $(p,q,r) \in P \times Q \times R$.
A configuration $(p,q,r)$ is \emph{$\ell$-legal} if
\begin{equation*}
\Delta(p,q,r) =
\max\pth{\bigl. \|p - q\|, \|p-r\|, \|q-r\| } \leq \ell,
\end{equation*}
where $\|p-q\|$ is the Euclidean distance between the points
$p$ and $q$ (this distance can be computed in constant time).
(Intuitively, the travelers do not want to be too far from each
other, so that if one of them is hurt, the others can quickly
come over and help.)
\begin{questions}
\item \points{50} Given the point sequences $P,Q,R$, and a
parameter $\ell > 0$, describe an algorithm, as fast as
possible, that decides if there is a motion planning
schedule from $(p_1,q_1,r_1)$ to $(p_n,q_n,r_n)$ such that
all the configurations used are $\ell$-legal. Such a
schedule is an \emph{$\ell$-feasible schedule}.
Here, it is legal for several travelers to move in the same
day, but they are not allowed to move back to a previous
location they already used. Furthermore, a traveler can
move, in one day, only one location forward in their
sequence.
\item \points{50} Given $P,Q,R$, as above, describe an
algorithm, as fast as possible, that computes the minimum
$\ell$ for which there is an $\ell$-feasible schedule.
\end{questions}
}{}{}{}{}
\end{questions}
\HomeworkEnd{}