Due Date: April 1, 2008 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.
Consider the graph below.
- (10 Points)
Depict the adjacency matrix representation of this graph.
- (10 Points)
Depict the adjacency list representation of this graph.
- (20 Points) Problem 2.
Consider the algorithm to test bipartiteness of an undirected graph
described in Section 3.4 of the textbook.
- (10 Points)
Write down detailed pseudo-code for this algorithm.
Your pseudo-code must be the modification of
the BFS pseudo-code (on page 90-91) described in
Section 3.4 of the textbook.
- (10 Points)
Analyze the time complexity of your algorithm
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.
Show that your algorithm is O(n+m).
- (20 Points) Problem 3.
A binary tree is a rooted tree in which each node can have at most 2 children.
We will say that the root node is at Level 0,
the children of the root are at Level 1,
the grandchildren of the root are at Level 2,
the greatgrandchildren of the root are at Level 3, etc.
Let's denote by h the maximum level of the tree (= the
height of the tree).
- (10 Points)
Construct a precise formula for the
mathematical function max_nodes_binary_level(i) such
that given a value i, 1 ≤ i ≤ h, produces the maximum
possible number of nodes at level i of a binary tree.
Justify your answer.
- (10 Points)
Construct a precise formula for the
mathematical function max_nodes_binary_tree(h)
such that given h ≥ 0, produces the maximum
possible total number of nodes that a binary tree of height h can have.
Justify your answer.
- (40 Points) Problem 4.
Let G=(V,E) be an undirected graph with n nodes and m edges, and (u,v) an edge in E,
where u and v are nodes in V.
- (12 Points)
Consider the problem of determining whether or not G has a cycle
containing edge (u,v).
Write a detailed algorithm (pseudo-code) that receives G and (u,v) as its input
and it outputs "yes" if G has a cycle containing edge (u,v),
and "no" if G has no cycles containing edge (u,v).
Your pseudo-code must use and/or modify the BFS
pseudo-code on page 90-91 of your textbook.
The runtime of your algorithm should be O(n+m).
Explicitly state if your algorithm uses an adjacency matrix or
an adjacency list representation of the graph.
- (14 Points)
Prove that your algorithm is correct. That is, prove that it
always produces the right answer for the given input.
- (14 Points)
Analyze the time complexity of your algorithm
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.
Show that your algorithm is O(n+m).