CS 4120 Analysis of Algorithms B term 2019 Homework 1, October 31, 2019 Due date: November 7, 2019 Asymptotic running time. Basic graph algorithms. Every homework will receive a grade between 0 to 100. The (maximal) grade of every question is identical and the sum of grades is the final grade. Homework must be legible and stapled, with writing on only one side of each piece of paper. 1. Order the following list of functions and arrange them in ascending order of growth rate. That is, if a function g(n) immediately follows a function f(n) then it should be the case that f(n) = O(g(n)). Briefly explain your ordering. • f1(n) = n2.5 • f2(n) = √ 2n • f3(n) = n + 10 • f4(n) = 10n • f5(n) = 102n • f6(n) = n2 log n • f7(n) = n1/ logn 2. Let G be an undirected graph with n vertices. Prove that G is a tree (connected with no cycles) if and only if G is connected and contains exactly n− 1 edges. 3. Let G be an undirected graph with n vertices and m edges. Give an efficient algorithm that tests whether G contains a cycle. Prove the correctness of your algorithm and analyze its running time. You may assume the graph is connected. 1 4. (a) Let G = (V,E) be an undirected graph connected graph with n > 1 vertices and m edges. Prove there must exist a node v ∈ V such that removing v from G results with a connected graph. Give an O(n + m) algorithm which finds such a node and prove its correctness. (b) Prove or disprove: for every strongly connected directed graph G = (V,E) there exists a vertex v ∈ V such that removing v from G results with a strongly connected graph. 5. Let G = (V,E) be an undirected graph. A cut (S, T ) in G is a partition of the set of vertices of V to two disjoint sets S, T such that S∪T = V . An edge e ∈ E crosses a cut (S, T ) if one of its endpoints belongs to S and the other belongs to T . In other words, e = (u, v) crosses (S, T ) if it is not the case that both u, v ∈ S or both u, v ∈ T . Prove: G is connected if and only if for every cut (S, T ) in the graph there exists an edge e ∈ E that crosses (S, T ). 2
