Question $1$: Dead Ends $(25$ points$)$

You work for a road construction company and your manager asks you to list all dead$-$ended intersections in the city. You are given an undirected graph G $,$ with vertices representing intersections, and edges representing roads in the city. You can assume that there are no vertices with $0$ edges, i$.$e$.,$ all roads are connected. Dead ends are represented as vertices that have only one edge.

a$.$ Describe at a high level how you would determine which vertices are dead$-$ended. Your function should return a list of vertices, and the only parameter should be the graph G$,$ with G$.$V as a list of vertices and G$.$E as a list of edges. $(3$ points$)$

b$.$ Provide the pseudocode for your function. $(5$ points$)$

Your manager now wants you to find which roads $($edges$)$ lead to dead$-$ends, rather than just the intersections. Remember that the order of choosing edges from a vertex in a breadth$-$first search is arbitrary. An edge leads to a dead$-$end if a breadth$-$first traversal beginning from a dead$-$ended intersection MUST traverse that edge in a deterministic order. For example:

In the image to the right, intersections A and J are dead$-$ends. A breadth$-$first search from A MUST traverse $($A$,$B$),$ then $($B$,$ C$),$ and $($C$,$D$),$ in that exact order, so those will be roads that lead to dead$-$ends. Once we reach $\backslash ($ D $\backslash ),$ we can arbitrarily choose any of $($D$,$E$),($D$,$ G$),$ or $($D$,$F$),$ so those roads will not be marked as dead$-$ended.

A breadth$-$first search from J must traverse $($J$,$I$),$ so that road leads to a dead$-$end. However, from point $\backslash ($ I $\backslash ),$ we can choose either of $\backslash ((\backslash$mathrm$\{$I$\},\backslash$mathrm$\{$H$\})\backslash )$ or $\backslash ((\backslash$mathrm$\{$I$\},\backslash$mathrm$\{$K$\})\backslash )$ to traverse, so these roads will not be marked as dead$-$ended.

c$.$ Write the pseudocode for an algorithm that, given a graph G $,$ will return a list of edges that lead to dead$-$ends. You may use the function you wrote in part b$)$ as a subprocedure. $(7$ points$)$

d$.$ Provide the big$-$O runtimes of part b$)$ and c$),$ and explain your answer. $(10$ points$)$