\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$}
\\ Due December 12, in Recitation
\end{center}
\begin{quote}
In the novel I never wrote, I wanted the hero to be a computer programmer
because it was the most poetic and romantic occupation I could think
of [...] I conceived of him, whose professional life was spent in the
sanctum of the night (when, I was told, the computers, too valuable to be
unemployed by industry during the day, are free, as it were, to frolic)
devising idioms whereby problems might be fed to the machines and emerge,
under binary percussion, as the music of truth - I conceived of him as
being too fine, transluscent, and scrupulous to live in our coarse age.
He was to be, if the metaphor is biological, an evolutionary abortion,
a mammalian mutation crushed underfoot by dinosours, and, if the metaphor
is mathematical, a hypothetical ultimate, one digit beyond the last real
number. The title of the book was to be $N+1$.
\\ from {\em The Music School} by John Updike
\end{quote}
\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$?
What is the interpretation of $\pi[v],d[v]$ for $v\not\in S$?
Which $v$ will have $\pi[v]=NIL$ at this time. For those
$v$ what will be $d[v]$?
\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)$.
\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 the chapter) to find
{\tt COUNT[s,j]} for all $j$.
\een
\begin{quote}
A clever man commits no minor blunders. -- Goethe
\end{quote}
\end{document}