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.
-
Arrange these functions under the O notation using only = (equivalent) or ⊂ (strict subset of):
-
-
2log n
-
-
-
23n
-
nn log n
-
-
-
log n
-
-
-
n log n2
-
-
-
nn2
-
-
-
log(log(nn))
-
E.g. for the function n, n + 1, n2, the answer should be
O(n + 1) = O(n) ⊂ O(n2).
Provide brief explanations for your arrangement.
-
Given functions f1, f2, g1, g2 such that f1(n) = O(g1(n)) and f2(n) = O(g2(n)). For each of the following statements, decide whether it is true or false and briefly explain why.
-
-
f1(n) · f2(n) = O (g1(n) · g2(n))
-
-
-
f1(n) + f2(n) = O (max (g1(n), g2(n)))
-
-
-
f1(n)2 = O g1(n)2
-
-
-
log2 f1(n) = O (log2 g1(n))
-
-
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.
-
Solve Kleinberg and Tardos, Chapter 3, Exercise 6.
Ungraded problems
6. Solve Kleinberg and Tardos, Chapter 2, Exercise 6.
2