% ---------
% Compile with "pdflatex hw0".
% --------
%!TEX TS-program = pdflatex
\documentclass[11pt]{article}
\usepackage{jeffe,handout,graphicx,mathtools}
\usepackage{tikz}
%!TEX encoding = UTF-8 Unicode
\usepackage[utf8x]{inputenc} % Allow some non-ASCII Unicode in source
\usepackage{enumerate}
\usepackage{stmaryrd}
\def\Sym#1{\textbf{\texttt{\color{BrickRed}#1}}}
% ---------
% The next following lines change the default text and math fonts and
% make a few other minor cosmetic changes. If you get any error
% messages related to these packages, just comment them out. -- Jeff
% --------
\usepackage[charter]{mathdesign}
\usepackage{berasans,beramono}
\SetMathAlphabet{\mathsf}{bold}{\encodingdefault}{\sfdefault}{b}{\updefault}
\SetMathAlphabet{\mathtt}{bold}{\encodingdefault}{\ttdefault}{b}{\updefault}
\SetMathAlphabet{\mathsf}{normal}{\encodingdefault}{\sfdefault}{\mddefault}{\updefault}
\SetMathAlphabet{\mathtt}{normal}{\encodingdefault}{\ttdefault}{\mddefault}{\updefault}
\usepackage{microtype}
% ---------
% End of cosmetics.
% --------
% ---------
% Redefine suits
% --------
\usepackage{pifont}
\def\Spade{\text{\ding{171}}}
\def\Heart{\text{\textcolor{Red}{\ding{170}}}}
\def\Diamond{\text{\textcolor{Red}{\ding{169}}}}
\def\Club{\text{\ding{168}}}
\def\Cdot{\mathbin{\text{\normalfont \textbullet}}}
\def\CDOT{\mathbin\bullet}
\def\Sym#1{\texttt{\upshape \color{BrickRed} {#1}}}
\def\Blank{\hphantom{A}\llap{$\diamond$}}
\def\Var#1{\ensuremath{\seq{\textsf{#1}}}}
\def\To{\leadsto}
\def\Tostar{\mathrel{\To\!\!\!^*}}
%\def\Enter{\small Enter}
\def\Enter{$\dlsh$}
% ---------
% Dashed lines in arrays
% --------
\usepackage{arydshln}
\dashlinedash 0.75pt
\dashlinegap 1.5pt
\hidesolutions
% =========================================================
\begin{document}
\headers{“CS 374”}{Homework 7}{Fall 2015}
\thispagestyle{empty}
\begin{center}
\LARGE
\textbf{“CS 374” Fall 2015 --- Homework 7}
\\
\Large Due Tuesday, October 27, 2015 at 10am
\end{center}
\bigskip
\bigskip
\bigskip
\hrule
\begin{center}
\Large \textbf{••• Some important course policies •••}\\
\end{center}
\hrule
\bigskip
\begin{itemize}
\item \textbf{You may work in groups of up to three people.} However, each problem should be submitted by exactly one person, and the beginning of the homework should clearly state the names and NetIDs of each person contributing.
\item \textbf{You may use any source at your disposal}—paper,
electronic, or human—but you \EMPH{must} cite \EMPH{every} source
that you use. See the academic integrity policies on the course web
site for more details.
\item
\textbf{Submit your pdf solutions in Moodle.}
See instructions on the course website and submit a separate pdf
for each problem. Ideally, your solutions should be typeset in LaTex. If you hand write your homework make sure that the pdf scan is easy to read. Illegible scans will receive no points.
\item
\textbf{Avoid the Three Deadly Sins!} There are a few dangerous writing (and thinking) habits that will trigger an automatic zero on any homework or exam problem. Yes, we are completely serious.
\begin{itemize}\itemsep0pt
\item Give complete solutions, not just examples.
\item Declare all your variables.
\item Never use weak induction.
\end{itemize}
\item
Unlike previous editions of this and other theory courses we are not
using the “I don’t know” policy.
\end{itemize}
\bigskip
\hrule
\begin{center}
\large \textbf{See the course web site for more information.}\\[2ex]\normalsize
If you have any questions about these policies,\\
please don’t hesitate to ask in class, in office hours, or on Piazza.
\end{center}
\hrule
\vfil
\vfil
\vfil
\newpage
\begin{enumerate}
\parindent 1.5em \itemsep 3ex plus 0.5fil
%----------------------------------------------------------------------
\def\arraystretch{1.2}
%\hidesolutions
\newcommand{\IsSinL}{\text{IsStringInL}}
%----------------------------------------------------------------------
\item Given an undirected connected graph $G=(V,E)$ an edge $(u,v)$ is
called a cut edge or a bridge if removing it from $G$ results in
two connected components (which means that $u$ is in one component
and $v$ in the other). The goal in this problem is to design an efficient
algorithm to find {\em all} the cut-edges of a graph.
\begin{itemize}
\item What are the cut-edges in the graph shown in the figure?
\begin{center}
\includegraphics{figs/graph}
\end{center}
\item Given $G$ and edge $e=(u,v)$ describe a linear-time algorithm
that checks whether $e$ is a cut-edge or not. What is the running time
to find all cut-edges by trying your algorithm for each edge? No proofs
necessary for this part.
\item Consider {\em any} spanning tree $T$ for $G$. Prove that every
cut-edge must belong to $T$. Conclude that there can be at most $(n-1)$
cut-edges in a given graph. How does this information improve the
algorithm to find all cut-edges from the one in the previous step?
\item Suppose $T$ is a spanning tree of $G$ rooted at $r$.
Prove that an edge $(u,v)$ in $T$ where $u$ is
the parent of $v$ is a cut-edge iff there is no edge in $G$
with one end point in $T_v$ (sub-tree of $T$ rooted at $v$)
and one end point outside $T_v$.
\item Use the property in the preceding part to design a linear-time
algorithm that outputs all the cut-edges of $G$. You don't have to
prove the correctness of the algorithm but you should point out how
your algorithm ensures the desired property.
\end{itemize}
%----------------------------------------------------------------------
\item Let $G=(V,E)$ be a directed graph. Each vertex $v \in V$ has
a weight $w(v)$ associated with it. Given a vertex $s \in V$
let $\alpha(s) = \max\{ w(v) \mid \mbox{$v$ can reach $s$ in $G$}\}$ be
the maximum weight among the weights of all nodes that can reach $s$ in $G$.
In the figure below $\alpha(b) = 21$ and $\alpha(i) = 40$.
\begin{figure}[h]
\centering
\includegraphics[height=2in]{figs/max-weight-fig.pdf}
\end{figure}
Describe an efficient algorithm that given a graph $G$ and the
weights $w(v), v \in V$, computes $\alpha(s)$ for every $s \in V$. To
this end first consider the case when $G$ is strongly connected and
when $G$ is a DAG. Full credit for a {\em linear-time} algorithm.
A formal proof is not needed but you need to give an explanation
of your algorithm and why it achieves the desired running time.
%----------------------------------------------------------------------
\item Let $G=(V,E)$ be a directed graph with non-negative edge lengths
$\ell(e), e \in E$. You are also given a subset of the nodes $X
\subset V$ that are called {\em dangerous}. Given two nodes $s,t$
describe an efficient algorithm to find a shortest path from $s$ to
$t$ among all paths that contain at most one dangerous node. You
can assume that $s$ and $t$ are not dangerous. Ideally the algorithm
should run in time proportional to one single-source shortest path
computation.
%----------------------------------------------------------------------
\end{enumerate}
\end{document}
%----------------------------------------------------------------------