\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{fancybox}
\usepackage{hyperref}
 
\newcommand{\DFSa}{\textsf{\sc DFS}}
\newcommand{\EXPLORE}{\textsf{\sc Explore}}
\newcommand{\UNION}{\textsf{\sc Union}}
\newcommand{\FIND}{\textsf{\sc Find}}

\newcommand{\DFS}{\mathord{\it DFS}}
\newcommand{\PRE}{\mathord{\it pre}}
\newcommand{\POST}{\mathord{\it post}}
\newcommand{\VISITED}{\mathord{\it visited}}
\newcommand{\TRUE}{\mathord{\it true}}
\newcommand{\FALSE}{\mathord{\it false}}
\newcommand{\CLOCK}{\mathord{\it clock}}
\newcommand{\LAS}{\mathord{\it LAS}}
\newcommand{\MIN}{\mathord{\it Min}}
\newcommand{\WT}{\mathord{\it wt}}

\newcounter{ques}
\newenvironment{question}{\stepcounter{ques}{\noindent\bf Question \arabic{ques}:}}{\vspace{5mm}}

\begin{document} 

\begin{center} \Large\bf
COMP 3804 --- Assignment 3 
\end{center} 

\noindent {\bf Due:} Monday March 25, 23:59.

\vspace{0.5em}

\noindent {\bf Assignment Policy:}
\begin{itemize}
\item Your assignment must be submitted as one single PDF file through
      Brightspace.

\begin{center}
\hfill\shadowbox{
  \begin{minipage}{.90\linewidth}
    {\textsf{Use the following format to name your file:
        \[ {\tt LastName\_StudentId\_a3.pdf}
        \]
      }}
  \end{minipage}
}
\end{center}
\item {\bf Late assignments will not be accepted. I will not reply to
      emails of the type ``my internet connection broke down at
      23:57'' or ``my scanner stopped working at 23:58'', or
      ``my dog ate my laptop charger''.}
\item You are encouraged to collaborate on assignments, but at the level
      of discussion only. When writing your solutions, you must do so
      in your own words.
\item Past experience has shown conclusively that those who do not put
      adequate effort into the assignments do not learn the material and
      have a probability near 1 of doing poorly on the exams.
\item When writing your solutions, you must follow the guidelines below.
      \begin{itemize}
      \item You must justify your answers.
      \item The answers should be concise, clear and neat.
      \item When presenting proofs, every step should be justified.
      \end{itemize}
\end{itemize}

\newpage 

\begin{quote}
\begin{tabbing}
{\bf Algorithm} $\DFSa(G)$: \\
{\bf for each} vertex $v$ \\
{\bf do} $\VISITED(v) = \FALSE$ \\
{\bf endfor}; \\
$\CLOCK = 1$; \\
{\bf for each} vertex $v$ \\
{\bf do} \= {\bf if} $\VISITED(v) = \FALSE$ \\
         \> {\bf then} $\EXPLORE(v)$  \\
         \> {\bf endif} \\
{\bf endfor} \\
\end{tabbing}
\end{quote}

\begin{quote}
\begin{tabbing}
{\bf Algorithm} $\EXPLORE(v)$: \\
$\VISITED(v) = \TRUE$; \\
$\PRE(v) = \CLOCK$; \\
$\CLOCK = \CLOCK + 1$; \\
{\bf for each} edge $(v,u)$ \\
{\bf do} \= {\bf if} $\VISITED(u) = \FALSE$ \\
         \> {\bf then} \= $\EXPLORE(u)$ \\
         \> {\bf endif} \\
{\bf endfor}; \\
$\POST(v) = \CLOCK$; \\
$\CLOCK = \CLOCK + 1$ \\
\end{tabbing}
\end{quote}

\newpage 

\begin{question}
Write your name and student number.
\end{question}

\begin{question}
Let $G=(V,E)$ be a directed graph. After algorithm $\DFSa(G)$ has 
terminated, each vertex has a $\PRE$- and $\POST$-number. Let $u$ and 
$v$ be two distinct vertices in $V$. Assume that both of the following 
are true: 
\begin{itemize} 
\item There is a directed path in $G$ from $u$ to $v$. 
\item $\PRE(u) < \PRE(v)$. 
\end{itemize} 
Professor Lionel Messi claims that, in the $\DFSa$-forest, $v$ must be 
in the subtree of $u$. 

Is Professor Messi's claim correct? As always, justify your answer.  
\end{question}

\begin{question}
Give an example of a directed graph $G=(V,E)$ that contains a vertex 
$v$ having the following properties: 
\begin{itemize} 
\item $v$ has at least one incoming edge and at least one outgoing edge.
\item Consider the $\DFSa$-forest after algorithm $\DFSa(G)$ has 
terminated. This forest contains a tree containing only the vertex $v$. 
\end{itemize} 
\end{question} 

