1. Arrange these functions under the O notation using only = (equivalent) or ⊂ (strict subset of):
a) 2logn
b) 23n
c) nn logn
d) logn
e) nlog(n2)
f) nn²
g) log(log(nn))
All logs are base 2. (10 pts)
2. 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. (12 pts) 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)))
3. Given an undirected graph G with n nodes and m edges, design an O(m+n) algorithm todetect whether G contains a cycle. Your algorithm should output a cycle if there is one. (12 pts)
4. Solve Kleinberg and Tardos, Chapter 2, Exercise 6. (14 pts)
5. What Mathematicians often keep track of a statistic called their Erdős Number, after thegreat 20th century mathematician. Paul Erdős himself has a number of zero. Anyone who wrote a mathematical paper with him has a number of one, anyone who wrote a paper with someone who wrote a paper with him has a number of two, and so forth and so on. Supposing that we have a database of all mathematical papers ever written along with their authors: (6 pts)
a. Explain how to represent this data as a graph.
b. Explain how we would compute the Erdős number for a particular researcher.
c. Explain how we would determine all researchers with Erdős number at most two.
6. Given a DAG, give a linear-time algorithm to determine if there is a simple path that visitsall vertices. (8 pts)
Ungraded Problems
1. What is the worst-case 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.
