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.
- 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 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}.
- Adjacency Matrix Representation
- (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.
- (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 GC = (V,EC)
as output. Assume that both G and GC 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).