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
2nd woh jiss ko tum ney har dukh me pukaara hoo (Mother)
--
For study materials, past papers and assignments,
Join VU School at www.vuscool.com
Facebook Group link
http://www.facebook.com/groups/vuCoooL
CoooL Virtual University Students Google Group.
To post to this group, send email to coool_vu_students@googlegroups.com
home page
http://groups.google.com/group/coool_vu_students?hl=en
No comments:
Post a Comment