CS502

SOLVED SUBJECTIVE
FINAL TERM

1) In strong components problem what complete refers to?

Ans: Complete in the sense that that it is possible from any location in the network to reach any
other location in the digraph.
2) How shortest path information is propagated in graph using Bell-Ford algorithm?
ANS. Bellman-Ford algorithm, solves the single-source shortest-paths problem allow negative-
weight edges in the in-put graph and produce a correct answer as long as no negative-weight
cycles are reachable from the source. Bellman-ford is based on performing repeated relaxation
.Bellman ford applies relaxation to every edge of the graph and repeats this V-1 times.

3) How can we make it possible for an array of “n” elements that every element has equal
probability of ‘1/n’ to be selected as pivot elements?

4) Define according to KrusKal” s algorithm

a) Create set(u) create a set containing a single item u.
b) Find set(u) Find the set that contains u
c) Union (u, v) merge the set containing u and set containing v into a common set.

5) Write the indicates that the graph is complete?

Ans: Acomplete graphis an undirected graph in which every pair of vertices is adjacent
6) What is the recurrence relation for binary search and give some details for it and write
asymptotic analysis at end?
7) Prove the Lemma:
Consider a diagraph G = ( V,E ) and any DFS forest for G. G has a cycle if and only if the
DFS forest has a back edges ?
Ans: If there is back edge (u,v) then v is an ancestor of u and by tree edges from u to v we get a cycle . we
show the contra positive suppose there are no back edges .by the lemma above each of the remaining
types of edges ,tree, forward and cross all have the property that they go from vertices with higher finish
time to the vertices with lower finish time .thus along any path finish times decrease monotonically
implying there can be no cycle.
Difference b/w back ward and forward 2 marks

Ans Back edges are those edges.(u,v) where v is an ancestor of u in a depth-first tree. .

. Forward edges are those non tree edges.(u,v) where v is a proper descendant of u in a depth-
first tree.

Polynomial time algorithm 2 marks

ANS:A polynomial time algorithm is any algorithm that runs in o(n k) time .A problem is
solvable in polynomial time if there is a polynomial time algorithm for it.
Describe Minimum Spanning Trees Problem with examples. 2 marks
ans; A common problem is communications networks ans circuit design is that of connecting
together a set of nodes by network of total minimum length .The length is the sum of lengths of
connecting wires. the computational problem is called minimum spanning tree(MST) problem. A
MST is a tree of minimum weight.
3n^2+7n-12 ke lower or upper bound solve kana tha 3 marks
Code of fib memorization . 3 marks

Ans. FIB(n)

1 if (n < 2)

2 then return n

3 else return FIB(n − 1) + FIB(n − 2)

write iterative dfs lgorithm?5 marks

ans ITERATIVE DFS(s)

1 PUSH(s)

2 while stack not empty

3 do v ← POP()

4 if v is unmarked

5 then mark v

6 for each edge (v, w)

7 do PUSH(w)

Q No.1 Suppose you could prove that an NP-complete problem can not be solved in
polynomial time. What would be the consequence?

Ans: The importance of NP-complete problems should now be clear. If any NP-complete
problem is solvable

in polynomial time, then every NP-complete problem is also solvable in polynomial time.
Conversely, if

we can prove that any NP-complete problem cannot be solved in polynomial time, the every
NP-complete problem cannot be solvable in polynomial time.
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ebadcadef
dbcfeacffcdeg
Q No.3 What are two cases for computing?

ANS
Describe Dijkstra's algorithm working?

ANS: Dijkstra’s algorithm works on a weighted directed graph G = (V, E) in which all edge

weights are non-negative, i.e., w(u, v) _ 0 for each edge (u, v) 2 E.

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
ANS: NO. Because number of rows and number of columns are always same
Q No.5 In the solution of edit distance technique, please describe two solution
given (i) MATHS (ii) ARTS
ANS:

Q No.6 Variants of shortest path solution briefly?

