Reference no: EM132402924

Describe and analyze an algorithm" means you must provide pseudocode, a proof of correctness and complexity analysis.

Question 1: Let (S, T) and (S', T') be minimum (s, t)-cuts in some flow network G. Prove that (S ∩ S', T υ T') and (S υ S', T ∩ T_i) are also minimum (s, t)-cuts in G.

Question 2: Mulder and Scully have computed, for every road in the United States, the exact probability that someone driving on that road won't be abducted by aliens. Agent Mulder needs to drive from Langley, Virginia to Area 51, Nevada. What route should he take so that he has the least chance of being abducted?

More formally, you are given a directed graph G = (V, E), where every edge e has an independent safety probability p(e). The safety of a path is the product of the safety probabilities of its edges. Design and analyze an algorithm to determine the safest path from a given start vertex s to a given target vertex t. You may assume that all necessary arithmetic operations can be performed in 0(1) time.

For example, with the probabilities shown above, if Mulder tries to drive directly from Langley to Area 51, he has a 50% chance of getting there without being abducted. If he stops in Memphis, he has a 0.7 x 0.9 = 63% chance of arriving safely. If he stops first in Memphis and then in Las Vegas, he has a 1-0.7 x 0.1 x 0.5 = 96.5% chance of being abducted! (That's how they got Elvis, you know.)

Question 3: Suppose we are given an undirected graph G in which every vertex has a positive weight.

(a) Describe and analyze an algorithm to find a spanning tree of G with minimum total weight. (The total weight of a spanning tree is the sum of the weights of its vertices.)

(b) Describe and analyze an algorithm to find a path in G from one given vertex s to another given vertex t with minimum total weight. (The total weight of a path is the sum of the weights of its vertices.)

Question 4: A graph G = (V,E) is dense if E = Θ(V²). Describe a modification of Jarniles minimum-spanning tree algorithm that runs in O(V²) time (inde-pendent of E) when the input graph is dense, using only elementary data structures-in particular, without using Fibonacci heaps. This variant of Jarnik's algorithm was first described by Edsger Dijkstra in 1958.