## Description

1. What is the tight bound on worst-case runtime performance of the procedure below? Give an explanation for your answer.

1 int c = 0;

2 for (int k = 0; k <= log (n); k ++)

3 for (int j = 1; j <= 2^k; j ++)

4 c++;

5 return c;

2. 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.

3. For each of the following indicate if f = O(g) or f = Ω(g) or f = Θ(g) or none of these.

4. Indicate for each pair of expressions (A,B) in the table below, whether A = O(B), A = Ω(B), A = Θ(B).

Assume that k and C are positive constants.

5. Find the total number of possible topological orderings in the following graph and list all of them

A B C

G D E F

6. 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. Time complexity is O(m+n)

7. Given functions f1, f2, g1, g2 such that f1(n) = O(g1(n)) and f2(n) = O(g2(n)). Check the following

statements, give a proof or counterexample.

8. 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

9. We have a connected graph G = (V, E), and a specific vertex u ∈ V . Suppose we compute a depth-first

search tree rooted at u, and obtain a tree T that includes all nodes of G. Suppose we then compute a

breadth-first search tree rooted at u, and obtain the same tree T. Prove that G = T. (In other words, if

T is both a depth-first search tree and a breadth-first search tree rooted at u, then G cannot contain any

edges that do not belong to T.)

10. Suppose that an n-node undirected graph G=(V,E) contains two nodes s and t such that the distance

between s and t is strictly greater than n/2. Show that there must exist some node v, not equal to either

s or t, such that deleting v from G destroys all s-t paths. (In other words, the graph obtained from G by

deleting v contains no path from s to t.) Give an algorithm with running time O(m + n) to find such a

node v.