\documentclass[12pt]{article}
\usepackage[margin=1in]{geometry} 
\usepackage{amsmath,amsthm,amssymb,amsfonts}
\usepackage{graphicx,epstopdf,fancyhdr,xspace,algorithm,algorithmic}
\usepackage[space]{grffile}
\pagestyle{fancy}
\usepackage{epsfig}
\usepackage[space]{grffile}
\usepackage{titlesec}
\usepackage[table,dvipsnames]{xcolor}
\usepackage{enumitem} 
\usepackage{tikz}
\usetikzlibrary{arrows,automata}
\cfoot{\thepage}
\usepackage{multicol}
\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}
 

\usepackage{thmtools}
\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{claim}{Claim}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{observation}{Observation}
\newtheorem{question}{Problem}
\newenvironment{solution}{\bigskip\noindent{\it Solution.}  \ignorespaces}{\hfill\qed}

\declaretheoremstyle[
    headfont=\bfseries\sffamily\color{ForestGreen!70!black}, bodyfont=\normalfont,
    mdframed={
        linewidth=2pt,
        rightline=false, topline=false, bottomline=false,
        linecolor=ForestGreen, backgroundcolor=ForestGreen!5,
    }
]{thmgreenbox}
\declaretheorem[style=thmgreenbox, name=Hint,numbered=no]{hint}



