Question 21 : _________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms?
1. NP
2. P
3. Hard
4. Complete
View Answer   Discuss with Members

Question 22 : What is the rate of the hamming code of parity bit m=8?
1. 0.94
2. 0.92
3. 0.90
4. 0.97
View Answer   Discuss with Members

Question 23 : What is the message length 'k' of a Hamming(7,4) code?
1. 2^r-1
2. 2^r-r+1
3. 2^r-r-1
4. 2^r+1-r
View Answer   Discuss with Members

Question 24 : Hamiltonian path problem is _________
1. NP problem
2. N class problem
3. P class problem
4. NP complete problem
View Answer   Discuss with Members

Question 25 : Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently?
1. branch and bound
2. iterative improvement
3. divide and conquer
4. greedy algorithm
View Answer   Discuss with Members

Question 26 : Who formulated the first ever algorithm for solving the Hamiltonian path problem?
1. Martello
2. Monte Carlo
3. Leonard
4. Bellman
View Answer   Discuss with Members

Question 27 : How many conditions have to be met if an NP- complete problem is polynomially reducible?
1. 1
2. 2
3. 3
4. 4
View Answer   Discuss with Members

Question 28 : The problem of finding a path in a graph that visits every vertex exactly once is called?
1. Hamiltonian path problem
2. Hamiltonian cycle problem
3. Subset sum problem
4. Turnpike reconstruction problem
View Answer   Discuss with Members

Question 29 : What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)?
1. O(N!)
2. O(N! * N)
3. O(log N)
4. O(N)
View Answer   Discuss with Members

Question 30 : Which of the following problems is not NP complete?
1. Hamiltonian circuit
2. Bin packing
3. Partition problem
4. Halting problem
View Answer   Discuss with Members