\documentclass[11pt]{article}
\usepackage{amsmath,amsthm,amsfonts,amssymb}
\usepackage[margin=1in]{geometry}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{xcolor}
\usepackage{tcolorbox}

\usepackage{tcolorbox}
\usepackage{enumerate}
\usepackage{tikz}


\usepackage{algorithmic}

\usetikzlibrary{arrows.meta}

    \setlength{\headheight}{26pt}
    \pagestyle{fancy}
    \fancyhead[C]{\textbf{Basic Algorithms (Section 7)}\\Fall 2024}
    \fancyhead[R]{HW9 (Due 11/20 22:00)\\ Instructor: Jiaxin Guan}
    \fancyfoot[C]{}
    \fancyfoot[R]{\thepage}
    \renewcommand{\headrulewidth}{0.4pt}
    \renewcommand{\footrulewidth}{0.4pt}  
    

\begin{document}


    %%%% EDIT THIS PART 
    %Put your name and Net ID here
    \fancyhead[L]{Name:  \\ Net ID: }
    %Write your collaborators' names here
    \fancyfoot[L]{Discussion Partners:}
    %%%%%

    %Problem 1
    \begin{tcolorbox}[title={Problem 1 (Cycle Detection, 35 pts)}] \setlength\parindent{1em}
         In this problem you will show how to detect whether an undirected graph $G=(V,E)$ has a  cycle in time $O(|V|)$ (independent of the number of edges).
        \begin{enumerate}[(a)]
            \item Prove that an undirected graph with $|V|$ edges \emph{must} contain a cycle.
            
            \item The above is not true for directed graphs. What is the maximum number of edges a DAG with $n$ nodes can have. Briefly justify your answer. (It may help to remember our maxim: if you see a DAG think about a topological ordering of its vertices!)
        
            \item Explain how to modify an algorithm from class to detect if the undirected graph $G$ contains a cycle in $O(|V|)$ time.
        \end{enumerate}        
    \end{tcolorbox}
    
    %Write your solution here!
    
    %Problem 2
    \begin{tcolorbox}[title={Problem 2 (Failed Magic, 20 pts)}] \setlength\parindent{1em}
         In Lecture 17, we saw a magic trick that can turn a BFS algorithm into a DFS algorithm by simply replacing the queue with a stack. But I mentioned that this magic trick does not work for all BFS algorithms. In this problem, we will see why.

         Below is the BFS algorithm from Lecture 16, but with the queue replaced by a stack attempting to make it into a DFS. Find a counterexmaple, i.e. construct a graph $G=(V,E)$ (can be either directed or undirected), such that for some vertex $s\in V$, running $\textsc{DFS-Visit}(G, s)$ does not correctly give you a DFS tree. The issue is with \textbf{the sequence of vertices} that you visit, so you may safely ignore the \textcolor{teal}{teal}-colored lines for the distances, as they are not used for DFS.

         You should specify the graph $G$ (drawing it out is fine) and the vertex $s$ that you run DFS on, along with a quick explanation of what goes wrong with the (incorrect) DFS tree it produces. (\emph{Hint: A simple example only needs 3 vertices.})

        
        \par\noindent\rule{\textwidth}{0.4pt}
        \smallskip        
        \textsc{DFS-Visit}$(G,s)$
        \begin{algorithmic}[1]
            \FOR{all $v\in V$}
                \STATE \textcolor{teal}{$\texttt{dist}(v)\gets \infty$}
                \STATE $\texttt{parent}(v)\gets \bot$
                \STATE $\texttt{color}(v)\gets \texttt{WHITE}$
            \ENDFOR
            \STATE \textcolor{teal}{$\texttt{dist}(s)\gets 0$}
            \STATE $\texttt{color}(s)\gets \texttt{YELLOW}$
            \STATE $\textsf{Stack}.\texttt{push}(s)$
            \WHILE{\textsf{Stack} is not empty}
                \STATE $u\gets \textsf{Stack}.\texttt{pop}()$
                \FOR{all $v \in \mathsf{Adj}[u]$}
                \IF{$\texttt{color}(v)=\texttt{WHITE}$}
                    \STATE \textcolor{teal}{$\texttt{dist}(v)\gets \texttt{dist}(u)+1$}
                    \STATE $\texttt{parent}(v)\gets \texttt{u}$
            \STATE $\texttt{color}(v)\gets \texttt{YELLOW}$
            \STATE $\textsf{Stack}.\texttt{push}(v)$
                \ENDIF
                \ENDFOR
                \STATE $\texttt{color}(u)\gets \texttt{GREEN}$
            \ENDWHILE
        \end{algorithmic}
        \vspace{-2mm}
        \par\noindent\rule{\textwidth}{0.4pt}
    \end{tcolorbox}

    %Write your solution here!

    \newpage
    %Problem 3
    \begin{tcolorbox}[title={Problem 3 (Topological Sort, 20 pts)}] \setlength\parindent{1em}
         How many valid topological sorts does the directed graph below have? List all the valid topological sorts in the following table. One of them has been listed as an example, where node A is output first and D is output last.

        \centering

        \vspace{2em}
        \begin{tabular}{ccccccc}
            \hline
             1. & A & B & C & F & E & D \\
             2. &  &  &  &  &  & \\
             &  &  &  &  &  & \\
             &  &  &  &  &  & \\
             &  &  &  &  &  & \\
             &  &  &  &  &  & \\
             &  &  &  &  &  & \\
             &  &  &  &  &  & \\
             &  &  &  &  &  & \\
            \hline
        \end{tabular}

        \vspace{2em}
        \begin{tikzpicture}[>={Latex[width=3mm,length=3mm]},
                node distance=1.5cm,
                scale=2,
                thick,main/.style = {draw, circle}]
            % Nodes
            \node[main,scale=1.8] (A) {A};
            \node[main,scale=1.8] (B) [above right of=A] {B};
            \node[main,scale=1.8] (C) [right of=B] {C};
            \node[main,scale=1.8] (D) [below right of=C] {D};
            \node[main,scale=1.8] (E) [below left of=D] {E};
            \node[main,scale=1.8] (F) [below right of=A] {F};

            %Edges
            \draw[->] (A) -- (B);
            \draw[->] (A) -- (F);
            \draw[->] (B) -- (C);
            \draw[->] (B) -- (F);
            \draw[->] (E) -- (D);
            \draw[->] (B) -- (D);
            \draw[->] (C) -- (F);
            \draw[->] (C) -- (D);
            \draw[->] (C) -- (E);
        \end{tikzpicture}
        \vspace{0.5em}
    \end{tcolorbox}

    %Write your solution here!

    \newpage
    %Problem 4
    \begin{tcolorbox}[title={Problem 4 (Number of Simple Paths, 25 pts)}] \setlength\parindent{1em}
        Give an algorithm that given a Directed Acyclic Graph (DAG, defined as a directed graph without cycles) and two vertices $s,t$, returns the \emph{number} of simple paths from $s$ to $t$. Your algorithm should run in time $O(|V|+|E|)$. Justify the correctness and runtime of your proposed algorithm. (Your algorithm does not need to list the simple paths, only needs to give the count.)

        (\emph{Hint: What is the letter after C? What is the letter before Q?})
    \end{tcolorbox}
    %Write your solution here!

\end{document}