\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi
\OLDHomeworkStart%
{8} % Homework number
{10} % Week of semester submitted
{1.0} % Version
\SaveIndent%
\HWInstructions{%
\textbf{Submission instructions as in previous %
\underline{%
\href{https://courses.engr.illinois.edu/cs374/fa2017/hw/hw_00.pdf}{homeworks}%
}.}%
\medskip%
\hrule %
\medskip
}
\noindent%
\begin{questions}[start=22]
\RestoreIndent%
\item \OLDHWProblem{100}{Where to park?}{
Urbana high school has (only) $n$ students, and every student
has a car (sadly, only one car). The parking lot $S$ has
$m\geq n$ spots where one can park their car. The $i$\th car
$c_i$, has exactly two distinct spots $s_i, s_i' \in S$ where
it is allowed to park, for $i=1,\ldots, n$. Given these spots,
design an efficient algorithm that decides if there is a way to
park all the cars (no two cars park in the same spot).
\begin{questions}
\item \points{10} Consider a graph $\Graph$ with $2n$
nodes, where for every car $c_i$ there are two nodes
$\Vrt{i}{s_i}$ and $\Vrt{i}{s_i'}$. For
$\gamma \in \{s_i, s_i'\}$ and $\delta \in \{s_j, s_j'\}$,
add a directed edge from $\Vrt{i}{\gamma}$ to
$\Vrt{j}{\delta}$, if parking the $i$\th car at
$\gamma$ implies that the $j$\th car must be parked in the
slot $\delta$ because the other parking spot of the $j$\th
car is $\gamma$. Let $m$ denote the number of edges of
$\Graph$. What is the maximum value of $m$ (in the worst
case)? What is the running time of your algorithm to
compute this graph?
\item \points{10} If there is a path in $\Graph$ from
$\Vrt{i}{\gamma}$ to $\Vrt{j}{\delta}$, then
$c_i=\gamma$ \emphi{forces} {$c_j=\delta$}. Prove that if
$c_i=s_i$ forces $c_j=s_j$ then {$c_j=s_j'$} forces
{$c_i=s_i'$}.
\item \points{20} Prove that if $\Vrt{i}{s_i}$ and
$\Vrt{i}{s_i'}$ are in the same strong connected
component of $\Graph$, then there is no legal way to park
the cars.
\item \points{20} Assume that there is a legal solution,
and consider a \SCC $Y$ of $\Graph$ involving cars, say,
$c_1, \ldots, c_t$ in $\Graph$; that is, $Y$ is a set of
vertices of the form
$\Vrt{1}{x_1},\ldots, \Vrt{t}{x_t}$. Prove that
$\Vrt{1}{x_1'},\ldots, \Vrt{t}{x_t'}$ form their
own strong connected component $\overline{Y}$ in $\Graph$
($\Bigl.\overline{Y}$ is the \emphi{reflection} of $Y$).
\item \points{10} Prove that if $X$ is a \SCC of $\Graph$
that is a sink in the meta graph $\GSCC$, then
$\Bigl.\overline{X}$ is a source in the meta graph $\GSCC$.
\item \points{30} Consider the algorithm that takes the
sink $X$ of the meta-graph $\GSCC$, use the associated
slots as specified by the nodes in $X$, remove the vertices
of $X$ from $\Graph$ and the vertices of
$\Bigl.\overline{X}$ from $\Graph$, and repeating this
process on the remaining graph. Prove that this algorithm
generates a legal parking of the cars if it exits (or
otherwise outputs that no such parking exists [describe how
to modify the algorithm to check for this]). Describe how
to implement this algorithm efficiently.
What is the running time of your algorithm in the worst
case as a function of $n$ and $m$.
\end{questions}
}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item \OLDHWProblem{100}{Revisit.}{
\begin{questions}
\item \points{20} Consider a \DAG $\Graph$ with $n$
vertices and $m$ edges. Assume that $s$ is a source in
$\Graph$ (a \emphi{source} is a vertex that has only
outgoing edges). Describe how to compute in linear time a
set of new edges such that $s$ is the only source in the
resulting graph (which still has to be a \DAG). How many
edges does your algorithm add (the fewer, the better)?
\item \points{20} Assume $\Graph$ is a \DAG with a source
vertex $s$. Some of the vertices of $\Graph$ are marked as
being \emphi{important}. Show an algorithm that in linear
time computes all the vertices that can be reached from $s$
via a path that goes through at least $\tau$ important
vertices, where $\tau$ is a prespecified parameter.
\item \points{30} An edge $\edge$ of $\Graph$ has the
length $\ell(\edge)$ assigned to it (it can be potentially
a negative number, not that it matters). Show an algorithm
(faster is better) that computes for all the vertices $v$
in $\Graph$ the length of the
\underline{\emphColor{longest}} path from $s$ to $v$.
\item \points{30} Using the above, describe how to compute,
in linear time, a path that visits the maximum number of
vertices of the \DAG $\Graph$ (the path is allowed to start
at any vertex and end at any vertex of $\Graph$).
\end{questions}
}{}{}
\end{questions}
\HomeworkEnd{}