.::VULMSIT::.eNoxel CS502 Final Term Paper

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

--
Zindagi mein 2 Logo ka buhat khayal rahkoooo

Ist woh jiss ney tumhari jeet ke Liye buhat kuch hara hoo (Father)

2nd woh jiss ko tum ney har dukh me pukaara hoo (Mother)

Regards, 

Umair Saulat

--
Virtual University of Pakistan*** IT n CS Blog
================================
http://www.geniusweb.tk
 
http://itncs.tk
 
 
You received this message because you are subscribed to the Google
Groups "vulms" group.
To post to this group, send email to vulmsit@googlegroups.com
To unsubscribe from this group, send email to
vulmsit+unsubscribe@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/vulmsit?hl=en?hl=en