CS502 Fundamentals of Algorithms 23 February 2013

Total Questions: 52
Total Marks: 80
Total MCQs: 40 (Each of 1 Mark)
Total Short Questions: 4 (Each of 2 Mark)
Total Short Questions: 4 (Each of 3 Mark)
Total Long Questions: 4 (Each of 5 Mark)
Q No.1 Suppose you could prove that an NP-complete problem can not be
solved in polynomial time. What would be the consequence?
Q No.2 Let the adjacency list representation of an undirected graph is given
below. Explain what general property of the list indicates that the graph
has an isolated vertex.
a à b à c à e
b à a à d
c à a à d à e à f
d à b à c à f
e à a à c à f
f à c à d à e
Q No.3 What are two cases for computing
Describe Dijkstra’s algorithm working?
Q No.4 The following adjacency matrix represents a graph that consists of four
vertices labeled 0, 1, 2 and 3. The entries in the matrix indicate edge
0 1 2 3
0 0 1 0 3
1 2 0 4 0
2 0 1 0 1
3 2 0 0 0

Q No.5 In the solution of edit distance technique, please describe two solution
given (i) MATHS (ii) ARTS
Q No.6 Variants of shortest path solution briefly?
Q No.7 Explain the following two basic cases according to Floyd-Warshall
Q No.8 Explain the topological sort?

Q No.9 Consider if point pi is dominated by another point pj, we do not need to
use pi for eliminating other points. This follows from the fact that
dominance relation is transitive. If pj dominates pi and pi dominates ph
then pj also dominates ph; pi is not needed.
(Give the answer YES or NO)
Another Paper

What is the Running time of Bellman Ford Algorithem?
O (v+e)

Define Forward Edge
from ancestor to descendent
(u, v) where v is a proper descendent of u in the tree.
A forward edge is a non-tree edge that connects a vertex to a descendent in a DFS-tree.
Edge x-y is less than the capacity there is a forward edge x-y with a capacity equal to the
capacity and the flow

According to the question this means that the problem can be solved in Polynomial time using known NP problem can be solved using the given problem with modified input (an NP problem can be reduced to the given problem) then the problem is NP complete.
The main thing to take away from an NP-complete problem is that it cannot be solved in polynomial time in any known way. NP-Hard/NP-Complete is a way of showing that certain classes of problems are not solvable in realistic time

What is the common problem in communications networks and circuit designing?
A common problem is communications networks and circuit design is that of connecting together a set of nodes by a network of total minimum length. The length is the sum of lengths of connecting wires.
Consider, for example, laying cable in a city for cable t.v.
Explain the following two basic cases according to Floyd-Warshall Algorithm,
1. Don t go through vertex k at all.
2. Do go through vertex k.
Don’t go through k at all
Then the shortest path from i to j uses only intermediate vertices {1, 2, . . . , k − 1}. Hence the length of
the shortest is d(k−1)
Do go through k
First observe that a shortest path does not go through the same vertex twice, so we can assume that we
pass through k exactly once. That is, we go from i to k and then from k to j. In order for the overall path to be as short as possible, we should take the shortest path from i to k and the shortest path from k to j.

Since each of these paths uses intermediate vertices {1, 2, . . . , k − 1}, the length of the path is

Q psedo code of timestamp DFS
1 for (each u 2 V)
2 do color[u] white
3 pred[u] nil
4 time 0
5 for each u 2 V
6 do if (color[u] = white)
7 then DFSVISIT(u)
Prove the following lemma,
Lemma: Given a digraph G = (V, E), consider any DFS forest of G and consider any edge (u, v) ∈ E. If this edge is a tree, forward or cross edge, then f[u] > f[v]. If this edge is a back edge, then f[u] ≤ f[v]

Proof: For the non-tree forward and back edges the proof follows directly from the parenthesis lemma. For example, for a forward edge (u, v), v is a descendent of u and so v’s start-finish interval is contained within u’s implying that v has an earlier finish time. For a cross edge (u, v) we know that the two time intervals are disjoint. When we were processing u, v was not white (otherwise (u, v) would be a tree edge), implying that v was started before u. Because the intervals are disjoint, v must have also finished before u.

How Kruskal’s algorithm works ?
Kruskal’s algorithm works by adding edges in increasing order of weight (lightest edge first). If the next edge does not induce a cycle among the current set of edges, then it is added to A. If it does, we skip it and consider the next in order. As the algorithm runs, the edges in A induce a forest on the vertices. The trees of this forest are eventually merged until a single tree forms containing all vertices
Three matrix are there B1( 5*7) B2 (7*5) ,B3(8,5) perform multiplication on it and proved which is the best
1 (B1)(B2B3)
2 (B1B2)(B3)

One question from The Floyd-Warshall algorithm perform three iteration ?