\usepackage{hyperref}
\hypersetup{
    colorlinks=true,
    linkcolor=blue,
    filecolor=magenta,      
    urlcolor=cyan,
}
\urlstyle{same}
\PassOptionsToPackage{hyphens}{url}
\newcommand{\homework}[6]{
   \pagestyle{myheadings}
   \thispagestyle{plain}
   \newpage
   \setcounter{page}{1}
   \noindent
   \begin{center}
   \framebox{
      \vbox{\vspace{2mm}
    \hbox to 6.28in { {\bf CS 256:~Algorithm Design and Analysis \hfill} }
       \vspace{6mm}
       \hbox to 6.28in { {\Large \hfill #1 \normalsize{(#2)}  \hfill} }
       \vspace{6mm}
     \hbox to 6.28in { {\it Instructor: #3 \hfill } }
   }
   }
   \end{center}
   \markboth{#1}{#1}
   \vspace*{4mm}
}



\begin{document}
\homework{Assignment 2}{due 02/21/2024}{Sam McCauley}{}{}{}

All problems on this assignment are worth 10 points.  (Bonus and extra credit problems are in addition to these totals, and their point values are marked separately.)

\bigskip
For this assignment, you are allowed to work in groups of 2 or 3.  If you do, please write the names of the students in this group here:

\begin{itemize}
	\item Student 1
	\item Student 2
	\item Student 3
\end{itemize}

\newpage
\subsection*{Depth-First Search \& Traversal Applications}

\bigskip

\begin{question} (KT 3.5) 
Let $G = (V, E)$ be a connected undirected graph, and let $T$ be a depth-first spanning tree of $G$
rooted at some node $v$. Prove that if $T$ is also a breadth-first spanning tree
of $G$ rooted at $v$, then $E = T$, that is, all edges of $G$ must be present in $T$ and vice versa. 

\begin{hint}
	Use the properties of BFS and DFS that we proved in class.
\end{hint}

\end{question}
\begin{solution}
\end{solution}


\newpage
\begin{question} \label{q:diameter}
Recall that the diameter of a graph $G$ is the ``longest shortest path'', that is, $diam(G) = \max\{dist(u,v) : u,v \in V\}$, where $d(u,v)$ is the length of the shortest path from $u$ to $v$ in $G$. % and that the length of a path $P$ between two vertices $u$ and $v$ is the number of edges on the path.
%
%
Let $T = (V, E)$ be a tree with $n$ vertices. In this question, we will design an $O(n)$-time algorithm to find the diameter of $T$ by modifying recursive DFS.\footnote{It might seem odd to apply BFS or DFS to a tree---you just get the tree you started with!
However, the traversal of a tree in a particular order can allow for efficient computation of useful quantities.}

In particular, suppose we modify recursive DFS so that it also computes, for each vertex $v$: (i) the diameter of the subtree of $T$ rooted at $v$, and (ii) the longest path from $v$ to a leaf in the subtree of $T$ rooted at $v$.

\begin{enumerate}[label = (\alph*)]

\item Why do you think we need to know both (i) and (ii)?

\begin{solution}
\end{solution}

\item Show how, knowing this information for all children of some vertex $u$, we can determine this information for $u$ itself.

\begin{solution}
\end{solution}

\item Argue why a modified recursive DFS (that computes the diameter as explained in part(b)) would still be $O(n)$ time. (To analyze the
running time, you'd have describe how the algorithm works but only in so much detail as to justify the time bound.)

\begin{solution}
\end{solution}

\end{enumerate}

\end{question}




\newpage
\begin{question} (KT 3.12)
You're helping a group of ethnographers analyze some oral history data they've collected by interviewing members of a village to learn about the lives of people who have lived there over the past two hundred years. From these interviews, they've learned about a set of $n$ people (all
of them now deceased), whom we'll denote $P_1, P_2,\ldots ,P_n$. They've also collected facts about when these people lived relative to one another. Each fact has one of the following two forms:
\begin{itemize}
    \item For some $i$ and $j$, person $P_i$ died before person $P_j$ was born; or
    \item For some $i$ and $j$, the life spans of $P_i$ and $P_j$ overlapped at least partially.
\end{itemize}

Naturally, they're not sure that all these facts are correct; memories are not so good, and a lot of this was passed down by word of mouth. So what they'd like you to determine is whether the data they've collected is at least internally consistent, in the sense that there could have existed a
set of people for which all the facts they've learned simultaneously hold. 

Give an algorithm to do this: either it should produce proposed dates of birth and death for each of the $n$ people so that all the facts hold true, or it should report (correctly) that no such dates can exist---that is, the facts collected by the ethnographers are not internally consistent. You can assume that the ``dates'' have the form $1, 2, \ldots$.

Justify the correctness and running time of your algorithm.

\begin{hint}
Model the collected facts as a directed graph.  The direction of an edge $(x,y)$ can represent an event $x$ occurring before event $y$.  What should be the nodes of this graph?	
\end{hint}

\end{question}
\begin{solution}
\end{solution}





\newpage
\begin{question}[Finding Bridges]
Let $G = (V,E)$ be a connected undirected graph. A \emph{bridge} is an edge $e \in E$ whose deletion disconnects the graph $G$. 
%
In this question, we will design an $O(n+m)$-time algorithm to determine if $G$ contains a bridge.  

\begin{enumerate}[label = (\alph*)]
\item Consider a DFS tree $T$ of $G = (V,E)$.  Can an edge $e \in E \setminus T$ be a bridge?  

\begin{solution}
\end{solution}

\item Give a necessary and sufficient condition 
under which an edge $e = (u,v) \in T$ is a bridge of $G$.   

\begin{solution}
\end{solution}

\item (\textbf{Extra credit (5 points)}) Modify depth-first search to determine whether a given graph $G$ contains a bridge in $O(n+m)$ time.
\begin{solution}
\end{solution}



\end{enumerate}
\end{question}

\newpage
\subsection*{Bonus Feedback Question.}
This question is optional and intended to guide future problem sets.  

\begin{question} (2 points)
This problem set took me:
\begin{multicols}{2}

\begin{enumerate}[label = (\alph*)]
    \item Between 6-8 hours.
    \item Between 4-6 hours.

\end{enumerate}
\columnbreak
\begin{itemize}
    \item[(c)] Between 8-10 hours.
    \item[(d)] Other (please specify)
\end{itemize}
\end{multicols}

\end{question}
\begin{solution}
\end{solution}




\end{document}



