Starting from:
$30

$24

HW 2


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):

        (a) 2log n

        (b) 23n
        (c) nn log n

        (d) log n

        (e) n log n2

        (f) nn2

        (g) 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.

    3. 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.

        (a) f1(n) · f2(n) = O (g1(n) · g2(n))

        (b) f1(n) + f2(n) = O (max (g1(n), g2(n)))


1





        (c) f1(n)2 = O g1(n)2

        (d) log2 f1(n) = O (log2 g1(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.

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


Ungraded problems

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









































2

More products