\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi
\OLDHomeworkStart%
{7} % Homework number
{9} % Week of semester submitted
{1.0} % 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}{No one expects the Spanish inquisition.}%
{%
(This problem is somewhat easier than the usual homeworks
problems.)
It is 1492 in Spain (the Jews were just kicked out of Spain,
and Columbus just landed in the Bahamas [an interesting year])
-- unfortunately, the people in the town that you live in
decided that you are a witch, and it is only a question of time
till the inquisition would come to investigate\footnote{For
once, somebody is expecting the Spanish inquisition:
\si{\url{https://www.youtube.com/watch?v=QqreRufrkxM}}.}. You
can avoid the investigation by paying bribes.
Fortunately, you got your hands on the organizational chart of
the inquisition, which is a tree. The leafs are the
investigators, and the internal nodes are the supervisors. A
person that corresponds to a node $u$ of this tree $T$, can be
bought off by paying $b_u$ \Maravedi{}s (the Spanish money at
the time), and then they would suppress any investigation by
anybody in their subtree.
Given a tree $T$ as above with $n$ nodes, the problem is to
compute the set of people that you should bribe, so that all
possible investigations are suppressed, and that the total sum
paid is minimal. As example, consider the following tree (on
the left, and a solution on the right).
\noindent%
\includegraphics[width=0.48\linewidth]%
{\File{figs/inquisition}}
\hfill%
\includegraphics[width=0.48\linewidth]%
{\File{figs/inquisition_sol}}
\begin{questions}
\RestoreIndent%
\item \points{30} State the recursive formula (or formulas
if needed) for computing the desired quantity -- and
explain the logic behind it (in one sentence). What is the
running time of your algorithm? (The running time should be
as good as possible, as usual.)
Note, that you need only to compute the price of the
optimal solution -- there is no need to output the solution
itself.
\item \points{70} Describe a dynamic program to solve the
problem. Your algorithm should be implemented using
explicit memoization, and should not use recursion. Analyze
the running time of your algorithm (you need to provide
pseudo-code). What is the running time and space of your
algorithm?
Here, assume the input is given in an array
$Z[\range{1}{n}]$ of nodes. The first entry (i.e., $Z[1]$)
is the root. Every node has a field $b$ specifying the
bribe, and a field $\ell$ specifying the number of children
it has, and an array/list $C$ of the indices of the
children nodes. You can assume that for a node $Z[i]$, all
its children are stored in locations in $Z$ with index
strictly larger than $i$.
(Again, no need to output the set realizing the solution --
just the price of this solution -- you should think about
how to print out the optimal solution.)
\item (\textbf{Not for submission}, and we are not going to
provide a solution for this part.) What if you need to
bribe $k$ people on each path from the root to a leaf of
the tree (think about the case $k=2$ or $k=3$). Indeed, if
each person getting bribed knows that you can manage
without them, the amount they are going to ask for is going
to be significantly lower. How do you compute the minimum
cost set of people to bribe in this case? What is the
resulting running time?
\end{questions}
}%
{}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item \OLDHWProblem{100}%
{Fishing for staircases.}%
{%
A \DAG is a directed graph with no cycles. Given a \DAG
$\Graph$ with $n$ vertices and $m$ edges, one can compute in
$O(n + m)$ time an ordering of its vertices $v_1, \ldots v_n$,
such that if there is an edges
$\dirEdge{v_i}{v_j} \in \Edges(\Graph)$, then $ i < j$. This is
known as \emphi{topological sort} (or \emphi{topological
ordering}) of $\Graph$, and you can assume you are given a
black box that can implement this operation in $O(n+m)$ time.
A vertex in a \DAG is a \emphi{sink} if it has no outgoing
edges.
\begin{questions}
\item \points{25} The \emphi{value} of a vertex $v$ in a
\DAG $\Graph$, is the length of the longest path in \DAG
that starts in $v$. Describe a linear time algorithm (in
the number of edges and vertices of $\Graph$) that computes
for all the vertices in $\Graph$ their value.
\item \points{25} Prove that if two vertices
$u,v \in \VerticesX{\Graph}$ have the same value (again,
$\Graph$ is a \DAG), then the edges $\dirEdge{u}{v}$ and
$\dirEdge{v}{u}$ are not in $\Graph$.
\item \points{25} Using (B), prove that in any \DAG
$\Graph$ with $n$ vertices, for any $k$, either there is a
path of length $k$, or there is a set $\SetX$ of
$\floor{n/k}$ vertices in $\Graph$ that is
\emphi{autonomous}; that is, there is no edge between any
pair of vertices of $\SetX$.
\item \points{25} %
Consider a set of $\PntSet$ of $n$ points in the plane. The
points of $\PntSet$ are in general position -- no two
points have the same $x$ or $y$ coordinates. Consider a
sequence $S$ of points $\pnt_1, \pnt_2,\ldots, \pnt_k$ of
$\PntSet$, where $\pnt_i = (x_i, y_i)$, for
$i=1,\ldots, k$. The sequence $S$ is \emphi{staircase}, if
either
\begin{compactitem}
\item for all $i=1, \ldots, k-1$, we have $x_i <
x_{i+1}$ and $y_i < y_{i+1}$, or
\item for all $i=1, \ldots, k-1$, we have $x_i <
x_{i+1}$ and $y_i > y_{i+1}$.
\end{compactitem}
Prove using (C) that there is always a staircase of length
$\floor{\sqrt{n}}$ in $\PntSet$. Describe an algorithm, as
fast as possible, that computes the longest staircase in
$\PntSet$.
\begin{tabular}{c|c|c}
\includegraphics[page=1]%
{\File{figs/staircase}}
&
\quad
\includegraphics[page=2]{\File{figs/staircase}}
\quad$~$
&
\quad
\includegraphics[page=3]{\File{figs/staircase}}
\end{tabular}
\item \textbf{(Harder + \textbf{not for submission}.)}
Using the algorithm of (D), describe a polynomial time
algorithm that decomposes $\PntSet$ into a set of
$O(\sqrt{n})$ disjoint staircases. Prove the correctness of
your algorithm.%
\end{questions}
}{}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item \OLDHWProblem{100}{Independence in orderly graphs.}%
{%
For a graph $\Graph$ with $n$ vertices, assigning each vertex
of $\Graph$ a unique number in $\brc{1,\ldots, n}$ is a
\emphi{numbering} of its vertices.
A graph $\Graph$ with a numbering
$\VerticesX{\Graph} = \brc{1,\ldots, n}$ is
\emphi{$k$-orderly}, if for every edge
$ij \in \EdgesX{\Graph}$, we have that $-k \leq i-j \leq k$
(note, that it is not true that if $|i-j| \leq k$ then $ij$
must be an edge in the graph!). A different numbering of the
vertices of $\Graph$ might change the value of $k$ for which
$\Graph$ is $k$-orderly. Here are a few examples of a
$3$-orderly graph:
\smallskip
\centerline{%
\begin{tabular}{|c|c|c|}
\includegraphics[width=0.28\linewidth]{\File{figs/3_orderly}}%
&
\includegraphics[width=0.28\linewidth]%
{\File{figs/3_orderly_2}}%
&
\includegraphics[width=0.28\linewidth]%
{\File{figs/3_orderly_3}}%
\end{tabular}%
}
\medskip%
\begin{questions}
\RestoreIndent%
\item \points{20} For any given value of $k$, show an example
of a graph that is not $k$-orderly for any numbering of its
vertices. Prove the correctness of your example. For credit
your graph should have a minimal number of edges (as a
function of $k$).
\item \points{80} %
Given a $k$-orderly graph $\Graph$ (here you are given the
numbering of the vertices, and the value $k$ [or, you can
compute it directly from the numbering]), consider the problem
of computing the largest {independent{ }set} of $\Graph$. As
a reminder, a set of vertices $X \subseteq \Vertices(\Graph)$
is \emphi{independent}, if no pair of vertices of $X$ are
connected by an edge of $\Graph$.
Provide an algorithm, as fast as possible, for computing the
size of the largest independent set in $\Graph$. What is the
dependency of the running time of your algorithm on the
parameter $k$?
In particular, for credit, your solution for this problem
should have polynomial time for $k$ which is a constant. For
full credit, the running time of your algorithm should be
$O(f(k) n)$, where $f(k)$ is some (potentially large) function
of $k$.
For this question you can use implicit memoization.
Hint: (A) Think about the vertices as ordered from left to
right as above. Start with $k=1$. Then, solve the problem for
$k=2,3, 4, \ldots$. Hopefully, by the time you hit $k=5$ you
would be able to describe an algorithm for the general
case. Think about defining a recursive function for this
problem that has $\approx k$ parameters.
\end{questions}
}{}{}{}
\end{questions}
\HomeworkEnd{}