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
gAnswer:
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:18YES
--
Join us at facebook: https://www.facebook.com/VU.Study.Corner
Group Link: http://groups.google.com/group/VU-Study-Corner?hl=en
Group Rules: http://groups.google.com/group/VU-Study-Corner/web/group-rules
Unsubscribe: VU-Study-Corner+unsubscribe@googlegroups.com
Adult contents, Spamming, Immoral & Rudish talk, Cell number, Websites & Groups links specially in paper days are strictly prohibited and banned in group.
---
You received this message because you are subscribed to the Google Groups "VU Study Corner" group.
To unsubscribe from this group and stop receiving emails from it, send an email to VU-Study-Corner+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
No comments:
Post a Comment