Analysis of algorithms

Below, you will find the problems assigned for this assignment. Please electronically submit your assign- ment to blackboard.

1. Show that any connected, undirected graph G = (V, E) satisfies |E| ≥ |V | − 1.

2. The square of a graph G = (V,E) is G2 = (V,E2) where (u,v) ∈ E2 if if and only if there exists a path of at most 2 edges from u to v in G. Describe an efficient algorithm to compute the square of a graph. Make sure to take into account which representation you are using.

3. Consider the following divide-and-conquer approach to minimum spanning trees: Given a graph G = (V,E), divide the set V into V1 and V2 such that the size of V1 and V2 differ by at most one. Let E1 be the set of edges only incident on V1, and E2 be the set of edges only incident on V2. Then, recursively solve the minimum spanning tree problem on (V1,E1) and (V2,E2). Finally, select the lightest edge in E crossing the cut (V1,V2). The result is the minimum spanning tree.

Prove or disprove that this correctly finds the minimum spanning tree of G.

4. Suppose you have a graph with a negative cycle. Could you modify the Bellman-Ford algorithm or

Dijkstra’s algorithm to find the shortest simple (no cycles) path in the graph? Why or why not? Consider the following graph represented by an adjacency matrix:

ABCDEFGHIJ A0 4 ∞ 3 2 3 3 1 5 2 B5 0 4 5 4 ∞ ∞ 5 5 5 C5 ∞ 0 2 ∞ 4 4 4 5 3 D1 5 4 0 5 ∞ ∞ 4 5 4 E5 ∞ 5 ∞ 0 1 4 1 3 5 F4 3 ∞ 5 ∞ 0 ∞ 3 4 1 G1 1 5 1 2 4 0 5 5 5 H2 4 1 1 1 ∞ ∞ 0 3 4

I ∞ 1 4 3 3 4 5 ∞ 0 4 J442344∞450

Use Dijkstra’s algorithm to find the shortest path from node E to all other nodes.

6. Suppose that we have a weighted, directed graph G = (V, E) in which edges that leave the source vertex s may have negative weights, all other edges are non-negative, and no negative cycles exist. Argue that Dijkstra’s algorithm correctly gives the shortest paths from s in this case.

7. Traditionally, the weight from a vertex to itself is zero in an adjacency matrix. What happens if instead of using zero along the main diagonal of our adjacency matrix, we use ∞, and then run the Floyd-Warshall algorithm? What will the resulting diagonal values represent?

8. Suppose there exists an undirected graph G = (V, E), whose edges can only be accessed through a “black box” query structure. That is, to determine whether (u, v) ∈ E, you query the black box and it returns yes or no. Prove that, in order to determine if G is connected, any algorithm must, in the worst case, query the existence of every possible edge (u, v).

1