Algorithm Design and Analysis September 5, 2008Pennsylvania State University CSE 565, Fall 2008Adam Smith Handout 3Homework 2 – Due Friday, September 12, 2008Please refer to the general information handout for the full homework policy and options.Reminders• Your solutions are due before the lecture. Late homework will not b e acc epted.• Collaboration is permitted, but you must write the solutions by yourself without assistance,and be ready to explain them orally to a member of the course staff if asked. You must alsoidentify your collaborators. Getting solutions from outside sources such as the Web or studentsnot enrolled in the class is strictly forbidden.• To facilitate grading, please write down your solution to each problem on a separate sheet ofpaper. Make sure to include all identifying information and your collaborators on each sheet.Your solutions to different problems will be graded separately, possibly by different people, andreturned to you independently of each other.• For problems that require you to provide an algorithm, you must give a precise description ofthe algorithm, together with a proof of correctness and an analysis of its running time. You mayuse algorithms from class as subroutines. You may also use any facts that we proved in class orfrom the book.Reading Review chapters 2.1-2.4, read chapter 3 in Kleinberg Tardos.Exercises These should not be handed in, but the material they cover may appear on exams:1. (Graph representations) Questions in this problem refer to the adjacency list and adjacencymatrix representations defined on pages 87–89 of KT.You are given a directed graph G = (V, E) with |V | = n vertices and |E| = m edges. Let GRbethe graph obtained by reversing the directions of all the edges in G. For each of the following,give an e ffic ient algorithm and analyze its running time.If G is given in the adjacency list representation,(a) compute the out-degree of each vertex;(b) compute the in-degree of each vertex;(c) compute the adjacency list represe ntation of GR.If G is given in the adjacency matrix representation,(d) compute the adjacency matrix of GR.2. Give two algorithms to detect whether a given undirected graph has a cycle. If the graph containsa cycle, your algorithms should output one (not all of them, just one). Base the first algorithmon BFS and the second, on DFS. The running time of your algorithms should be the same asthe running times of BFS and DFS. Explain why your algorithms are correct and run in therequired time .13. A directed graph G = (V, E) is singly connected if for all vertices u, v in V there is at mostone simple path from u to v. (Recall that a path is simple if all vertices on the path are distinct.)Give an efficient algorithm to determine whether or not a directed graph is singly connected.Hint: Run DFS from each vertex.Problems to be handed inPage limits: The answer to each problem should fit in 2 pages (or one double-sided sheet) ofpaper. Longer answers will be penalized.1. (More Asymptotics)(a) Prove that for any positive numbers a, b > 0, we have nb= ω(loga(n)).There are several ways to approach this. One way is to use L’Hospital’s rule for evaluatinglimits together with the following fact: f(n) = ω(g(n)) if and only if limn→∞f(n)g(n)= +∞.(b) Prove or disprove: There exist two strictly increasing functions f(n), g(n), such that neitherf(n) = O(g(n)) nor g(n) = O(f (n)) holds.(c) Prove or disprove: If h(n) = dn log(n)e, then n = Θ(h(n)/ log h(n)).2. (Basic proof techniques)(a) (Induction) Chapter 3, problem 5.(b) (Contradiction) Chapter 3, problem 7.3. (Shortest cycles containing a given edge) Give an algorithm that takes as input a (undi-rected) graph G = (V, E) and an edge e0∈ E, and outputs a shortest cycle that contains e (ifno cycle containing e exists, the algorithm should output “no cycle”).(Note: See the reminder above on problems that require an algorithm. Remember to provecorrectness of your algorithm. You may use algorithms from class as subroutines.)4. (Articulation points) A vertex v ∈ V is an articulation point in an undirected graph if removingv from the graph increases the number of connected components (that is, removing v breaks upone of the graph’s connected components).Give as efficient an algorithm as you can for finding all the articulation points of a graph G =(V, E) given in adjacency list format. State the running time of your algorithm in terms ofm = |E| and n = |V |.5. * (Extra credit) Given a graph G, we say that paths (u, a1), (a1, a2), ..., (ak, v) and (u, b1), (b1, b2),..., (bt, v) are vertex disjoint if they are both valid paths in G and they do not pass through anyof the s ame vertices, that is, the sets {a1, a2, ..., ak} and {b1, b2, ..., bt} are disjoint.Prove that a graph G has no articulation points if and only if for every pair of vertices u and v,there exist two vertex-disjoint paths from u to