ANS: There are a few variants of the shortest path problem.
Single-source shortest-path problem: Find shortest paths from a given (single) source
vertex s 2 V to every other vertex v 2 V in the graph G.
Single-destination shortest-paths problem: Find a shortest path to a given destination
vertex t from each vertex v. We can reduce the this problem to a single-source problem
by reversing the direction of each edge in the graph.
Single-pair shortest-path problem: Find a shortest path from u to v for given vertices u
and v. If we solve the single-source problem with source vertex u, we solve this problem
also. No algorithms for this problem are known to run asymptotically faster than the
best single-source algorithms in the worst case.
All-pairs shortest-paths problem: Find a shortest path from u to v for every pair of
vertices u and v. Although this problem can be solved by running a single-source
algorithm once from each vertex, it can usually be solved faster.
Ref: Handouts Page No.153
Q No.7 Explain the following two basic cases according to Floyd-Warshall Algorithm,?
ANS There are two basic cases:
1. Don’t go through vertex 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
2. Do go through vertex 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 ( 1) ( 1) kk dd ik kj 
Ref: Handouts Page No.162
Q No.8 Explain the topological sort?
Ans: A topological sort of a DAG is a linear ordering of the vertices of the DAG such that for
each edge (u, v),u appears before v in the ordering. Computing a topological ordering is actually
quite easy, given a DFS of the DAG. For every edge (u, v) in a DAG, the finish time of u is
greater than the finish time of v (by the lemma). Thus, it suffices to output the vertices in the
reverse order of finish times

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)

working of dijkstra algorithm working

write two steps of dynamic programming

Dynamic programming is essentially recursion without repetition. Developing a dynamic programming

algorithm generally involves two separate steps:

Formulate problem recursively. Write down a formula for the whole problem as a simple combination
of answers to smaller sub problems.

Build solution to recurrence from bottom up. Write an algorithm that starts with base cases and works
its way up to the final solution
pseoudo code for strong component?

Ans: sTRONGCOMPONENTS(G)

1 Run DFS(G) computing finish times f[u]

2 Compute GT
3 Sort vertices of GT in decreasing f[u]

4 Run DFS(GT) using this order

5 Each DFS tree is a strong component

hum nay ak railway track bishana hy hum konsa algorithm select krain gay k hum minimum track kar
sakian
write code of dikstra algorith ?

ans:

DIJKSTRA((G, w, s))

1 for ( each u belong V )

2 do d[u] ← ∞

3 pq.insert (u, d[u])

4 d[s] ← 0; pred [s] ← nil; pq.decrease key (s, d[s]);

5 while ( pq.not empty ())

6 do u ← pq.extract min ()

7 for ( each v ∈ adj[u])

8 do if (d[u] + w(u, v) < d[v])

9 then d[v] = d[u] + w(u, v)

10 pq.decrease key (v, d[v])

11 pred [v] = u
Difference b/w back ward and forward 2 marks (repeated)
Polynomial time algorithm 2 marks

A polynomial time algorithm is any algorithm that runs in O(nk) time.A problem is solvable in
polynomial time if there is a polynomial time algorithm for it.

Describe Minimum Spanning Trees Problem with examples. 2 marks )(REPEATED)

Ak code given that us ka asymptotic notation bateni the. 3 marks

3n^2+7n-12 ke lower or upper bound solve kana tha 3 marks
Code OF fib memorization . 3 marks (REPEATE)
itterative step OF DFS: 5 marks
Q No.1 Suppose you could prove that an NP-complete problem can not be solved in
polynomial time. What would be the consequence?(REPEATED)
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 à dc à a à d à e à fd à b à c à fe à a à c à ff à 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.
1 2 3
1 3
1 2 4
2 1 1
3 2
Q No.5 In the solution of edit distance technique, please describe two solution given (i)
MATHS (ii) ARTSQ 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)I forget other

1) Give Detail Example of 2-d mazama Problem

