### CS2223 Algorithms Homework 3 - D Term 2008

#### PROF. CAROLINA RUIZ

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.
• See the course webpage for the late homework submission policy.

• Homework Problems:

1. (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.

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

3. (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.

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