\begin{question} 
Let $G=(V,E)$ be a directed graph that is given to you using adjacency 
lists. The vertices of $V$ are numbered arbitrarily as 
$v_1,v_2,\ldots,v_n$. 

For each vertex $u$ of $V$, let $R(u)$ be the set of all vertices $v$ 
such that there exists a directed path in $G$ from $u$ to $v$, and let 
$\MIN(u)$ be the smallest index of all vertices in $R(u)$. Thus, 
\[ \MIN(u) = \min \{ i : v_i \in R(u) \} .
\] 
Give an algorithm that computes, in $O(|V|+|E|)$ time, the value of 
$\MIN(u)$ for all vertices $u$ in $V$. As always, justify your answer. 

\noindent 
\emph{Hint:} 
Consider the graph $G'$ obtained from $G$ by reversing the direction of 
all edges in $G$. Algorithm $\DFSa$ is useful for this question. 
\end{question}

\begin{question} 
Let $G=(V,E)$ be a connected undirected graph in which each edge 
$\{u,v\}$ has a weight $\WT(u,v)$. Consider the following algorithm: 
\begin{itemize} 
\item Let $G' = G$. 
\item While $G'$ contains a cycle: 
\begin{itemize} 
\item Let $C$ be an arbitrary cycle in $G'$.
\item Let $e$ be an edge of $C$ whose weight is maximum. 
\item Delete the edge $e$ from $G'$. 
\end{itemize} 
\item Return the graph $G'$. 
\end{itemize} 
Prove that the output of this algorithm is a minimum spanning tree 
of the input graph $G$.  
\end{question}

\begin{question} 
Let $G=(V,E)$ be a directed graph in which each edge $(u,v)$ 
has a weight $\WT(u,v)$. Let $s$ be an arbitrary source vertex. 
Assume that the following are true: 
\begin{itemize}
\item Edges that leave $s$ may have negative weights. 
\item All other edges have positive weights. 
\item There is no cycle with negative weight. 
\end{itemize} 
Professor Justin Bieber claims that Dijkstra's algorithm correctly 
computes, for each vertex $v$, the length of a shortest path from $s$ 
to $v$. 

Is Professor Bieber's claim correct? As always, justify your answer.  
\end{question}

\begin{question} 
Let $S = (a_1,a_2,\ldots,a_n)$ be a sequence of $n$ numbers. 
A subsequence $T$ of $S$ is called \emph{awesome}, if for every 
$i$ with $1 \leq i \leq n-1$, $a_i$ and $a_{i+1}$ are not both in $T$. 
In other words, whenever a number is in $T$, none of its 
neighbors in $S$ is in $T$. The weight of the subsequence $T$ is 
the sum of all numbers in $T$. 

Give a dynamic programming algorithm that computes, in $O(n)$ time, 
the maximum weight of any awesome subsequence of $T$. 

As always, justify your answer. 
Follow the three dynamic programming steps that we have seen in class. 
\end{question}

\begin{question} 
Tyler is not only your friendly TA, he is also the CEO of 
\emph{Tuttle Enterprises}. This company buys long copper wires, cuts 
them into subwires, and then sells the subwires. 
Tuttle Enterprises only buys copper wires having integer lengths
and cuts them such that each subwire has an integer length. 

Let $n$ be a large integer and let $p_1,p_2,\ldots,p_n$ be a sequence of 
positive numbers. For each $i$ with $1 \leq i \leq n$, Tuttle Enterprises 
sells a subwire of length $i$ for $p_i$ dollars. 

Consider a copper wire of length $n$. Give a dynamic programming 
algorithm that computes, in $O(n^2)$ time, the maximum revenue that 
can be obtained by cutting the length-$n$ wire into subwires. 

As always, justify your answer. 
Follow the three dynamic programming steps that we have seen in class. 

For example, let $n=4$. Here are the different options to cut a 
length-$4$ wire: 
\begin{itemize}
\item The wire is not cut. Then the revenue is $p_4$. 
\item The wire is cut into one subwire of length $1$ and one subwire 
of length $3$. Then the revenue is $p_1+p_3$. 
\item The wire is cut into two subwires of length $1$ and one subwire 
of length $2$. Then the revenue is $2 \cdot p_1+p_2$. 
\item The wire is cut into two subwires of length $2$.
Then the revenue is $2 \cdot p_2$. 
\item The wire is cut into four subwires of length $1$.
Then the revenue is $4 \cdot p_1$. 
\end{itemize} 
\end{question}

\end{document} 
