Unit-V
1) _________ is the class
of decision problems that can be solved by non-deterministic polynomial
algorithms?
A. NP
B.
P
C.
Hard
D.
Complete
2. Problems that cannot
be solved by any algorithm are called____
A.
Tractable problems
B.
Intractable problems
C. Undecidable problems
D.
Decidable problems
3.: I: If a polynomial time algorithm exists for any of these problems, all problems in NP would be polynomial time solvable.
II: A problem is NP-hard if all problems in NP are
polynomial time reducible to it, even though it may not be in NP itself.
A.
Only I is correct
B.
Only II is correct
C. Both are correct
D.
Both are not correct
4.How many stages of
procedure does a non-deterministic algorithm consist of?
A.
1
B. 2
C.
3
D.
4
5. Code generation
problem is
A.
P-Class
B.
NP- Class
C.
NP-Complete
D. NP-Hard
6.
I: Sorting networks are comparison networks that always sort their inputs.
II: A comparison network
is comprised solely of wires and comparators.
A.
Only I is correct
B.
Only II is correct
C. Both are correct
D.
Both are not correct
7. The goal of an
approximation algorithm is
A.
Find boolean value
B.
Find minimum value
C.
Find maximum value
D. Find closest value
8. To which of the
following class does a CNF-satisfiability problem belong?
A.
NP class
B.
P class
C. NP complete
D.
NP hard
9. The choice of
polynomial class has led to the development of an extensive theory called
________
A. computational complexity
B.
time complexity
C.
problem complexity
D.
decision complexity
10. I: A bitonic sorter,
which is a network that sorts binary sequences.II: A bitonic sorter is
comprised of several stages, each of which is called a full-cleaner.
A.
Only I is correct
B.
Only II is correct
C.
Both are correct
D. Both are not correct
11. : A bitonic sorter is
comprised of several stages, each of which is called a half-cleaner.II: Each
half-cleaner is a comparison network of depth 1 in which input line i is
compared with line i + n/2 for i = 1, 2, . . . . n/2.
A.
Only I is correct
B.
Only II is correct
C. Both are correct
D.
Both are not correct
12. I: If P ≠ NP, there
are problems in NP that are neither in P nor in NP-Complete.II: All problems in
P can be solved with non-polynomial time algorithms.
A. Only I is correct
B.
Only II is correct
C.
Both are correct
D.
Both are not correct
13. The goal of an
approximation algorithm is
A.
Find Boolean value
B.
Find minimum value
C.
Find maximum value
D. Find closest value
14. To which of the
following class does a CNF-satisfiability problem belong?
A.
NP class
B.
P class
C. NP complete
D.
NP hard
15.Statement I : Merging
Network is the network that can join two sorted input sequences into one sorted
output sequence. Statement II : The sorting network need the merging network to
implement a parallel version of merge sort.
A.
Only I is correct
B.
Only II is correct
C. Both are correct
D.
Both are not correct
16. Which of the
following is true for uses of comparators?
A.
Can’t be used in mass production
B.
Not suitable for inspection purposes
C. the element of list
are compared
D.
Slow rate of working
17. The number of
comparators required for sorting n inputs is called the………. of the network.
A.
Height
B. Size
C.
N size
D.
Depth
18. Size of sorting
network calculated by ...
A. [n(n-1)]/2
B.n+n/2
C.
n/2+1
D.
None of above
19.The algorithm required
by a single processor to solve the entire problem is called ……………
A.
Parallel algorithm
B. Sequential algorithm
C.
Top to Bottom algorithm
D.
Bottom up algorithm
20. The algorithm
required by a multiple processor to solve sub problem is called ……………
A. Parallel algorithm
B.
Sequential algorithm
C.
Top to Bottom algorithm
D.
Bottom up algorithm
21. Sequential model of
parallel computing use ….
A. Single Processor
B.
Sequence of Processor
C.
Multiple Processors
D.
No Processor
22. Parallel model of
parallel computing use ….
A.
Single Processor
B.
Sequence of Processor
C. Multiple Processors
D.
No Processor
23. The odd even merge is
merging algorithm based on …..
A. Divide and conquer
B.
Backtracking
D.
Branch and bounding
C.
Dynamics Programming
24. If …… problem can be
solved in polynomial time then all the NP complete problem can be solved in
polynomial time.
A. NP Hard
B.
NP
C.
NP Complete
D.
P
25. All the ………. Problems
are NP hard.
A
) NP
B. NP Complete
C.
P
D.
None of above
26. The algorithm in
which every operation may not have unique result is called……….
A.
Deterministic Algorithm
B. Non- Deterministic
Algorithm
C.
Parallel Algorithm
D.
sequential algorithm
27. Decision Problems
are….
A.
NP
Hard
B.
NP
C.
NP Complete
D.
P
28. Optimization Problems
are….
A.
NP Hard
B.
NP
C.
NP
Complete
D.
P
29. CNF-SAT is based on
……..
A.
Boolean Formulas
B.
Arithmetic
Formulas
C.
Geometrical
Formulas
D.
None
of Above
30. How many liberals in
3SAT?
1
2
3
4
No comments:
Post a Comment