# 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
g
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
weights.
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
Algorithm,
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)
ij
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
DFS(G)
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]