CS502 Current Final Term Paper Fall 2012
SOLVED with references
On 23 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: 1 Define common problem in communication networks.(2)
Answer:
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
Q:2 Why we need reductions? Give Example. (5)
EXAMPLE:
Q: 3 Make adjacency list of given graph. (5)
Answer:
Q: 4 Kruskal algorithms can return different spanning tree. Prove
Answer:
Question was so unclear.
Please read out kruskal algorithm topic at pg 147.
Q:5 How to get Knapsack optimal solution with dynamic programming algorithm table ? (5)
Answer:
PAGE NO 96
Q:6 Define the following in Kruskal algorithm
Create Set-u
Find Set-u
Union(u,v)
Answer:
Q:7 In divide-conquer strategy which step have main processing?
Answer: Page no 27
I think the step conquer has main processing.
Q:8 Q No.7 Explain the following two basic cases according to Floyd-War shall Algorithm?
Answer:
GO through K
The length of shortest is d(k-1)ij
Don't go through k
The length is d (k-1)ik+d(k-1)kj
Q:9:
Chain matrix multiplication? (2)
Answer: Page no 84
Q: 10 How we can convert a weighted edges graph into unweighted edges graph. A adjacency matrix was given with weights as entries.
Answer:
As adjacency matrix was given so i made a digraph by using weights as number of edges. It will result in graph that doesn't have weights but number of edges.
This figure is really important two long questions were from Adjacency matrix and list.
Q:11 How to propagate shortest path in Bell men Ford theorem?
Answer: 
Page no : 160
Q:12 Lemma was question Page no :150 
Today Final Term Paper Fall 2012
On 21 Feb 2013
Q No.1 Suppose you could prove that an NP-complete problem can not be
solved in polynomial time. What would be the consequence?
Answer:
If we can prove that any NP-complete problem cannot be solved in polynomial time, the every NP-complete problem cannot be solvable in polynomial time.
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
Answer:
A graph is connected if every vertex can reach every other vertex. And is isolated if any node has not connected to other vertex, here's "g" is the node that is not connected with any other vertex. This general property of the list indicates that the graph has an isolated vertex.
Q No.3: What are two cases for computing?
Answer:
There are two cases for computing Lij the match case if ai = bj , and the mismatch case if ai 6= bj . In the match case, we do the following:
and in the mismatch case, we do the following:
Q no.4:Describe Dijkstra's algorithm working?
Answer:
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
Answer:
The same question was mine.
As adjacency matrix was given so i made a digraph by using weights as number of edges. It will result in graph that doesn't have weights but number of edges.
This figure is really important two long questions were from Adjacency matrix and list.
Q No.5 In the solution of edit distance technique, please describe two solution
given
(i) MATHS (ii) ARTS
Answer: Page no 79
Q No.6 Variants of shortest path solution briefly?
Answer: Page no : 154
Q No.7 Explain the following two basic cases according to Floyd-Warshall
Algorithm,
Answer:
GO through K
The length of shortest is d(k-1)ij
Don't go through k
The length is d (k-1)ik+d(k-1)kj
Q No.8 Explain the topological sort?
Answer: Page no 133
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)
Answer: Page no:18
YES
Regards
Ghazala Jabbar
MBA (HR)
-
You received this message because you are subscribed to the Google Groups "Pak Youth" group.
To post to this group, send email to pak-youth@googlegroups.com.
To unsubscribe from this group, send email to pak-youth+unsubscribe@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/pak-youth?hl=en.
---
You received this message because you are subscribed to the Google Groups "Pak Youth" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pak-youth+unsubscribe@googlegroups.com.
To post to this group, send email to pak-youth@googlegroups.com.
Visit this group at http://groups.google.com/group/pak-youth?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
No comments:
Post a Comment