CSCI 570 HW 2

Description

1. What is the worst-case runtime performance of the procedure below?

c = 0

i = n

while i > 1 do

for j = 1 to i do

c = c + 1

end for

i = floor(i/2)

end while

return c

Provide a brief explanation for your answer.

2. Arrange these functions under the O notation using only = (equivalent) or ⊂ (strict subset of):

2. 1. 2^{log n}

2. 2. 2³ⁿ

   3. _nn log n

2. 4. log n

2. 5. n log n²

2. 6. nⁿ²

2. 7. log(log(nⁿ))

E.g. for the function n, n + 1, n², the answer should be

O(n + 1) = O(n) ⊂ O(n²).

Provide brief explanations for your arrangement.

3. Given functions f₁, f₂, g₁, g₂ such that f₁(n) = O(g₁(n)) and f₂(n) = O(g₂(n)). For each of the following statements, decide whether it is true or false and briefly explain why.

3. 1. f₁(n) · f₂(n) = O (g₁(n) · g₂(n))

3. 2. f₁(n) + f₂(n) = O (max (g₁(n), g₂(n)))

1. 3. f₁(n)² = O g₁(n)²

1. 3. log₂ f₁(n) = O (log₂ g₁(n))

4. Given an undirected graph G with n nodes and m edges, design an O(m+ n) algorithm to detect whether G contains a cycle. Your algorithm should output a cycle if G contains one.

4. Solve Kleinberg and Tardos, Chapter 3, Exercise 6.

Ungraded problems

6. Solve Kleinberg and Tardos, Chapter 2, Exercise 6.

2