CS2223 Algorithms Homework 3 - D Term 2009

PROF. CAROLINA RUIZ

Due Date: April 7, 2009 at 1:00 PM
See course policy regarding late homework submissions

• Homework Instructions:
• Read Chapter 3 of the textbook in detail.
• See Useful logarithm and exponential facts.
• This is an individual homework. No collaboration is allowed.
• Submit a hardcopy of your written homework solutions by the beginning of class (i.e., 1:00 pm) the day the homework is due.
• See the course webpage for the late homework submission policy.

• Homework Problems:

1. (20 Points) Problem 1. In this problem, we observe connectivity properties of undirected and of directed graphs.

• (10 Points). Let G=(V,E) be any connected undirected graph. Prove that there is a node u in V such that removing u (together with all its incident edges) from G leaves G connected. Explain your answer in detail.
Hint: Use the tree structure constructed during the execution of BFS.

• (10 Points). Give an example of a graph G=(V,E) which is strongly connected (see definition in Section 3.5 of the textbook and in the textbook slides) but such that the removal of any node in G would make G not strongly connected. Note that you need to show that: (1) G is strongly connected, and that (2) for each node u in your graph, removing u and all the edges incident to u from G would result in a graph that is not strongly connected.

2. (45 Points) Problem 2. Let G=(V,E) be an undirected graph. The complement of G is defined as the undirected graph GC = (V,EC), with the same set of nodes V, but such that an edge (u,v) belongs to EC if and only if (u,v) doesn't belong to E. That is, EC = { (u,v) | (u,v) ∉ E}.

1. (5 Points) Write detailed pseudo-code for an algorithm that receives a graph G=(V,E) as input, and produces GC = (V,EC) as output. Assume that both G and GC are represented using an adjacency matrix representation. The more efficient your algorithm, the better. Explain your work.

2. (10 Points) Analyze the time complexity of your algorithm above instruction by instruction. Produce a function T(n,m) that measures the runtime of your algorithm for an input graph with n nodes and m edges. Provide a tight asymptotic bound f(n,m) for T(n,m). That is, provide a function f(n,m) and prove that T(n,m) is Θ(f(n,m)).