Ticker

6/recent/ticker-posts

CSE408 Design & Analysis Of Algorithms Practice MCQs, CA 02

 CSE408 Practice MCQs. 

DESIGN & ANALYSIS OF ALGORITHMS Practice MCQs 32 Questions.

1. What is the complexity of quick sort in average case?      

a) n^2

b) nlogn

c)logn

d)(n^2)(logn)

2. What is the complexity of Merge sort in worst case? 

a) n^2

b) nlogn

c)logn

d)(n^2)(logn)

3. Find the value of C[i] after commulative addition at the 5th index.The elements are 7,2,4,7,2,9,10,7,8,9,2,3,4                                       

a)9

b)10

c)12

d)13

4. In Bucket sort , range of randomised input is:-

a)[0,1]

b) [0,1)

c) (0,1)

d)(0,1]

5. The Binary search finds the elements in the time complexity of:-                

a)nlogn

b)logn

c)n

d)n^2

6. The complexity of Heap sort is ‘x’ and Maxheap help to sort the element in ‘y’ order while Minheap help to sort the elements in ‘z’ order:-         

a)logn ,Decending,Ascending

b)log n ,Ascending, Descending

c)nlogn ,Decending ,Ascending

d)nlogn , Ascending,Decending 

7. Solve the recurrence equation T(n)=27T(n/3) + n^2    to find the complexity.                         

a) (n^2)logn

b) n^2

c) nlogn

d) None of these

8. In the recurrence equation of T(n)=27T(n/3)+n,the value of É› and k is   

a) É› =1 and k=not required

b) É› =2 and k=not required

c) É› =1 and k=0

d) É› =not required and k=0

9. Find the complexity of the recurrence equation T(n)=2T(n+5)+logn by Master method.

a) n

b) logn

c) nlogn

d)Can't apply method

10. Find the value of epsilon for T(n)=4T(n/2)+n^100.                   

a)100

b)Not required in this case

c)98

d)99

11. Find the complexity in the recurrence tree whose recurrence equation is given as

T(n)=2T(n/2)+n^2.                                                                                          

a)     n^2

b)    logn

c)    n

d)    None of these

12. The Complexity of Radix sort and selection sort is      

a)n ,n^2

b)n^2,n

c)nlogn, n^2

d)n^2 ,logn

13. What is the value of n if x is 213444 and y is 23613 in multiplication of Large Integer. 

a)3

b)6                                                                               

c)5

d)None of these

14. In Strassen’s Matrix multiplication,the total no of additions and multiplication takes place are:-

a)18 and 7

b)18 and 8

c)17 and 7

d)17 and 8

15. What is the value of n and (n/2) if x=9621964636 and y=20173927 in multiplication of Large Integer. 

a)10 and 5

b)8 and 4                                                                                                         

c)9 and 4

d)None of these

16. Apply Quick sort Algorithm on the following elements  2,8,7,1,3,5,6,4  to find the value of i at j=6.                                           

a)-1

b)1

c)2

d)3

17. In strassens’s Matrix multiplication,If A00=1, A10=8, A01=2, A11=4, B00=3, B10=9, B01=8, B11=7;then to compute C00,there is a requirement of:-

a) M1   + M3  - M2 + M6

b) M1   + M4  - M5 + M7                       

c) M1   - M4  + M5 - M7                       

d) M1   - M3  + M2 - M6

18. Find the complexity of T(n) = 0.5T(n/2) + 1/n using Master method.      

a)n

b)1

c)n^2

d)Does not apply.

19. Find the complexity of T(n) = 7T(n/3) + n^2 using Master method.    

 a)n

b)1

c)n^2

d)Does not apply.

20. Find the complexity of T(n) = 16T (n/4) + n!            

a)n

b)n!

c)n^2

d)Does not apply.

21. Find the complexity of T(n)=3T(n/3)+sqrt(n).                     

a) n

b)Sqrt(n)

c)n^2

d)None of these

22. Apply Quick sort Algorithm on the following elements  2,8,7,1,3,5,6,4  to find the value of A[i] at j=6.                                            

a)6

b) 8

c) 3

d) 7

23. Apply Quick sort Algorithm on the following elements  2,8,7,1,3,5,6,4  to find the value of A[i] at j=6.                                            

a)3

b)7

c)8

d)2

24. Apply Quick sort Algorithm on the following elements  2,8,7,1,3,5,6,4  to find the value of A[i] at j=6.                                            

a)8

b)7

c)2

d)3

25. Apply Quick sort Algorithm on the following elements  2,8,7,1,3,5,6,4  to find the value of A[q] at j=7.                                            

a)4

b)6

c)2

d)3

26. Find the sum of B[i]+B[i+3] after commulative addition at the 4th index in count sort.The elements are 7,2,4,7,2,9,10,7,8,9,2,3,4                                       

a)19

b)20

c)22

d)23

27. Time Complexity of Breadth First Search is? (V – number of vertices, E – number of edges)

a) O(V + E)
b) O(V)
c) O(E)
d) O(V*E)

28. A person wants to visit some places. He starts from a vertex and then wants to visit every place connected to this vertex and so on. What algorithm he should use?

a) Depth First Search
b) Breadth First Search
c) Trim’s algorithm
d) Kruskal’s algorithm

29. A person wants to visit some places. He starts from a vertex and then wants to visit every vertex till it finishes from one vertex, backtracks and then explore other vertex from same vertex. What algorithm he should use?

a) Depth First Search
b) Breadth First Search
c) Trim’s algorithm
d) Kruskal’s Algorithm

30. What are the worst case and average case complexities of a binary search tree?

a) O(n), O(n)
b) O(logn), O(logn)
c) O(logn), O(n)
d) O(n), O(logn)

31. What is the running time of Strassen’s algorithm for matrix multiplication?

a) O(n2.81)
b) O(n3)
c) O(n1.8)
d) O(n2)

32. What is the running time of naïve matrix multiplication algorithm?

a) O(n2.81)
b) O(n4)
c) O(n)
d) O(n3)




Post a Comment

0 Comments