Design and Analysis of Algorithm MCQ Unit-V

 

 

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

 

Design and Analysis of Algorithm MCQ Unit-II

 

Unit- II

 

Q.1 Indicator random Variables provide a convenient method for Converting

[A]Probabilities

[B]Expectation

[C]Both [A] and [B]

[D] None of these

 

Q.2  ........is the use of probability in the analysis of problems.

[A]Probabilistic analysis

[B]Worst case analysis

[C]Best case Analysis

[D]None of these

 

Q.3 What is the best case complexity of binary search in successful search?

[A] θ(n log n)

[B] (θlog n)

[C] θ(1)

[D] θ(n)

 

Q.4  What will be the worst case time complexity of merge sort?

[A] O(n log n)

[B] O(n²)

[C] O(n² log n)

[D] O(n log n²)

 

Q.5 Which of the following method is used for sorting in quick sort?

[A] merging

[B] partitioning

[C] selection

[D] exchanging

 

Q.6 What is time complexity for best case of Quick Sort?

[A] O(n log n)

[B] O(n²)

[C] O(n² log n)

[D] O(n log n²)

 

Q.7 The running time depend on

[A] partition is balanced or unbalance

[ B] input array

[C] pivot element position

[D] None of these

 

Q.8  An algorithm .......if its behaviour is determined not only by its input but also by values produced by random number generator.

[A]Sequential

[B]Randomized

[C]Parallel

[D]None of these

 

Q.9 The algorithm from which the input is random by referring to the running time of a ....................as an expected running time.

[A]Randomized algorithm

[B] Merge sort

[C]Bubble sort

[D] None of these

 

Q.10 What is the worst case time complexity of a quick sort algorithm?

 

[A] O(n)

[B] O(n log n)

[C] O(n²)

[D] O(log n)

 

Q.11 Which of the following sorting algorithms is the fastest?

[A] Merge sort

[B] Quick sort

[C] Insertion sort

[D] Shell sort

 

Q.12 Identify problem in which All permutations of the input are equally likely, a probabilistic analysis?

[A] TSP problem

[B]Hiring problem

[C] Greedy problem

[D] None of these

 

Q.13 Merge sort uses which of the following technique to implement sorting?

[A] backtracking

[B] greedy algorithm

[C] divide and conquer

[D] dynamic programming

 

Q.14 What is the advantage of recursive approach than an iterative approach?

[A] Consumes less memory

[B] Less code and easy to implement

[C] Consumes more memory

[D] More code has to be written

 

Q.15 Which of the following is not an application of binary search?

 [A] To find the lower/upper bound in an ordered sequence

[B] Union of intervals

[C] Debugging

[D] To search in unordered list

 

Q.16 Find the pivot element from the given input using median-of-three partitioning method. 8, 1, 4, 9, 6, 3, 5, 2, 7, 0.

 [A] 8

[B] 7

[C] 9

[D] 6

 

Q.17 A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits.

[A] worst case

[B] best case

[C] average case

[D] none of the mentioned

 

Q.18 ................... is the use of probability in the analysis of problems.

[A] Probabilistic analysis

[B]Linear Analysis

[C]Quadratic Analysis

[D] None of these

 

Q.19 In Hiring Algorithm if candidate i is better than candidate best

 

[A] best=0

[B]best=i

[C] best=1

[D] None of these

 

Q.20  Worst case analysis of Hiring Algorithm is

[A] O(Ch_m)

[B] O(Ci_n+Ch_m)

[C] O(Ci_N)

[D] None of these

 

Q.21  Each of the possible n! permutations appears with equal probability then it is

[A] uniform random permutation

[B] random permutation

[C] uniform permutation

 [D] permutation

 

Q.22 Which algorithm provide a convenient method for converting between probabilities and expectations?

[A] Quick sort

[B] Indicator random variables

[C] Bubble sort

[D] None of these

 

Q.23 What is a randomized QuickSort?

 [A] The leftmost element is chosen as the pivot

[B] The rightmost element is chosen as the pivot

[C] Any element in the array is chosen as the pivot

[D] A random number is generated which is used as the pivot

 

Q.24 Choose the incorrect statement about merge sort from the following?

[A] it is a comparison based sort

[B] it is an adaptive algorithm

[C] it is not an in place algorithm

[D] it is stable algorithm

 

Q.25 Indicator random variable denoted by

[A] I{A}

[B] R{s}

[C] V{a}

[D] None of these

 

Q.26  What is the time complexity of uniform binary search?

[A] O(nlogn)

[B] O(logn)

[C] O(n)

[D] O(n²)

 

Q.27 In which of the cases uniform binary search fails compared to binary search?

 [A] A table lookup is generally faster than an addition and a shift

[B] Many searches will be performed on the same array

[C] Many searches will be performed on several arrays of the same length

[D] Complexity of code

 

Q.28 Which of the following stable sorting algorithm takes the least time when applied to an almost sorted array?

[A] Quick sort

[B] Insertion sort

[C] Selection sort

 [D] Merge sort

 

Q.29 Which of the following is not in place sorting algorithm by default?

[A] merge sort

[B] quick sort

[C] heap sort

[D] insertion sort

 

Q.30 Choose the correct statement about bottom up merge sort from the following?

 [A] bottom up merge sort has greater time complexity than standard merge sort

[B] bottom up merge sort has lesser time complexity than standard merge sort

[C] bottom up merge sort saves auxiliary space required on call stack

 [D] bottom up merge sort uses recursion.