Problem 1 (Common ancestor) Given a rooted tree (T o) with n vertices and a set of k pairs of vertices {(ui, u), (u2, v2), . . . , (uk, tk), design an algorithm to find the lowest common ancestor of ui and v, for all i-1,... ,k. Analyse the running time of your algorithm. Faster and correct algorithms worth more points. You should try to find an algorithm to solve the problem for an undirected rooted tree but if you solve the directed version you will get partial credit. Hint: Consider the labels prev) and post(). Consider the set S of all vertices DFS discovered but haven't finish exploring (i.e. those vertices with a prev) but no post)). Note that the set S changes as we run DFS. Now for any pair with prev(upost(v:), consider the vertex w ES with marimal prev() such that prev(w) prev(w) at the time you discovered vi. Instructions: In this class, assume we're always using min-heap data structure for Dijkstra's. Report runtime accordingly In the algorithm design problems: use the algorithms from class, such as DFS, BFS, Dijkstra's, connected components, etc., as a black-box subroutine for your algorithm. So say what you are giving as input, then what algorithm you are running, and what's the output you're taking from it Here's an example: I take the input graph G, I first find the vertex with largest degree, call it u*. I take the complement of the graph G, call it G. Run Dijkstra's algorithm on G with s and then I get the array dist[v] of the shortest path lengths from s to every other vertex in the graph G. I square each of these distances and return this new array We don't want you to go into the details of these algorithms and tinker with it, just use it as a black-box as showed with Dijkstra's algorithm above. Make sure to explain your algorithm in words, no pseudocode. You can use Explore (subroutine of DFS) as one of the black-box algorithms. Problem 1 (Common ancestor) Given a rooted tree (T o) with n vertices and a set of k pairs of vertices {(ui, u), (u2, v2), . . . , (uk, tk), design an algorithm to find the lowest common ancestor of ui and v, for all i-1,... ,k. Analyse the running time of your algorithm. Faster and correct algorithms worth more points. You should try to find an algorithm to solve the problem for an undirected rooted tree but if you solve the directed version you will get partial credit. Hint: Consider the labels prev) and post(). Consider the set S of all vertices DFS discovered but haven't finish exploring (i.e. those vertices with a prev) but no post)). Note that the set S changes as we run DFS. Now for any pair with prev(upost(v:), consider the vertex w ES with marimal prev() such that prev(w) prev(w) at the time you discovered vi. Instructions: In this class, assume we're always using min-heap data structure for Dijkstra's. Report runtime accordingly In the algorithm design problems: use the algorithms from class, such as DFS, BFS, Dijkstra's, connected components, etc., as a black-box subroutine for your algorithm. So say what you are giving as input, then what algorithm you are running, and what's the output you're taking from it Here's an example: I take the input graph G, I first find the vertex with largest degree, call it u*. I take the complement of the graph G, call it G. Run Dijkstra's algorithm on G with s and then I get the array dist[v] of the shortest path lengths from s to every other vertex in the graph G. I square each of these distances and return this new array We don't want you to go into the details of these algorithms and tinker with it, just use it as a black-box as showed with Dijkstra's algorithm above. Make sure to explain your algorithm in words, no pseudocode. You can use Explore (subroutine of DFS) as one of the black-box algorithms
