# www.vustudents.ning.com

We non-commercial site working hard since 2009 to facilitate learning Read More. We can't keep up without your support. Donate.

CS502 All Current Final Term Papers Fall 2012 (20 February to 03 March 2013) at one Place

From 20 February to 03 March 2013 Fall 2012

Current Final Term Papers Fall 2012 Papers, Feb 2013 Final Term Papers, Solved Final Term Papers, Solved Papers, Solved Past Papers, Solved MCQs

Please Share your Current Papers Questions/Pattern here to help each other. Thanks

Views: 4010

### Replies to This Discussion

Please Share your Current Papers Questions/Pattern here to help each other. Thanks

current paper Attachments:

Javeria Saeed thanks for sharing ur paper Note for All Members: You don’t need to go any other site for current Final Term papers fall 2012, Because All discussed data/sharing of our members in this discussion are going from here to other sites. You can judge this at other sites yourself. So don’t waste your precious time with different links.

Current paper cs502

2013

What is a common problem in communication network and circuits?

Shortest path algo

Dijkstra algo

Suedo code of  Dijkstra algo

Heapify

Polynomial time algo

Greedy algo ka maray paper main kuch nai aya

DFS algo

2-d maxima

NP completeness

DAG

Fibonacci sequence

Clique cover problem

Pseudo code of relaxing

Floyd-Warshall shortest path

Huffman encoding algo ka bhut aya tha maray paper main

Aik graph tha us main iteration ka batana tha

Main memory

Today Final Term Paper Fall 2012
On 21 Feb 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)

haaaaa aj ka paper cancel ho gya tha bhai

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
Pleas give these two questions

+ "♦♦ǥůяiά♦♦" janb ya konca paper upload ker reha ho     cs 502 Algorithm

thanks guriya    Can you tell me k past papers main se aaya tha k nae?

Mine solved paper of cs502     23 February 2013

Mostly mcqs were from Moaaz file

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.

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

psedo code of timestamp  DFS

DFS(G)

1 for (each u 2 V)

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 ?