Suppose you want to buy a car. You want the pick the fastest car. But fast cars are expensive; you want
the cheapest. You cannot decide which is more important: speed or price. Definitely do not want a car if
there is another that is both faster andcheaper. We say that the fast, cheap car dominates the
slow,expensive car relative to your selection criteria. So, given a collection of cars, we want to list those
cars that are not dominated by any other.. • Let a point p in 2-dimensional space be given by its integer
coordinates, p = (p.x, p.y). • A point p is said to be dominated by point q if p.x ≤ q.x and p.y ≤ q.y.

• Given a set of n points, P = {p1, p2, . . . , pn} in 2-space a point is said to be maximal if it is
notdominated by any other point in P.

The car selection problem can be modelled this way: For each car we associate (x, y) pair where x is the
speed of the car and y is the negation of the price. High y value means a cheap car and low y means
expensive car. Think of y as the money left in your pocket after you have paid for the car . Maximalpoints
correspond to the fastest and cheapest cars.

The 2-dimensional Maxima is thus defined as

• Given a set of points P = {p1, p2, . . . , pn} in 2-space, output the set of maximal points of P, i.e.,those
points pi such that pi is not dominated by any other point of P.
Where Clique Problem Arise?

ANS: The clique cover problem arises in applications of clustering. We put an edge between two nodes if
theyare similar enough to be clustered in the same group. We want to know whether it is possible to
cluster allthe vertices into k groups.
What is Decision Problem and give Examples
ANS: A problem is called a decision problem if its output is a simple “yes” or “no” (or you may this of
this as true/false, 0/1, accept/reject.) We will phrase may optimization problems as decision problems.

explain with Flody Algorithm ( Running time and Space used )?

Ans: Let G = (V, E) be a directed graph with edge weights. If (u, v) ∈ E is an edge then w(u, v) denotes
itsweight. δ(u, v) is the distance of the minimum cost path between u and v. We will allow G to have
negative edges weights but will not allow G to have negative cost cycles. We will present an Θ(n3)
algorithm for the all pairs shortest path. The algorithm is called the Floyd-Warshall algorithm and is
based on dynamic programming. the running time is Θ(n3). The space used by the algorithm is Θ(n2).

Fibonacci sequence 2mark

Ans: This sequence, in which each number is the sum of the two preceding numbers, has proved
extremely fruitful and appears in many different areas of mathematics and science. The Fibonacci
numbers F n are defined as follows:

F0 = 0

F1 = 1

Fn = Fn−1 + Fn−273

Clique cover problem 2mark

ans: Given a graph G and an integer k, can we find k subsets of vertices V1, V2, . . . , VK , such that SiVi
= V , and that each Vi is a clique of G. The clique cover problem arises in applications of clustering. We
put an edge between two nodes if they are similar enough to be clustered in the same group. We want to
know whether it is possible to cluster all the vertices into k groups.

Communication design problem (MST).

ans: 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.

Q: what is forest and free tree?

An acyclic, undirected graph is a forest, and a connected, acyclic, undirected graph is a(free) tree
Strong connected component problem?

Ans.Are the components fully connected?. A digraph is strongly connected if for every pair of vertices u,
v in V , u can reach v and vice versa. We would like to write an algorithm that determines whether a
digraph is strongly connected. In fact, we willsolve a generalization of this problem, of computing the
strongly connected components of a digraph
Heapify? 5marks

Ans: There is one principal operation for maintaining the heap property. It is called Heapify. we are given
an element of the heap which we suspect may not be in valid heap order, but we assume that all of other
the elements in the subtree rooted at this element are in heap order. In particular this root element may be
too small. To fix this we “sift” it down the tree by swapping it with one of its children. Which child? W e
should take the larger of the two children to satisfy the heap ordering property. This continues recursively
until the element is either larger than both its children or until its falls all the way to the leaf level

