\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Assignment 12}
\\ Solutions
\end{center}
\ben
\item Suppose that we are doing Dijkstra's Algorithm on
vertex set $V=\{1,\ldots,500\}$ with source vertex $s=1$
and at some time we have $S=\{1,\ldots,100\}$.
What is the interpretation of $\pi[v],d[v]$ for $v\in S$?
\So $d[v]$ is the minimal cost of a path from $s$ to $v$ and
$\pi[v]$ will be the vertex just before $v$ on that path.
\\ What is the interpretation of $\pi[v],d[v]$ for $v\not\in S$?
\So $d[v]$ is the minimal cost of a path $s,v_1,\ldots,v_j,v$ where
all the $v_1,\ldots,v_j\in S$. $\pi[v]$ will be the vertex just
before $v$ in this path, here $v_j$.
\\
Which $v$ will have $\pi[v]=NIL$ at this time.
\So Those $v$ for which there is no directed edge from any vertex
in $S$ to $v$.
\\ For those
$v$ what will be $d[v]$?
\So Infinity
\item Suppose, as with Dijkstra's Algorithm, the input is
a directed graph, $G$, a source vertex $s$, and a weight
function $w$. But now further assume that the weight
function only takes on the values one and two. Modify
Dijkstra's algorithm -- replacing the {\tt MIN-HEAP} with
a more suitable data structure -- so that the total time
is $O(E+V)$.
\So There are a number of approaches here. Start with
$S=\{s\}$ and sets ONE (those $v$ adjacent to $s$ via an
edge of weight one), TWO
(those $v$ adjacent to $s$ via an
edge of weight two), and INFTY (those not adjacent to $s$).
Now rather than going one vertex at a time $S$ will be all
points at weighted distance $d$ or less from $s$ and ONE,TWO
will be those $v$ adjacent to a $v\in S$ be an edge of weight
one or two (if both, one). Suppose, first, ONE is empty. Add
all points $v\in TWO$ to $S$. Each new (not in $S$) neighbor
of each such $v$ is put in ONE or TWO depending on its weight.
Suppose, otherwise, ONE is not empty. Add all points $v\in ONE$
to $S$. All points of TWO more to ONE.
Each new (not in $S$) neighbor
of each such $v$ is put in ONE or TWO depending on its weight.
{\tt Alternate Approach:} Whenever $w(x,y)=2$ create a new
vertex $z$, delete edge $(x,y)$ and add edges $(x,z),(z,y)$,
each of weight one. Now all the weights are one so that
BFS will give the distances.
\item Let $G$ be a {\tt DAG} on vertices $1,\ldots,n$ and
suppose we are {\em given} that the ordering $1\cdots n$ is
a Topological Sort.
Let {\tt COUNT[i,j]} denote the number
of paths from $i$ to $j$. Let $s$, a ``source vertex" be
given.
Give an efficient algorithm
(appropriately modifying the methods of \S 24.1) to find
{\tt COUNT[s,j]} for all $j$.
\So Lets assume $s=1$ (we can ignore the earlier vertices, if
any) and write $COUNT[j]$ for $COUNT[1,j]$. We set $COUNT[1]=1$.
The key is that
$COUNT[1,j]$ is the sum, over all $i