Description
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) n
2
log(n
2
)
2 log(n) log(log(5
n
))
3 n
1/3
(log(n))
3
4 2
n 2
3n
5 n
4
/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 Ω Θ
n
3+log(n)+n
2 C*n
3
n
2 C*n*2
log(n)
(2
n
)*(2
k
) n
2k
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), g2
(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)