Dijkstra Algorithm?
ans: Dijkstra’s algorithm is a simple greedy algorithm for computing the single-source shortest-paths to
all other vertices. Dijkstra’s algorithm works on a weighted directed graph G = (V, E) in which all
edgeweights are non-negative, i.e., w(u, v) ≥ 0 for each edge (u, v) ∈ E.
Define Floyd Marshall 5marks
Ans: Let G = (V, E) be a directed graph with edge weights. If (u, v) ∈ E is an edge then w(u, v) denotes
its weight. δ(u, v) is the distance of the minimum cost path between u and v. We will allow G to have
negative edges weights but will not allow G to have negative cost cycles. We will present an
Θ(n3)algorithm for the all pairs shortest path. The algorithm is called the Floyd-Warshall algorithm and is
based on dynamic programming. Formulation: Define d( k)ij to be the shortest path from i to j such that
any intermediate vertices on the path are chosen from the set {1, 2, . . . , k}. The path is free to visit any
subset of these vertices and in any order. There are two basic cases:

1. Don’t go through vertex k at all.

2. Do go through vertex k.
what is the running time and space used by Floyd Marshall 3marks

Ans: the running time is Θ(n3). The space used by the algorithm is Θ(n2). repeated
DFS algorithm 3marks

How we convert the shortest path problem into a single source problem? 2 Marks

Ans: Find a shortest path to a given destination vertex from each vertex. By reversing the direction of
each edge in the graph, we can reduce this problem to a single-source problem
If problem A reduces (is polynomial-time reducible) to problem B and B is NP-complete then A is
NP-complete ?

Ans. Yes because if np complete is reducible in polynomial then all can be in polynomial time.
Consider the following code:
For(j=1; j<n;j++)
For(k=1; k<15;k++)
For(l=5; l<n; l++)
{
Do_something_constant();
}
What is the order of execution for this code.?
An arbitrary graph with G(V,E) with E = |V|- I is a tree. true or false tell briefly 2 marks

ANS:Yes
Analysis of the brute-force maxima algorithm?
Ans: Assume that the input size is n, and for the running time we will count the number of time that any
element of P is accessed. Clearly we go through the outer loop n times, and for each time through this
loop, we go through the inner loop n times as well. The condition in the if-statement makes four accesses
to P. The output statement makes two accesses for each point that is output. In the worst case every points
maximal these two access are made for each time through the outer loop
Given a digraph G = (V, E), consider any DFS forest of G and consider any edge (u, v) 2 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] ?

ANS: 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’ Is 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.
Where the Clique Cover Problem arises 3 marks(repeated)
What is decision problem, also explain with example? 2 marks

ANS A problem is called a decision problem if its output is a simple “yes” or “no” (or you may this of
this as true/false, 0/1, accept/reject.) We will phrase may optimization problems as decision problems. For
example, the MST decision problem would be: Given a weighted graph G and an integer k, does G have a
spanning tree whose weight is at most k
How Dijkstra’s algorithm operates? 3

Ans: Dijkstra’s algorithm is based on the notion of performing repeated relaxations. The algorithm
operates by maintaining a subset of vertices, S ⊆ V , for which we claim we know the true distance, d[v]
= δ(s, v).Initially S = ∅, the empty set. We set d[u] = 0 and all others to ∞. One by one we select vertices
from V − S to add to S.
write code of relaxing a vertex 5

Ans: RELAX((u, v))

1 if (d[u] + w(u, v) < d[v])

2 then d[v] ← d[u] + w(u, v)

3 pred[v] = u
Explain why the statement “The running time of A is at least On2 ” is meaning less 5 Marks
Show the strongly connected components of the following graph using DFS algorithm. Take node E
as a starting node. [You can show final result in exam software and need not to show all
intermediate steps].5 marks
Q. Heap sort Algorithm?

Ans: We build a max heap out of the given array of numbers A[1..n]. We repeatedly extract the maximum
item from the heap. Once the max item is removed, we are left with a hole at the root. To fix this, we will
replace it with the last leaf in tree We will apply a heapify procedure to the root to restore the heap.
Q. Difference between Back edge and cross edge. (REPEATED)
Q.HOW Prim's Algorithm builds the MST?

