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.
