CSCI570 HOMEWORK 2 Solution

Q1. What is the tight bound on worst-case runtime performance of the procedure below? Give an explanation for your answer. (10 points)
int c = 0; for(int k = 0; k <= log2n; k++) for(int j = 1; j <= 2^k; j++) c=c+1
return c
Q2. 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. (10 points)
Q3. For each of the following indicate if f = O(g) or f = Θ(g) or f = Ώ(g) (10 points)
f(n) g(n)
1 nlog(n) n2log(n2)
2 log(n) log(log(5n))
3 n1/3 (log(n))3
4 2n 23n
5 n4/log(n) n(log(n))4
Q4. Indicate for each pair of expressions (A,B) in the table below, whether A is O, Ω, or Ө of B (in other words, whether A=O(B), A= Ω(B), or A= Ө (B)). Assume that k and C are positive constants. You can mark each box with Yes or No. No justification needed. (9 points)
(Note: log is base 2)
A B O Ω Θ
n3+log(n)+n2 C*n3
n2 C*n*2log(n)
(2n)*(2k) n2k
Q5. Find the total number of possible topological orderings in the following graph and list all of them (15 points)

Q6. Given a directed graph with m edges and n nodes where every edge has weight as either 1 or 2, find the shortest path from a given source vertex ‘s’ to a given destination vertex ‘t’. Expected time complexity is O(m+n). (8 points)
Q7. 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. (12 points)
(a) f1(n) · f2(n) = O (g1(n) · g2(n))
(b) f1(n) + f2(n) = O (max (g1(n), g (n)))
(c) f1(n)2 = O g1(n)2
(d) log2 f1(n) = O (log2 g1(n))
Q8. Design an algorithm which, given a directed graph G = (V, E) and a particular edge e ∈ E, going from node u to node v determines whether G has a cycle containing e. The running time should be bounded by O(|V | + |E|). Explain why your algorithm runs in O(|V | + |E|) time. (8 points)
Q9. Solve Kleinberg and Tardos, Chapter 3, Exercise 6. (8 points)
Q10. Solve Kleinberg and Tardos, Chapter 3, Exercise 9. (10 points)