Homework 3 - D Term 2008

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).