CSCI 570 Fall 2021 HW 2 Due September 9th 1 Graded Problems 1 What is the worst case runtime performance of the procedure below 2 Arrange these functions under the O notation using only equivalent or strict subset of c 0 i n while i 1 do for j 1 to i do c c 1 end for i oor i 2 end while return c a 2log n b 23n c nn log n d log n e n log cid 0 n2 cid 1 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 1 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 cid 0 g1 n 2 cid 1 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 2
View Full Document
Unlocking...