Ans: Prim’s algorithm builds the MST by adding leaves one at a time to the current tree. We start with a
root vertex r; it can be any vertex. At any time, the subset of edges A forms a single tree
Q. Do go through k & Dont go through k at all?

Ans

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 d(k−1 )ik+ d( k−1 )kj
Q. BFS pseudo code in graph?

Ans:

TRAVERSE(s)

1 enqueue(∅, s)

2 while queue not empty

3 do dequeue(p, v)

4 if (v is unmarked )

5 then mark v

6 parent (v) ← p

7 for each edge (v, w)

8 do enqueue(v, w)
Q. heapify? REPEATED)
7. Prove that the generic TRAVERSE (S) marks every vertex in any connected graph exactly once
and the set of edges (v, parent (v)) with parent (v) ¹F form a spanning tree of the graph.

Ans: Call an edge (v, parent(v)) with parent(v) 6 = ∅, a parent edge. For any node v, the path of parent
edges v → parent(v) → parent(parent(v)) → . . . eventually leads back to s. So the set of parent edges
form a connected graph .Clearly, both end points of every parent edge are marked, and the number of
edges is exactly one less than the number of vertices. Thus, the parent edges form a spanning tree.
8. Apply Kruskal’s algorithms on the following graph.[You can show final result in exam software
and need not to show all intermediate steps].
1) polynomial time algorithm? (Repeated)
2) what is a run time analysis and its two criteria?

Ans:

The main purpose of run time analysis will be measuring the execution time. THE running time of an
implementation of the algorithm would depend upon the speed of the computer, Two criteria for
measuring running time are worst-case time and average-case time.

Worst-case time is the maximum running time over all (legal) inputs of size n. Let I denote an input
instance, let |I| denote its length, and let T (I) denote the running time of the algorithm on input Average-
case time is the average running time over all inputs of size n. Let p(I) denote the probability of seeing
this input. The average-case time is the weighted sum of running times with weights being the
probabilities:

3) Dijkstra algorithm correctness criteria two conditions?

Ans: the correctness of Dijkstr’s algorithm by Induction. We will use the definition that δ(s, v)denotes the
minimal distance from s to v.For the base case

1. S = {s}

2. d(s) = 0, which is δ(s, s)

4) Floyd algorithm (repeated)
5) a table is given and we have to make the adjacency list and matrix
6) an mst graph is given and we have to calculate its weigth?
-Q Describe depth-first search algorithm in graphs with iterative version.

Ans:

ITERATIVE DFS(s)

1 PUSH(s)

2 while stack not empty

3 do v ← POP()

4 if v is unmarked

5 then mark v

6 for each edge (v, w)

7 do PUSH(w)
- Where clique problem arises. (repeated)
- what is decision problem.expalin wd example.repeated
- find the minimum cost spanning tree.....diagram was given...
- there was given a recursive search function we have to the complexity of that search.
3 marks................
-Q Floyd-warshall algorithem with respect to running time n spaced used.(repeated)
- Q how khurkal algorithm works?

Ans: 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. This can be done
using the Union-Find data structure which supports the following O(log n) operations:

Create-set(u): Create a set containing a single item u.

Find-set(u): Find the set that contains u

Union(u,v): merge the set containing u and set containing v into a common set.
- T/F:A sequence of matrix in column of dynamic problem table for a instance of knapsack is
always non decreasing? explain briefly.
2 marks...............
-Q informal definition of algorithm.?

Ans: An algorithm is any well-defined computational procedure that takes some values, or set of values,
as input and produces some value, or set of values, as output. An algorithm is thus a sequence of
computational steps that transform the input into output
- differentiate farwrd n backwrd edge. (Repeated)
- how dijshkra algorithm operate. . (Repeated)

Q1) answer the follwing according to Floyd Marshall 1) runing time 2) space use? . (Repeated)

2) write suedo code of dijkstra algorithm? 5marks. (Repeated)

3)Give a detailed example for 2-d maxima problem 2marks . (Repeated)

