%---------change this for every latex homework
\def\yourid{mst3k}
\def\collabs{list collaborators's computing IDs}
\def\sources{Cormen, et al, Introduction to Algorithms. \emph{(add others here)}}
% -----------------------------------------------------
\def\duedate{Friday, March 18, 2022 at {\bf 11:30 pm}}
\def\duelocation{via Gradescope}
\def\htype{Basic}
\def\hunit{B}
\def\hnumber{1}
\def\course{{cs4102 - algorithms - spring 2022}}%------
%-------------------------------------
%-------------------------------------
\documentclass[10pt]{article}
\usepackage[colorlinks,urlcolor=blue]{hyperref}
\usepackage[osf]{mathpazo}
\usepackage{amsmath,amsfonts,graphicx}
\usepackage{latexsym}
\usepackage[top=1in,bottom=1.4in,left=1.25in,right=1.25in,centering,letterpaper]{geometry}
\usepackage{color}
\definecolor{mdb}{rgb}{0.1,0.6,0.4}
\definecolor{cit}{rgb}{0.05,0.2,0.45}
\pagestyle{myheadings}
\markboth{\yourid}{\yourid}
\usepackage{clrscode}
\usepackage{listings}
\newenvironment{proof}{\par\noindent{\it Proof.}\hspace*{1em}}{$\Box$\bigskip}
\newcommand{\handout}{
\renewcommand{\thepage}{Unit \hunit: \htype~Homework \hnumber~-~\arabic{page}}
\noindent
\begin{center}
\vbox{
\hbox to \columnwidth {\sc{\course} \hfill}
\vspace{-2mm}
\hbox to \columnwidth {\sc due \MakeLowercase{\duedate} \duelocation\hfill {\Huge\color{mdb}\hunit\hnumber{\Large\MakeLowercase{\htype}}(\yourid)}}
}
\end{center}
\vspace*{1mm}
\hrule
\vspace*{1mm}
{\footnotesize \textbf{Collaboration Policy:} You are encouraged to collaborate with up to 3 other students, but all work submitted must be your own {\em independently} written solution. List the computing ids of all of your collaborators in the \texttt{collabs} command at the top of the tex file. Do not share written notes, documents (including Google docs, Overleaf docs, discussion notes, PDFs), or code. Do not seek published or online solutions for any assignments. If you use any published or online resources (which may not include solutions) when completing this assignment, be sure to cite by naming the book etc.\ or listing a website's URL. Do not submit a solution that you are unable to explain orally to a member of the course staff. Any solutions that share similar text/code will be considered in breach of this policy. Please refer to the syllabus for a complete description of the collaboration policy.
\vspace*{1mm}
\hrule
\vspace*{2mm}
\noindent
\textbf{Collaborators}: \collabs\\
\textbf{Sources}: \sources}
\vspace*{2mm}
\hrule
\vskip 2em
}
\newcommand{\solution}[1]{\color{blue}\hfill\break\noindent\textbf{Solution:} #1\color{black}}
\newcommand{\altsolution}[1]{\color{blue}\hfill\break\noindent\textbf{Solution (Alternative):} #1\color{black}}
%\newcommand{\solution}[1]{}
%\newcommand{\altsolution}[1]{}
\newcommand{\bit}[1]{\{0,1\}^{ #1 }}
%\dontprintsemicolon
%\linesnumbered
\newtheorem{problem}{\sc\color{cit}problem}
\newtheorem{practice}{\sc\color{cit}practice}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newcommand{\Z}{\mathbb{Z}} % This might be useful for Integers!
\begin{document}
\thispagestyle{empty}
\handout
%----Begin your modifications here. Add your answer in the \solution environment for each question
%--- Problem 1 ------------------------------------------------------------------------------
\begin{problem} Short Questions on BFS \end{problem}
\begin{enumerate}
\renewcommand{\theenumi}{\Alph{enumi}}
\item What is the maximum number of vertices that can be on the queue at one time in a BFS search? Briefly explain the situation that would cause this number to be on the queue.
\solution{
Your answer here!
}
\item If you draw the BFS tree for an undirected graph $G$, some of the edges in $G$ will not be part of the tree. Explain why it's not possible for one of these non-tree edges to connect two vertices that have a difference of depth that's greater than 1 in the tree.
\solution{
Your answer here!
}
\end{enumerate}
%--- Problem 2 ------------------------------------------------------------------------------
\begin{problem} True or False. (You don't have to explain this in your submission, but you should understand the reason behind your answer.) \end{problem}
\begin{enumerate}
\renewcommand{\theenumi}{\Alph{enumi}}
\item If you use BFS to detect a cycle in an undirected graph, an edge that connects to a vertex that's currently on the queue or has been removed from the queue indicates a cycle as long as that vertex is not the parent of the current node.
\solution{
Your answer here!
}
\item If you use DFS-visit on a \textit{directed} graph with $V>1$ starting at vertex $v_1$, you will always visit the same number of vertices that you would if you started at another node $v_2$.
\solution{
Your answer here!
}
\item If you use DFS-visit on a connected \textit{undirected} graph with $V>1$ starting at vertex $v_1$, you will always visit the same number of vertices that you would if you started at another node $v_2$. (If it were not connected, would your answer change?)
\solution{
Your answer here!
}
\end{enumerate}
%--- Problem 3 ------------------------------------------------------------------------------
\begin{problem} Finding Cycles Using DFS \end{problem}
In a few sentences, explain how to recognize a directed graph has a cycle in the DFS-visit algorithm's code we saw in class. How does this need to be modified if the graph is undirected?
\solution{
Your answer here!
}
%--- Problem 4 ------------------------------------------------------------------------------
\begin{problem} Finding a path between two vertices \end{problem}
Describe the modifications you would make to DFS-visit() given in class to allow it to find a path from a start node $s$ to a target node $t$. The function should stop the search when it finds the target and return the path from $s$ to $t$.
\solution{
Your answer here!
}
%--- Problem 5 ------------------------------------------------------------------------------
\begin{problem} Labeling Nodes in a Connected Components \end{problem}
In a few sentences, explain how you'd modify the DFS functions taught in class to assign a value $v.cc$ to each vertex $v$ in an undirected graph $G$ so that all vertices in the same connected component have the same $cc$ values. Also, count the number of connected components in $G$. \\
In addition to your explanation, give the order-class of the time-complexity of your algorithm.
\solution{
Your answer here!
}
%--- Problem 6 ------------------------------------------------------------------------------
\begin{problem} BFS and DFS Trees \end{problem}
Consider the BFS tree $T_B$ and the DFS tree $T_D$ for the same graph $G$ and same starting vertex $s$.
In a few sentences, clearly explain why for every vertex $v$ in $G$, the depth of $v$ in the BFS tree cannot be greater than its depth in the DFS tree. That is:
$$ \forall \, v \in G.V, depth(T_B, v) \leq depth(T_D, v)$$
(Here the depth of a node is the number of edges from the node to the tree's root node. Also, you can use properties of BFS and DFS that you've been taught in class. We're not asking you to prove those properties.)
\solution{
Your answer here!
}
\begin{problem} Gradescope Submission \end{problem}
Submit a version of this \verb|.tex| file to Gradescope with your solutions added, along with the compiled PDF. You should only submit your \verb|.pdf| and \verb|.tex| files.
\end{document}