$30
CSCI 570 -HW 2 1 Graded Problems 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 2. Arrange these functions under the O notation using only = (equivalent) or ⊂ (strict subset of): (a) 2log n (b) 23n (c) n n log n (d) log n (e) n log n 2 (f) n n 2 (g) log(log(n n)) E.g. for the function n, n + 1, n 2 , the answer should be O(n + 1) = O(n) ⊂ O(n 2 ). 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 you think it is true or false and give a proof or counterexample. (a) f1(n) · f2(n) = O (g1(n) · g2(n)) (b) f1(n) + f2(n) = O (max (g1(n), g2(n))) (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. 2 Practice Problems 1. Solve Kleinberg and Tardos, Chapter 2, Exercise 6. 2. Solve Kleinberg and Tardos, Chapter 3, Exercise 6.