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