\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi
\OLDHomeworkStart%
{10} % Homework number
{14} % Week of semester submitted
{1.0} % Version
\HWInstructionsStd{}%
\SaveIndent%
\begin{questions}[start=28]
\RestoreIndent%
\item
\OLDHWProblem{100}{MST.}{
\RestoreIndent%
Let $\Graph$ be an undirected graph with $n$ vertices and $m$
edges with weights on the edges (here $m \geq n$). Furthermore,
assume that the given weights $w(\cdot)$ on the edges are all
distinct.
\begin{questions}
\RestoreIndent%
\item \points{30} For a path $\pi$ in the graph, its
\emphi{bottleneck price} $\beta(\pi)$ is the maximum weight
of an edge on $\pi$. Formally,
$\beta(\pi) = \max_{e \in \pi} w(e)$. The
\emphi{bottleneck distance} for two vertices
$u,v \in \VX{\Graph}$ is
$\bm{\beta}(u,v) = \min_{\pi \in \Pi(u,v)} \beta(\pi)$,
where $\Pi(u,v)$ is the set of all paths between $u$ and
$v$ in $\Graph$.
Describe how to build a data-structure, using $O(n)$ space,
such that given a query pair of vertices
$u,v \in \VX{\Graph}$, one can compute $\bm{\beta}(u,v)$ in
$O(n)$ time. Describe the query algorithm that computes the
distance, and prove its correctness (i.e., that the result
it returns is correct). What is the construction time of
the data-structure?
[Harder but doable by you. Not for submission (and we will
not provide a solution): Show how to build a data-structure
that uses $O( n \log n)$ space, and answers such queries in
$O( \log n)$ time.]
\item \points{10} Consider computing the \MST $T_1$ from
$\Graph$, removing the edges of $T_1$ from $\Graph$,
computing an \MST $T_2$ of the remaining graph, and
continuing in this fashion till the graph is disconnected,
and let $T_1, \ldots, T_k$ be the extracted spanning trees.
Computing such trees can be useful for robustness -- if the
first \MST fails, you have a tree which is almost as good
as backup (i.e., $T_2$), and so on.
Clearly, this sequence can be computed in
$O( k ( n \log n + m))$ time (how?). We are interested in a
faster algorithm (for example, think about the case that
$k = \Omega(\sqrt{n})$).
To this end, let $\edge_1, \ldots, \edge_m$ be the edges of
$\Graph$ in increasing sorted order by weight. Let
$L_1(t) = \brc{\edge_1, \ldots, \edge_t}$ be the set of the
first $t$ edges in this order. Let $F_1(t)$ be the set of
edges used by the spanning forest computed by the Kruskal
algorithm after inserting the edges of $L_1(t)$.
More generally, for $i>0$, let
$L_{i+1}(t) = L_i(t) \setminus F_i(t)$, and let
$F_{i+1}(t)$ be the edges of the spanning forest of
$L_{i+1}(t)$ as computed by the Kruskal algorithm when
executed on the set of edges $L_{i+1}(t)$.
Prove that $F_1(m), \ldots, F_k(m)$ are the edges of the
trees $T_1, \ldots, T_k$, respectively.
\item \points{10} In the context of (B). Prove, that if
two vertices $u,v$ are in the same connected component of
the graph $(\Vertices, F_i(t))$, for some time $i$, then
they are in the same connected component of
$(\Vertices, F_j(t))$, for all $j < i$.
\item \points{20} Let $D_i(t)$ be the union-find
data-structure used by the Kruskal algorithm, defined over
the $\VX{F_i(t)}$, after handling the edges of $L_i(t)$.
Assume that you have $D_1(t), D_2(t),\ldots$, and the edge
$\edge_{t+1} = u_{t+1}' v_{t+1}'$. Show how to compute, in
$O( \alpha(n) \log n)$ time, the minimal index $j>0$, such
that the two vertices $u_{t+1}'$ and $v_{t+1}'$ of
$\edge_{t+1}$ appear in two different connected components
of $F_j(t)$.
Here, assume $\alpha(n)$ is a bound on the time it takes to
perform a single operation in the union-find
data-structure.
\item \points{30} Using the above, show how to compute the spanning
trees $T_1, \ldots, T_k$, from part (B), in
$O( m \alpha(n) \log n)$ time. Be careful about the
details -- the value of $k$ is not given to you, and you
might need to create new sets (of a single element) in the
union-find data-structures on the fly.
\end{questions}
\HWInstructions{%
Do not use hashing or dictionary data-structures in solving
this problem.%
}% \medskip%
}{}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item \OLDHWProblem{100}{Undecidable.}{%
For each of the following languages, either prove that it is
undecidable (by providing a detailed reduction from a known
undecidable language), or describe an algorithm that decides
this language -- your description of the algorithm should be
detailed and self contained. (Note, that you cannot use Rice
Theorem in solving this problem.)
\begin{questions}
\item \points{25}
\begin{math}
L_1 = \Set{ \permut{D, N} }{ L(D)=L(N)\text{, where } D
\text{ is a \DFA, and } N \text{ is an \NFA}}
\end{math}
\item \points{25}
\begin{math}
L_2 = \Set{ \permut{M, D} }{ L(M)=L(D)\text{, where } M
\text{ is a Turing machine, and } D \text{ is a
\DFA}}
\end{math}
\item \points{25}
\begin{math}
L_3 = \Set{ \permut{D} }{ L(D) \text{ is finite, where
} D
\text{ is a \DFA }}.
\end{math}
\item \points{25}
\begin{math}
L_4 = \Set{ \permut{M} }{ L(M) \text{ is finite, where
} M \text{ is a Turing machine}}.
\end{math}
\end{questions}
}{}{}{}{}{}
\end{questions}
\HomeworkEnd{}