4)Make Adjacency list from the given table 5marks. (Repeated)

5) how generic algorithms work with minimum spaning tree 3marks

Ans: A generic greedy algorithm operates by repeatedly adding any safe edge to the current spanning
tree.
6) Floyd-Warshall matrix diya tha os py 3 itration apply karny thy 5marks (for example see page
no 165 to167 on handouts. Figures )
7) Which points should be supposed to prove the correctness of the Dijkstra's Algorithm 3marks

Ans: Assume that d(v) = δ(s, v) for every v belong to S and all neighbors of v have been relaxed. If d(u)
≤ d(u 0)for every u’ belong to then d(u) = δ(s, u), and we can transfer u from V to S, after which d(v) =
δ(s, v) for every v belong to S.
Fibonacci sequence 2mark (repeated)
Clique cover problem 2mark (repeated)

Make Adjacency list from the given table 3marks (repeated)

Communication design problem (MST).

Ans: 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.
Strong connected component problem? repeated)

Heapify proof..... 5marks repeated)

Dijkstra Algorithmn repeated)

Define Floyd Marshall 5marks repeated)

what is the running time and space of Floyd Marshall 3marks repeated)

DFS algorithm 3marks repeated)

(1) give a detailed example of 2-d maxima ? repeated)

(2) what is common problem in communication networks and circuit designing? 2

Ans: 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
(3) write psuedo code of relaxing a vertex 5 repeated)
(4) write suedo code of dijkstra algorithm? 5 repeated)
(5) define NP completeness 5 repeated)
(6) define floyed warshall algorithm in these two cases 5 repeated)
do not go through a vertex k at all
do go through a vertex k
(7) Define DAG 3

Ans: A directed graph that is acyclic is called a directed acyclic graph (DAG)

4 Questions of 5 Marks

1) Write steps of sieve techniques?

ANS: The sieve technique works in phases as follows. It applies to problems where we are interested in
finding a single item from a larger set of n items. We do not know which item is of interest, We select a
random element of A partition A into three parts.
1. A[q] contains the pivot element x,

2. A[1..q − 1] will contain all the elements that are less than x and

3. A[q + 1..n] will contains all elements that are greater than x.
2) Write Psuedo code of Dijkstra's algorithm repeated)
3) Prove the Lemma:
Consider a diagraph G = ( V,E ) and any DFS forest for G. G has a cycle if and only if the DFS
forest has a back edges repeated)
Where the clique cover problem is used?

Ans: The clique cover problem arises in applications of clustering. We put an edge between two nodes if
they are similar enough to be clustered in the same group. We want to know whether it is possible to
cluster all the vertices into k groups
What is decision problem, also explain with examples? repeated

Fibonacci sequence 2mark repeated)

Clique cover problem 2mark repeated)

Make Adjacency list from the given table 3marks repeated)

Communication design problem (MST). repeated)

Strong connected component problem? repeated)

Heapify proof..... 5marks repeated)

Dijkstra Algorithmn
Define Floyd Marshall 5marks repeated)

Floyd Marshall 3marks repeated)

runtime
space used
DFS algoritmn 3marks repeated)

(1) give a detailed example of 2-d maxima ? repeated)

(2) what is common problem in communication networks and circuit designing? 2 repeated)
(3) write psuedo code of relaxing a vertex 5 repeated)
(4) write psuedo code of dijkstra algorithm? 5 repeated)
(5) define NP completeness 5 repeated)
(6) define floyed warshall algorithm in these two cases 5 repeated)

do not go through a vertex k at all

do go through a vertex k
(7) Define DAG 3 repeated)

10 marks: What is generic approach for computing MST? repeated)

10 marks: write the pseudo code algorithm for implementing knapsack using stack?
5 marks: you are given a task of laying railway tracks in Pakistan. You want that there should be
minimum distance between any two cities. Which algorithm would you apply for this. 4 options
were given Prim, Floyd-Warshall, Bellman-Ford and Dijkstra?

