We are here with you hands in hands to facilitate your learning & don't appreciate the idea of copying or replicating solutions. Read More>>

Looking For Something at vustudents.ning.com? Click Here to Search

www.bit.ly/vucodes

+ Link For Assignments, GDBs & Online Quizzes Solution

www.bit.ly/papersvu

+ Link For Past Papers, Solved MCQs, Short Notes & More


Dear Students! Share your Assignments / GDBs / Quizzes files as you receive in your LMS, So it can be discussed/solved timely. Add Discussion

How to Add New Discussion in Study Group ? Step By Step Guide Click Here.

Fellows please share your current final term paper.

+ How to Follow the New Added Discussions at Your Mail Address?

+ How to Join Subject Study Groups & Get Helping Material?

+ How to become Top Reputation, Angels, Intellectual, Featured Members & Moderators?

+ VU Students Reserves The Right to Delete Your Profile, If?


See Your Saved Posts Timeline

Views: 3863

.

+ http://bit.ly/vucodes (Link for Assignments, GDBs & Online Quizzes Solution)

+ http://bit.ly/papersvu (Link for Past Papers, Solved MCQs, Short Notes & More)

+ Click Here to Search (Looking For something at vustudents.ning.com?)

+ Click Here To Join (Our facebook study Group)

Replies to This Discussion

Thanks

My cs502 paper

(1)How kruskul algorithm works 3mrks

(2) Explain the following two basic cases according to Floyd-Warshall Algorithm, 3mrks

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

2. Do go through vertex k

(3)how many  basic cases according to Floyd-Warshall Algorithm,? 2mrks

(4) drive a formula to calculate a cost of encoded tree T?

(5)kruskul algoritm running time when its sparse? 3mrks

(6) a tree was given we have to find MST 5mrks

(7) a matrix is given we have to find adjacency list 5mrks

(8) why we need a reduction,give one example 5mrks

(9)

 

 

Qaiser Gill (mcs 4)  thanks for sharing..keep it up 

Attention Students: You don’t need to go any other site for current papers pattern & questions. Because all sharing data related to current Final term papers of our members 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. Just keep visiting http://vustudents.ning.com/ for all latest updates.

 

CS502 Final term current Papers from 01-03-2014 to 12-03-2014

VU Current Final Term Paper
Semester Fall 2013-2014

VU Current Final Term Paper
Semester Fall 2013
Total Questions = 52 
Total Marks = 80
Total 1 Mark MCQ = 40
Total 2 Marks Short Questions = 4
Total 3 Marks Short Questions = 4
Total 5 Marks Long Questions = 4
Is there any relationship between number of back edges and number of cycles in DFS? (2 MARKS)
ANS: There is no relationship between no. of edges and cycles (Page 131)

How do we compute assuming we already have the previous matrix? (2 MARKS)
ANS: 1. don’t go through vertex k at all.
2 .Do go through vertex k (Page 162)

Consider the case of 3 matrices: A1 is 5 × 4, A2 is 4 × 6 and A3 is 6 × 2 The multiplication can be carried out as ((A1A2)A3) The cost of is? (2 MARKS)
ANS: ((A1A2)A3) = (5 · 4 · 6) + (5 · 6 · 2)= 180 (Page 84)

4.. What the time is dominated by sorting if the graph is sparse? (2 MARKS)
ANS: Θ(E log E) = Θ(E log V ) (Page 149)

5.. Consider a digraph G = (V, E) and any DFS forest for G. G has a cycle if and only if the DFS forest has a back edge? (3 MARKS)
ANS: Proof: If there is a back edge (u, v) then v is an ancestor of u and by following tree edge from v to u, we get a cycle (Page 131)

6.. Variants of shortest path solution briefly? (3 MARKS)
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.

7.. Express the Harmonic series in summation form and also with capital theta notation? (3 MARKS)
ANS:

8.. What do you mean by polynomial time algorithm? Explain what kind of problems can be solved by using polynomial time algorithm? (3 MARKS)
ANS: A polynomial time algorithm is any algorithm that runs in time.
A problem is solvable in polynomial time if there is a polynomial time algorithm for it. (Page 131)

9.. What is the cost of the following graph? (5 MARKS)

ANS: Cost =33 (Page 142)

1:Write pseudo code for Kruskal’s algorithm.

2:Apply Prim’s algorithms on the following graph.[You can show final result in exam software and need not to show all intermediate steps].

3:Calculate the Q complexity of the following sort procedure

sort( A[1..n] )

{

for i = 2//to n do

for j = n //do onto i do

for i , j =Q

if( A[j-1] > A[j] )

swap(A[j-1], A[j])

}

4:Suppose you could reduce an NP-complete problem to a polynomial time problem in polynomial time. What would be the consequence?

5:You are given the task of laying down new railway line between Peshawar and Karachi. There are n intermediatecities that can be used and you know the cost of laying track between any pair of these cities. Your goal is to spend the least total amount of track to construct the railway line. How would you determine the least amount of track and the cities to go through? Name the best algorithm which addresses the above problem.

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

7:Consider a digraph G = (V, E) and any DFS forest for G. Prove that G has a cycle if and only if the DFS forest has a back edge.


8:Given an adjacency list for G, what is the time complexity to compute GT.?

9:Suppose you are given a large data to sort and your primary memory is short. Which sorting technique will help you to solve this problem efficiently?

10:Answer yes or no and give a brief explanation for your choice.

If problem A reduces (is polynomial-time reducible) to problem B and B is NP-complete then A is NP-complete.

11:

How Dijkstra’s algorithm operates?
What is the running time of the Dijkstra’s algorithm?

Uzma Kanwal CS502 paper 6-03-14 Thursday 8:00 –10:00

40 MCQS

Mcqs 8 almost last chap may say thay 5 to chap he k thay or baki yey pocha tha k np hay to np complete hay ya nai ,p hay to NP hay ya nai asay fazaool say thay jin ki smaj he nai ari the

Huffman say b thay stable inplace ka koi b nai tha moaz file say kam he thay handouts k thay zada tar but ez thay zada muskil nai tha
12 question  in subjective

 1-What is an edge   (2 marks)

2- Can an adjacency matrix for a directed graph ever not be square in shape? Why or why not?  (2 marks)

3-what is minimizing spanning tree of 2 and what is greedy approach in it.(2 marks)

4-Np say related koi lambiiiiiiiiii c statmwnts  the 2 or un ko yes no krna tha and xplain b karna tha  (2 marks)

5--what is MST and give ex of  (3 marks)

6-What is fractional knapsack problem?(3)

7-Np  complete say related tha kuch  (3 marks)

8-Describe equivalence relation, mutually reachable vertices and strong components? (3 marks)

9-What is topological sort (5 marks)

10-Dijisiktra Algorithm pscedo code (5 marks)

11-Analyze the following pseudo code for Huffman tree building algorithm. And write the body of second for loop with the proper logic: (5 marks)

HUFMAN (N, symbol[1…N], freq[1…N]
For i = 1 to N
Do t ß Tree Node(symbol[i], freq[i])
pq.insert(t, freq[i])
for i = 1 to N - 1
?
?
?
?
?
return pq.remove

12-Adjacency matrix di v the us ki 3 iterations karni the 5 marks

Uzma Kanwal (MCS 3rd)  thanks for sharing ur paper.. 

Attention Students: You don’t need to go any other site for current papers pattern & questions. Because all sharing data related to current Final term papers of our members 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. Just keep visiting http://vustudents.ning.com/ for all latest updates.

CS502 Final term current Papers from 01-03-2014 to 12-03-2014


VU Current Final Term Paper
Semester Fall 2013-2014

VU Current Final Term Paper
Semester Fall 2013
Total Questions = 52 
Total Marks = 80
Total 1 Mark MCQ = 40
Total 2 Marks Short Questions = 4
Total 3 Marks Short Questions = 4
Total 5 Marks Long Questions = 4
Is there any relationship between number of back edges and number of cycles in DFS? (2 MARKS)
ANS: There is no relationship between no. of edges and cycles (Page 131)

How do we compute assuming we already have the previous matrix? (2 MARKS)
ANS: 1. don’t go through vertex k at all.
2 .Do go through vertex k (Page 162)

3 Consider the case of 3 matrices: A1 is 5 × 4, A2 is 4 × 6 and A3 is 6 × 2 The multiplication can be carried out as ((A1A2)A3) The cost of is? (2 MARKS)
ANS: ((A1A2)A3) = (5 · 4 · 6) + (5 · 6 · 2)= 180 (Page 84)

4.. What the time is dominated by sorting if the graph is sparse? (2 MARKS)
ANS: Θ(E log E) = Θ(E log V ) (Page 149)

5.. Consider a digraph G = (V, E) and any DFS forest for G. G has a cycle if and only if the DFS forest has a back edge? (3 MARKS)
ANS: Proof: If there is a back edge (u, v) then v is an ancestor of u and by following tree edge from v to u, we get a cycle (Page 131)

6.. Variants of shortest path solution briefly? (3 MARKS)
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.

7.. Express the Harmonic series in summation form and also with capital theta notation? (3 MARKS)
ANS:

8.. What do you mean by polynomial time algorithm? Explain what kind of problems can be solved by using polynomial time algorithm? (3 MARKS)
ANS: A polynomial time algorithm is any algorithm that runs in time.
A problem is solvable in polynomial time if there is a polynomial time algorithm for it. (Page 131)

9.. What is the cost of the following graph? (5 MARKS)

ANS: Cost =33 (Page 142)

1:Write pseudo code for Kruskal’s algorithm.

2:Apply Prim’s algorithms on the following graph.[You can show final result in exam software and need not to show all intermediate steps].

3:Calculate the Q complexity of the following sort procedure

sort( A[1..n] )

{

for i = 2//to n do

for j = n //do onto i do

for i , j =Q

if( A[j-1] > A[j] )

swap(A[j-1], A[j])

}

4:Suppose you could reduce an NP-complete problem to a polynomial time problem in polynomial time. What would be the consequence?

5:You are given the task of laying down new railway line between Peshawar and Karachi. There are n intermediatecities that can be used and you know the cost of laying track between any pair of these cities. Your goal is to spend the least total amount of track to construct the railway line. How would you determine the least amount of track and the cities to go through? Name the best algorithm which addresses the above problem.

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

7:Consider a digraph G = (V, E) and any DFS forest for G. Prove that G has a cycle if and only if the DFS forest has a back edge.


8:Given an adjacency list for G, what is the time complexity to compute GT.?

9:Suppose you are given a large data to sort and your primary memory is short. Which sorting technique will help you to solve this problem efficiently?

10:Answer yes or no and give a brief explanation for your choice.

If problem A reduces (is polynomial-time reducible) to problem B and B is NP-complete then A is NP-complete.

11:

How Dijkstra’s algorithm operates?
What is the running time of the Dijkstra’s algorithm?

CS502 Final term current Papers from 01-03-2014 to 12-03-2014

How the generic greedy algorithm opreats in minimum spanning tree?
How Dijkstra’s algorithm operates?
what is the running time of the Dijkstra algorithm?
if problem A reduces (is polynomial –time reducible) to problem B and B is N-P complete then A is N-P complete.
Ans yes or no and briefly explain.
what is the idea behind in counting sort algorithm , to sort the elements without comparisons in linear time?
Consider a digraph G=V,E and any DFS forest for G prove that G has a cycle if and only if the DFS forest has a back edge. (3)
what is all pairs shorests paths problem also describe Floyed- warshall algoriyhm? (3)
what are the application of edit distance technique . Three names? (3)
what do u mean by polynomial time algorithm .Explain what kind of polynomial can be solved by polynomial?(3)
show the result of topological sort graph. ? graph dia hova tha. (5)
According to Dijkstra algorithm write the pseudo code to relax a vertex./(5)
why we need reduction? 2
Give an example of reduction ? 3 (5)
1) What is a common problem is communications networks and circuit design? Page no 142
2) How Kruskal’s algorithm works? Page no 147
3) This one was related to the 2 maxima related. Page no 17
4) When Floyd warshall introduced? Pages no 162
5) How to convert a shortest path in a single path?
6) What are Calatan Numbers and their formula?
7) What is create, find and union?
8) This one was related from railway track from Peshawar and Karachi?
9) A diagram was given and asked to make the graph of traverse of 1st depth order?
10) How many minimum and maximum no of elements in heap h?
11) Topic of this question was Minimum Spanning Trees. Page no 142
12) Initialized distance matrix of all pair shortest algorithm.

@Tariq bhai ...you are copy pasting same questions again and again...flooding the discussion and confusing the students...Kindly check tu kar lo keh questions repeated na hoon...

I know you are trying your best to copy-paste current question posted on other VU website to Ning website, so that ning website gets all the traffic,and VU students stay maximum time on Ning... and they click on the google adds on ning, so that you can make good money...

But kindly dont confuse the students...

RSS

© 2020   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service

.