# 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 Current Final Term Papers Spring 2012 Date: 16-July-2012 to 27-July-2012

Current Final Term Papers Spring 2012 Date: 16-July-2012 to 27-July-2012

Current Final Term Papers Spring 2012 Papers, July 2012, Solved Final Term Papers, Solved Papers, Solved Past Papers, Solved MCQs

Views: 3273

### Replies to This Discussion

a-o-a frnds...i hav done my cs502 exam.........there were total of 52 questions..........n evrything was frm past papers.......even a single mcq.............so guys.....plz read all past paperz once......n Good luck....Allah Hafiz.

M.Tariq Malik Plz Jis past paper wali file sy ap ny Prepration ki hy wo yahn share kr do

Final Term Paper 2012

CS502 Fundamentals of Algorithms

Attempt by Umair Saulat

Dated 16 July 2012 time 2.30 Pm

North Nazimabad Campus, Karachi

40 MCQs…. 20 MCQs were from past paper                                      Time 2Hours

12 Questions

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?

http://vustudents.ning.com/

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 questions

CS502_Final_Term_Paper_Spring_2012

Attachments:

Final Term Paper 2012

CS502 Fundamentals of Algorithms

Attempt by Umair Saulat

Dated 16 July 2012 time 2.30 Pm

North Nazimabad Campus, Karachi

40 MCQs…. 20 MCQs were from past paper                                     Time 2Hours

12 Questions

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)

I  forget other questions

Attachments:

My CS502 paper

Attachments:

Cs502 Fundamentals of Algorithm spring 2012 final

Subjective

1. Suppose we are able to prove that an NP-complete problem cannot be solved in less than exponential number of steps, what would be consequence? (2)

1. Differentiate between back edge and forward edge? (2)

1. i) How Dijkstra’s algorithm operates?            (2)

ii) What is the running time for Dijkstra’s algorithm?

1. What is difference between O (n log n) and theta (n log n)? (2)

1. Let the adjacency list representation of an undirected graph is given below. Explain what general property of the list indicates that the graph has a loop. (3)

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

6. Consider the following two problems. In P1 we are given as input a set of n squares (specified by their corner points), and a number k. The problem is to determine whether there is any point in the plane that is covered by k or more squares.

In P2 we are given as input an n–vertex graph, and a number k; the problem is to determine whether there is a set of k mutually adjacent vertices. (E.g. for k = 3 we are just looking for a triangle in the graph.).

Obviously, the problems are both in NP. There exists a simple translation from P1 to P2: just make a graph vertex for each square, and add an edge between a pair of vertices if the corresponding two squares overlap.

If P1 is NP-complete, would this translation imply that P2 is NP-complete?

(Give your Answer in Yes or No) (3)

7. 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 order is the execution of this code? (3)

8. How Dijkstra’s algorithm works? (3)

9. Explain the topological sort?  (5)

10. You are given the task of laying down new railway lines which will connect all n cities.

Thus for any pair of cities, you will end up with track connecting them. Note that two routes may share the same track; track lay between Lahore and Islamabad can be used to travel in both directions. Your goal is to use the minimum amount of track. How would you achieve the goal now? (Note: consider the scenario carefully and name only the best suited algorithm)

1.  Prims algorithm
2.  Dijkstra's algorithm
3. 3.      Floyd Warshall algorithm
4.  Bellman Ford algorithm.

11. Arrange the following functions such that which are time wise efficient appear first and so on. Where “n” is a binary number and where ever “log” is used it has base “2”.

O (log n √n); O (n/n); O (n/log n); O (n/√n); O (√n. √n)      (5)

aik question yad nhe

Dua Zahra  gud keep it up & keep sharing 1) In storage components problem what complete refers to?

2) How shortest path information is propagated in graph using Bell-Ford algorithm?

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 KrasKal” salgorithm

a) Create set(u)

b) Find set(u)

c) Union (u, v)

5) Write the general property of the matrix indicate that the graph is complete?

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 ?

Difference b/w back ward and forward 2 marks

Polynomial time algorithm 2 marks

Describe Minimum Spanning Trees Problem with examples. 2 marks

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 that fib memorization ka. 3 marks

Ak diagram given the us ma prims algorithm batna tha. 5 mark

Ak matrix given the us ka floyed warshal step batna tha. 5 marks

DFS ka itterative step batna tha 5 marks

A-o-a Dear Students,

I hope u all are fine. Today i have given my cs502 paper u can say 80 paper even subjective was full from the past papers and majority MCQ's. I would request u all to kindly study past papers for best results.I am sharing my paper here attached via.

Remember me in ur prayers!

Best of Luck!

Attachments:

Thanks for sharing........May Allah Bless You