Ans: I will chose Floyd-Warshall and I also gave solid arguments for this.
3 marks: What is the running time of Floyd-Warshall algorithm? repeated)

1 mark: When we have objects in such a way that there is some interconnection or relationship
among objects then what is the best way to model such situations.
Ans:GRAPHS is the best way to model the problem.
What is DFS?

Ans Another traversal strategy is depth-first search (DFS). The strategy followed by depth-first search is,
as its name implies, to search“deeper” in the graph whenever possible. Depth-first search explores edges
out of the most recently discovered vertexthat still has unexplored edges leaving it. Once all ofv’s edges
have been explored, the search “backtracks” to explore edges leaving the vertex from which vwas
discovered. DFS procedure can be written recursively or non-recursively. Both versions are passed s
initially.
Q.When is a graph strongly connected graph?

Ans: A digraph is strongly connected if for every pair of vertices u, v ∈ V , u can reach v and vice versa
5 marks: Prove the following lemma
Given a digraph G = (V, E), consider any DFS forest of G and consider any edge (u, v) 2 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].

ans: 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.

3 variants of shortest path algorithm?.....3(repeated)

Matrix was given ...we have to tell the general property of having loop.....3
Apply dijkstra algorithm on given graph......5(repeated)
Q: how topological sort work??............5

ans: A topological sort of a DAG is a linear ordering of the vertices of the DAG such that for each edge
(u, v),u appears before v in the ordering .Computing a topological ordering is actually quite easy, given a
DFS of the DAG. For every edge (u, v)in a DAG, the finish time of u is greater than the finish time of v
(by the lemma). Thus, it suffices to output the vertices in the reverse order of finish times.
Q:Pseudo code of topological sort........10

ans

TOPOLOGICALSORT(G)

1 for (each u ∈ V )

2 do color[u] ← white

3 L ← new Linked List()

4 for each u ∈ V

5 do if (color[u] = white)
6 then TOPVISIT(u)

7 return L

you are given a task of laying railway tracks in Pakistan. You want that there should be minimum
distance between any two cities. Which algorithm would you apply for this. 4 options were given
Prim, Floyd-Warshall, Bellman-Ford and Dijkstraa? (repeated)
Ans: I will chose Floyd-Warshall
Q:define unweighted graph?

ans: An un-weighted graph can be considered as a graph in which every edge has weight one unit.
what is common problem in network n circuit design?.....2(repeated)
Forward edge ??.

Ans: 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
formula to compute encodings tree T.......1
(1)Is adjacency matrix faster than list to find the cost of an edge? Why and why not?
) Adjacency Matrix is better to locate edges as compared to list ; as matrix has direct entries for edges.
Here you can think more about these data structures space wise "lists " will be preferable to store the
graph information as matrix takes O(n^2) space while in Sparse graph means having less edges in it   the
lists will take less storage. It all depends upon the application for which you want to use the particular
data structure

(2)As we know that huffman coding algorithm is a greedy approach. What is the theta notation for
this algorithm? Is it polynomial time algorithm or exponential? Please explain

Yes it is polynomial time algorithm and it has time complexity up to O(n^2)..

(3)In directed graphs, what may be the maximum number of vertices?Any relation for this?Please
explain it?

There may be as many vertices as possible for directed graph . You have not specified for which you
want to ask relationship; however if it means the in degree and out degree of edges then the sum of all
in degrees or out degrees will be equal to no of edges present in the graph ;here in degree means the no
of edges coming to that particular vertex and out degree means the no of edges going out that
particular vertex.   IF YOU HAVE ASKED OTHER RELATION i.e. no edges and no vertices then this is not
predictable as there may be random no of edges may go OUT and IN to the vertex.

4
( )Breadth first search is shortest path algorithm that works on un-weighted graphs. Is depth first

shortest path algorithm that works on un-weighted graphs ?

Depth First Search also works for un-weighted AND WEIGHTED graphs as well
REMEMBER ME IN UR PRAYS: