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?

Answer:

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.

Answer:-

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

Answer:

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]

Answer:-

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 ?

Answer:

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 ?

DOWNLOAD SOLUTION HERE