Q1) You are given a weighted undirected graph G(V, E) and its MST T(V, E). Now suppose an edge (a, b) E has been deleted from the graph. You need to devise an algorithm to update the MST after deletion of (a, b). Describe an algorithm for updating the MST of a graph when an edge (a, b) is deleted from the MST (and the underlying graph). Its time complexity must be better than running an MST algorithm from scratch. State and explain the time complexity of your algorithm. Analyze time complexity of your algorithm. You can assume that all edge weights are distinct, that the graph has E edges and V vertices after the deletion, that the graph is still connected after the deletion of the edge, and that your graph and your MST are represented using adjacency lists.

Q2) Can you use the DFS algorithm to compute the number of distinct paths between two given nodes, s and t? Two paths are considered distinct if they differ by 1 or more edges. If you think the answer is yes, then provide the pseudo-code for a DFS based algo that computes this number in O(|V|+|E|). If you think the answer is no, draw a graphwith eight vertices in total,with two of its vertices labeleds and t, in which DFS will fail to compute the number of distinct pathsbetween s and t.

Q3) CM of Punjab has decided to build a new road in Lahore. He has a choice of k roads from which he can only build one. However, secretly, CM is only interested in two places in the city: s and t (his office and home). He wishes to build the road which, when added into the city, reduces the cost of the shortest path from s to t the most. He has hired you to write a computer program to tell him which of the k roads to build for this purpose. The input to your program is going to be a directed weighted graph and list of k weighted edges not already in the graph.

(a)Write an algorithm that does the job in O(k(|E|)lg|V|).Note that since k itself is O(|V|2 )this is a pretty slow algorithm.

(b) CM is in a hurry. He wants you to write an algorithm that works in O (k+|E|lg|V|), only. Can you do it?