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