Homework 3 - D Term 2009

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.
**Remember to show your work and explain your answers.**Correct answers without complete explanations won't receive full credit. Incorrect answers with explanations may receive partial credit.- See the course webpage for the late homework submission policy.

**Homework Problems:****(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.

**(45 Points) Problem 2**. Let G=(V,E) be an undirected graph. The complement of G is defined as the undirected graph G^{C}= (V,E^{C}), with the same set of nodes V, but such that an edge (u,v) belongs to E^{C}if and only if (u,v) doesn't belong to E. That is, E^{C}= { (u,v) | (u,v) ∉ E}.**Adjacency Matrix Representation****(5 Points)**Write detailed pseudo-code for an algorithm that receives a graph G=(V,E) as input, and produces G^{C}= (V,E^{C}) as output. Assume that both G and G^{C}are represented using an adjacency matrix representation. The more efficient your algorithm, the better. Explain your work.**(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)).

**Adjacency List Representation****(15 Points)**Write another detailed pseudo-code for an algorithm that receives a graph G=(V,E) as input, and produces G^{C}= (V,E^{C}) as output. Assume that both G and G^{C}are represented using an adjacency list representation. (Do NOT assume that the neighbors of a node are organized in any particular order in the node's adjacency list). The more efficient your algorithm, the better. Explain your work.**(15 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 an upper asymptotic bound g(n,m) for T(n,m). That is, provide a function g(n,m) and prove that T(n,m) is O(g(n,m)).

**(35 Points) Problem 3**. Let G=(V,E) be an undirected graph. Let u be a node in G. Recall that the*degree*of a node u is the number of neighbors of u in G, or in other words, the number of edges in E that are incident to u.**(10 Points)**Write a detailed pseudo-code for an algorithm that receives a graph G=(V,E) as input with |V|=n, |E|=m, and produces an array SumNeighborsDegrees[1...n] as output, where for each node u in V, SumNeighborsDegrees[u] contains the sum of the degrees of all the neighbors of u. Assume that G is represented using an adjacency list representation. Your algorithm should run in linear time, that is it should be O(n+m).**(10 Points)**Prove that your algorithm above is correct.**(15 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. Prove that T(n,m) is O(n+m).