Introduction to Analysis of Algorithms - Graph and algorithms

Please provide step by step explanation and runtime analysis thank you. 

 

Transcribed Image Text:

Problem 1 (Construction work ). Suppose we have access to undirected graph G = (V,E) that represents a set of towns and roads connecting them. We also know the distance d of each road (u, v) E. The local government is tasked with building roads between two towns s,t V with the goal of decreasing the driving time between them as much as possible. They have narrowed down a list of candidate roads P = {(a1, bi)..... (ak, bk)} that we could build. Here, a, b; V are towns with no direct route between them in E. We also know the distance d'; between them. Due to financial constraints, the city government only has funding to build up to 2 roads. Your task is to find which roads would reduce the driving time between s and t by as much as possible when added to G (or none at all). You may use that Dijkstra's algorithm can run in time O(E + V log V). a. Describe a brute-force-like algorithm to determine which roads from P to use. State the runtime of this algorithm with respect to n = |V|, m = |E|, k. The local mayor realizes that with how large k is, your simple algorithm will not finish before re-election season. Towns s and t are home to many important residents and so finding the best way to connect them is top priority. Suddenly, an idea pops into your head: you can reduce to finding the shortest path on a new graph G = (V', E') created from G and P (and some ingenuity). This new graph should encode that you have original paths in G as well as new possible paths using edges in P while respecting that we can construct only 2 new roads. b. C. d. First, describe how to create this new graph G' = (V', E') using G and P. [Hint: V' should consist of existing towns while also tracking of how many new roads it took to reach there.] Explain how you can use Dijkstra's algorithm and G' to determine the solution. What is V' and edges |E' in terms of n, m, k? Use these to state and prove the asymptotic runtime of your algorithm in terms of n, m, k. Problem 1 (Construction work ). Suppose we have access to undirected graph G = (V,E) that represents a set of towns and roads connecting them. We also know the distance d of each road (u, v) E. The local government is tasked with building roads between two towns s,t V with the goal of decreasing the driving time between them as much as possible. They have narrowed down a list of candidate roads P = {(a1, bi)..... (ak, bk)} that we could build. Here, a, b; V are towns with no direct route between them in E. We also know the distance d'; between them. Due to financial constraints, the city government only has funding to build up to 2 roads. Your task is to find which roads would reduce the driving time between s and t by as much as possible when added to G (or none at all). You may use that Dijkstra's algorithm can run in time O(E + V log V). a. Describe a brute-force-like algorithm to determine which roads from P to use. State the runtime of this algorithm with respect to n = |V|, m = |E|, k. The local mayor realizes that with how large k is, your simple algorithm will not finish before re-election season. Towns s and t are home to many important residents and so finding the best way to connect them is top priority. Suddenly, an idea pops into your head: you can reduce to finding the shortest path on a new graph G = (V', E') created from G and P (and some ingenuity). This new graph should encode that you have original paths in G as well as new possible paths using edges in P while respecting that we can construct only 2 new roads. b. C. d. First, describe how to create this new graph G' = (V', E') using G and P. [Hint: V' should consist of existing towns while also tracking of how many new roads it took to reach there.] Explain how you can use Dijkstra's algorithm and G' to determine the solution. What is V' and edges |E' in terms of n, m, k? Use these to state and prove the asymptotic runtime of your algorithm in terms of n, m, k.