Today's Final paper of cs502

[maz01]

Dear Fellows this is my paper of cs502 16july,2011. prepare it and pray for my further success.

[Xpert]

Thank you so much for sharing this paper..... please other students also share your paper


Question No: 1 ( Marks: 1 ) - Please choose one
] If a problem is in NP-complete, it must also be in NP.
► True
► False

Question No: 2 ( Marks: 1 ) - Please choose one
The Huffman algorithm finds a optimal solution.

► True

► False

Question No: 3 ( Marks: 1 ) - Please choose one
The Huffman algorithm finds an exponential solution
► True
► False

Question No: 4 ( Marks: 1 ) - Please choose one
The Huffman algorithm finds a polynomial solution
► True
►False
Question No: 5 ( Marks: 1 ) - Please choose one
The greedy part of the Huffman encoding algorithm is to first find two nodes with smallest frequency.
► True
►False

Question No: 6 ( Marks: 1 ) - Please choose one
The codeword assigned to characters by the Huffman algorithm have the property that no codeword is the prefix of any other.
► True
► False

Question No: 7 ( Marks: 1 ) - Please choose one
Huffman algorithm uses a greedy approach to generate a postfix code T that minimizes the expected length B (T) of the encoded string.
► True
► False
Question No: 8 ( Marks: 1 ) - Please choose one
Dijkestra’s single source shortest path algorithm works if all edges weights are non-negative and there are negative cost cycles.
► True
► False
Question No: 9 ( Marks: 1 ) - Please choose one
The term “coloring” came form the original application which was in architectural design.
► True
► False
Question No: 10 ( Marks: 1 ) - Please choose one
In the clique cover problem, for two vertices to be in the same group, they must be adjacent to each other.
► True
►False

Question No: 11 ( Marks: 1 ) - Please choose one
Dijkstra’s algorithm is operates by maintaining a subset of vertices
► True
►False
Question No: 12 ( Marks: 1 ) - Please choose one
We do sorting to,
► keep elements in random positions
► keep the algorithm run in linear order
► keep the algorithm run in (log n) order
► keep elements in increasing or decreasing order

Question No: 13 ( Marks: 1 ) - Please choose one
After partitioning array in Quick sort, pivot is placed in a position such that
► Values smaller than pivot are on left and larger than pivot are on right
► Values larger than pivot are on left and smaller than pivot are on right
► Pivot is the first element of array
► Pivot is the last element of array

Question No: 14 ( Marks: 1 ) - Please choose one
Merge sort is stable sort, but not an in-place algorithm
► True
►False

Question No: 15 ( Marks: 1 ) - Please choose one
A p × q matrix A can be multiplied with a q × r matrix B. The result will be a p × r matrix C. There are (p . r) total entries in C and each takes _________ to compute.
► O (q)
► O (1)
► O (n2)
► O (n3)

Question No: 16 ( Marks: 1 ) - Please choose one
One of the clever aspects of heaps is that they can be stored in arrays without using any
_______________.


Pointers
constants
variables

functions

Question No: 17 ( Marks: 1 ) - Please choose one
Merge sort requires extra array storage,


True
False


Question No: 18 ( Marks: 1 ) - Please choose one
The Huffman codes provide a method of encoding data inefficiently when coded using
ASCII standard.


True
Falase

Question No: 19 ( Marks: 1 ) - Please choose one
Using ASCII standard the string abacdaacac will be encoded with __________ bits.


80
160
320
100



Question No: 20 ( Marks: 1 ) - Please choose one
Using ASCII standard the string abacdaacac will be encoded with 160 bits.


True
False

Question No: 21 ( Marks: 1 ) - Please choose one
Using ASCII standard the string abacdaacac will be encoded with 10 bytes.


True
False

Question No: 22 ( Marks: 1 ) - Please choose one
The greedy part of the Huffman encoding algorithm is to first find two nodes with
character frequency


True
False

Question No: 23 ( Marks: 1 ) - Please choose one
Huffman algorithm uses a greedy approach to generate an prefix code T that minimizes
the expected length B (T) of the encoded string.


True
False



Question No: 24 ( Marks: 1 ) - Please choose one
Dijkestra s single source shortest path algorithm works if all edges weights are nonnegative and there are negative cost cycles.


True
False


Question No: 25 ( Marks: 1 ) - Please choose one

Question No: 26 ( Marks: 1 ) - Please choose one

Question No: 27 ( Marks: 2 )
explain 2-d maxima problem mathematically or algrithmically.


Question No: 28 ( Marks: 2 )
Differentiate between back edge and forward edge.


Question No: 29 ( Marks: 2 )
Question No: 30 ( Marks: 2 )
Question No: 31 ( Marks: 3 )

Question No: 32 ( Marks: 3 )



Question No: 33 ( Marks: 3 )


Question No: 34 ( Marks: 5 )
Suppose you could prove that an NP-complete problem can not be solved in polynomial time. What would be the consequence?

Question No: 48 ( Marks: 3 )
Recursive explanation of dynamic programming.

Question No: 49 ( Marks: 5 )
What is the cost of the following graph?







Cost =33

Question No: 50 ( Marks: 5 )
. 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
Question No: 51 ( Marks: 5 )
Floyd Warshal algorithm with three recursive steps

Question No: 52 ( Marks: 5 )