## 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)