\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{makecell}

\usepackage{algorithmic}

    \setlength{\headheight}{26pt}
    \pagestyle{fancy}
    \fancyhead[C]{\textbf{Basic Algorithms (Section 7)}\\Fall 2024}
    \fancyhead[R]{HW11 (Due 12/11 22:00)\\ Instructor: Jiaxin Guan}
    \fancyfoot[C]{}
    \fancyfoot[R]{\thepage}
    \renewcommand{\headrulewidth}{0.4pt}
    \renewcommand{\footrulewidth}{0.4pt} 
    
    \usetikzlibrary{arrows.meta, quotes}    

\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 0
    \begin{tcolorbox}[title={Problem 0 (Course Evaluation, 0 points)}] \setlength\parindent{1em}
        If you haven't done so already, please fill out the course evaluation at \url{https://go.blueja.io/c74Z6Qe6T0G4GxKD_gfpgA} or by scanning the QR code below.
        
        \vspace{1em}
        \centering
        \includegraphics[scale=0.7]{qr-24fall}  
    \end{tcolorbox}

    %Problem 1
    \begin{tcolorbox}[title={Problem 1 (MST Algorithms, 20 pts)}] \setlength\parindent{1em}
         Consider the following undirected graph $G=(V,E)$.
        
        {\centering
        \vspace{2em}
        \begin{tikzpicture}[>={Latex[width=3mm,length=3mm]},
                node distance=1.5cm,
                scale=2,
                main/.style = {draw, circle},
                every edge quotes/.style = {auto}]
            % Nodes
            \node[main,scale=1.5] (A) {A};
            \node[main,scale=1.5] (B) [above right of=A] {B};
            \node[main,scale=1.5] (C) [right of=B] {C};
            \node[main,scale=1.5] (D) [right of=C] {D};
            \node[main,scale=1.5] (G) [below right of=A] {G};
            \node[main,scale=1.5] (F) [right of=G] {F};
            \node[main,scale=1.5] (E) [right of=F] {E};

            %Edges
            \draw (A) edge["1"] (B);
            \draw (B) edge["7"] (C);
            \draw (C) edge["3"] (D);
            \draw (D) edge["10"] (E);
            \draw (C) edge["2"] (F);
            \draw (C) edge["6"] (E);
            \draw (A) edge[swap, "4"] (G);
            \draw (G) edge[swap, "8"] (F);
            \draw (A) edge["5"] (F);
            \draw (A) edge[swap, "9"] (C);
            \draw (F) edge[swap, "11"] (E);

        \end{tikzpicture}

        \vspace{1em}
        }

        \begin{enumerate}[(a)]
         \item Illustrate a run of Kruskal’s algorithm on this graph by filling in the table below. State at each step which edge is added to the tree. We have filled the first step in for you. Here, \textbf{we only want the edge added to the tree and not every edge that is considered.}
         
         {
         \centering
         \vspace{1em}
         \begin{tabular}{c|c|c|c|c|c|c}
             \textbf{Step} & 1 & 2 & 3 & 4 & 5 & 6\\
             \hline
             \textbf{Edge Added} & $AB$ & \phantom{XX} & \phantom{XX} & \phantom{XX} & \phantom{XX} & \phantom{XX} \\
         \end{tabular}
         \vspace{1em}
         
         }

         \item Illustrate a run of Prim’s algorithm on this graph starting from vertex $A$ by filling in the table below. State at each step which edge is added to the tree. We have filled the first step in for you. Here, \textbf{we only want the edge added to the tree and not every edge that is considered.}     

         {
         \centering
         \vspace{1em}
         \begin{tabular}{c|c|c|c|c|c|c}
             \textbf{Step} & 1 & 2 & 3 & 4 & 5 & 6\\
             \hline
             \textbf{Edge Added} & $AB$ & \phantom{XX} & \phantom{XX} & \phantom{XX} & \phantom{XX} & \phantom{XX} \\
         \end{tabular}
         \vspace{1em}
         
         }
        \end{enumerate}
    \end{tcolorbox}

    %Write your solution here!
    
    %Problem 2
    \begin{tcolorbox}[title={Problem 2 (Pizza Delivery, 30 points)}]\setlength\parindent{1em}

    Alice, who lives at a vertex $s$ of a directed, weighted graph $G = (V, E)$ (with non-negative weights), is going to her friend's house at vertex $h$ for dinner. Naturally, Alice wants to get from $s$ to $h$ as soon as possible, but it appears that her friend is terrible at cooking, so along the way she wants to get a pizza from a pizza store just in case her friend cooks something inedible.  Let's say the pizza stores form a subset of the vertices $B\subset V$. Thus, starting at $s$, Alice must go to some vertex $b \in B$ of her choice, and then head from $b$ to $h$ using the shortest overall route possible (assuming she wastes no time at the pizza store). We can help Alice reach $h$ as soon as possible, by solving the following sub-problems.
    
    \begin{enumerate} 
        \item Compute the shortest distance from $s$ to all pizza stores $b\in B$.
        \item Compute the shortest distance from every pizza store $b \in B$ to $h$. Note that this is the dual of
        the single-source shortest path where we are now asking for the shortest path from every node to a particular destination.
        \item Combine part 1 and 2 to solve the full problem.
    \end{enumerate}
    
    A straightforward solution is to run Dijkstra’s algorithm twice (once in part 1 and once in part 2). In this problem, you will improve this solution by running Dijkstra's algorithm only \textbf{once}.  Specifically, you should define a new graph $G'$ on $2|V|$ vertices and at most $2|E|+|V|$ edges (and appropriate weights for these edges), so that the original problem can be solved using a single Dijkstra call on $G'$. Briefly argue correctness of your proposed solution. (\emph{Hint: This
    is another problem on reductions. You might want to refresh your memories on Problem 2 in Homework 8, which is also a reduction problem.})
    \end{tcolorbox}
	%Write your solution here!

    \newpage
    %Problem 3
    \begin{tcolorbox}[title={Problem 3 (Dijkstra Practice, 25 points)}]\setlength\parindent{1em}
        Show the running of Dijkstra’s algorithm for finding the distance from $A$ to all other vertices in the following graph. You should show the updated distances to all the vertices (i.e., the key of the vertex in the priority queue) after each step in the algorithm.
        
        {\centering
        \vspace{2em}
        \begin{tikzpicture}[>={Latex[width=3mm,length=3mm]},
                node distance=2.5cm,
                scale=2,
                thick,main/.style = {draw, circle},
                every edge quotes/.style = {auto}]
            % Nodes
            \node[main,scale=1.5] (A) {A};
            \node[main,scale=1.5] (B) [right of=A] {B};
            \node[main,scale=1.5] (C) [below right of=B] {C};
            \node[main,scale=1.5] (D) [below of=C] {D};
            \node[main,scale=1.5] (H) [below left of=A] {H};
            \node[main,scale=1.5] (G) [below of=H] {G};
            \node[main,scale=1.5] (F) [below right of=G] {F};
            \node[main,scale=1.5] (E) [below left of=D] {E};

            %Edges
            \draw[->] (A) edge["14"] (B);
            \draw[->] (A) edge[swap, "3"] (H);
            \draw[->] (C) edge[swap, "12"] (B);
            \draw[->] (C) edge["6"] (D);
            \draw[->] (D) edge["1"] (E);
            \draw[->] (F) edge["1"] (C);
            \draw[->] (F) edge["9"] (D);
            \draw[->] (F) edge[swap, "8"] (E);
            \draw[->] (F) edge["0"] (G);
            \draw[->] (G) edge[swap, "15"] (A);
            \draw[->] (G) edge[swap, "4"] (B);
            \draw[->] (H) edge[swap, "2"] (G);
            \draw[->] (B) edge["5"] (F);

        \end{tikzpicture}

        \vspace{1em}
        }

        For the ease of representing your solution, simply complete the following table. The first row (Step 0) represents the initial values.

        \hspace{-2em}
        {
        \centering
        \vspace{1em}
        \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|}
        \hline
          & \makecell{Vertex \\extracted \\from PQ} & $\mathsf{dist}(A)$ & $\mathsf{dist}(B)$ & $\mathsf{dist}(C)$ & $\mathsf{dist}(D)$ & $\mathsf{dist}(E)$ &
         $\mathsf{dist}(F)$ &
         $\mathsf{dist}(G)$ &
         $\mathsf{dist}(H)$\\
         \hline
         0 & - & $0$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ & $\infty$ \\
         \hline
         1 & $A$ & & & & & & & & \\
         \hline
         2 & & & & & & & & & \\
         \hline
         3 & & & & & & & & & \\
         \hline
         4 & & & & & & & & & \\
         \hline
         5 & & & & & & & & & \\
         \hline
         6 & & & & & & & & & \\
         \hline
         7 & & & & & & & & & \\
         \hline
         8 & & & & & & & & & \\
         \hline
        \end{tabular}
        \vspace{1em}
        
        }

    \end{tcolorbox}

    \newpage
    %Problem 4
    \begin{tcolorbox}[title={Problem 4 (Detecting Negative-Weight Cycles, 25 points)}] \setlength\parindent{1em}
        In lecture we mentioned why it does not make sense to consider shortest paths on a graph with negative-weight cycles, but how do we detect if a graph contains such a cycle? Recall that a negative-weight cycle is defined as a cycle where the sum of the weights of the edges in the cycle is negative. Show how one can use the output of the Floyd-Warshall algorithm to detect the presence of
        a negative-weight cycle in a directed graph. Briefly argue the correctness of your algorithm.
    \end{tcolorbox}
    
\end{document}