Q1. If 4 is the GCD of 16 and 12, What is the GCD of 12 and 4?.
A. 12.
B. 6.
C. 4.
D. 2.
Answer= 4
Q2. Which of the following is not an application of Euclid’s algorithm?.
A. Simplification of fractions.
B. Performing divisions in modular arithmetic.
C. Solving quadratic equations.
D. Solving diophantine equations.
Answer= Solving quadratic equations
Q3. The Euclid’s algorithm runs efficiently if the remainder of two numbers is divided by the minimum of two numbers until the remainder is zero..
A. TRUE.
B. FALSE.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= TRUE
Q4. According to Gabriel lame, how many steps does Euclid’s algorithm require to solve a problem?.
A. Less than five times the number of digits.
B. More than five times the number of digits.
C. Less than two times the number of digits.
D. More than two times the number of digits.
Answer= Less than five times the number of digits
Q5. Which of the following is the correct mathematical application of Euclid’s algorithm?.
A. Determination of prime numbers.
B. Lagrange’s four square theorem.
C. Cauchy-Euler theorem.
D. Residue theorem.
Answer= Lagrange’s four square theorem
Q6. If GCD of two numbers is 1, then the two numbers are said to be ________.
A. Co-prime numbers.
B. Prime numbers.
C. Composite numbers.
D. Rational numbers.
Answer= Co-prime numbers
Q7. What is the total running time of Euclid’s algorithm?.
A. O(N).
B. O(N log M).
C. O(N log N).
D. O(log N +1).
Answer= O(N)
Q8. Euclidean algorithm does not require the calculation of prime factors..
A. TRUE.
B. FALSE.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= TRUE
Q9. What is the formula for Euclidean algorithm?.
A. GCD (m,n) = GCD (n, m mod n).
B. LCM(m,n)=LCM(n, m mod n).
C. GCD(m,n,o,p) = GCD (m, m mod n, o, p mod o).
D. LCM (m,n,o,p) = LCM (m, m mod n, o, p mod o).
Answer= GCD (m,n) = GCD (n, m mod n)
Q10. What is the total running time of the binary GCD algorithm?.
A. O(N).
B. O(N^2).
C. O(log N).
D. O(N log N).
Answer= O(N^2)
Q11. What is the GCD of 20 and 12 using Euclid’s algorithm?.
A. 8.
B. 2.
C. 4.
D. 6.
Answer= 4
Q12. Strassen’s algorithm is a/an_____________ algorithm..
A. Non- recursive.
B. Recursive.
C. Approximation.
D. Accurate.
Answer= Recursive
Q13. What is the running time of Strassen’s algorithm for matrix multiplication?.
A. O(n^2.81).
B. O(n3).
C. O(n1.8).
D. O(n^2).
Answer= O(n^2.81)
Q14. What is the running time of naïve matrix multiplication algorithm?.
A. O(n^2.81).
B. O(n4).
C. O(n).
D. O(n3).
Answer= O(n3)
Q15. Strassen’s matrix multiplication algorithm follows ___________ technique..
A. Greedy technique.
B. Dynamic Programming.
C. Divide and Conquer.
D. Backtracking.
Answer= Divide and Conquer
Q16. The number of scalar additions and subtractions used in Strassen’s matrix multiplication algorithm is ________.
A. O(n^2.81).
B. Theta(n^2).
C. Theta(n).
D. O(n3).
Answer= Theta(n^2)
Q17. Who demonstrated the difference in numerical stability?.
A. Strassen.
B. Bailey.
C. Lederman.
D. Higham.
Answer= Higham
Q18. What is the recurrence relation used in Strassen’s algorithm?.
A. 7T(n/2) + Theta(n^2).
B. 8T(n/2) + Theta(n^2).
C. 7T(n/2) + O(n^2).
D. 8T(n/2) + O(n^2).
Answer= 7T(n/2) + Theta(n^2)
Q19. Who discussed techniques for reducing the memory requirements for Strassen’s algorithm?.
A. Strassen.
B. Lederman.
C. Bailey.
D. Higham.
Answer= Bailey
Q20. What is the formula to calculate the element present in second row, first column of the product matrix?.
A. M1+M7.
B. M1+M3.
C. M2+M4 – M5 + M7.
D. M2+M4.
Answer= M2+M4
Q21. Strassen’s Matrix Algorithm was proposed by _____________.
A. Volker Strassen.
B. Andrew Strassen.
C. Victor Jan.
D. Virginia Williams.
Answer= Volker Strassen
Q22. How many iterating statements are involved in the naïve method of matrix multiplication?.
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 3
Q23. Strassen’s algorithm is quite numerically stable as the naïve method..
A. TRUE.
B. FALSE.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= FALSE
Q24. Compute the product matrix using Strassen’s matrix multiplication algorithm.Given a11=1; a12=3;a21=5;a22=7b11=8;b12=4;b21=6;b22=2.
A. c11=20;c12=12;c21=100;c22=15.
B. c11=22;c12=8;c21=90;c22=32.
C. c11=15;c12=7;c21=80;c22=34.
D. c11=26;c12=10;c21=82;c22=34.
Answer= c11=26;c12=10;c21=82;c22=34
Q25. What is pseudo random number generator?.
A. an algorithm that generates random numbers with help of mathematical formula.
B. an algorithm that generates random numbers according to user activity.
C. an algorithm that generates random numbers according to time.
D. an algorithm that generates random numbers with help of user input.
Answer= an algorithm that generates random numbers with help of mathematical formula
Q26. What should be the return type of rand() function?.
A. int.
B. float.
C. long.
D. double.
Answer= int
Q27. What is the purpose of using function srand()?.
A. to set the seed of rand() function.
B. to generate random numbers.
C. to enable rand() function.
D. to improve efficiency of rand().
Answer= to set the seed of rand() function
Q28. What is the range of rand()?.
A. 0 to RAND_MAX.
B. 0 to infinity.
C. 0 to 2147483647.
D. 0 to 32767.
Answer= 0 to RAND_MAX
Q29. Which of the following will generate random numbers in the range 1-100 (both inclusive)?.
A. rand() % 100.
B. rand() % 101.
C. (rand() % (101)) + 1.
D. (rand() % (100)) + 1.
Answer= (rand() % (100)) + 1
Q30. What is the minimum value of RAND_MAX possible in any implementation?.
A. 0.
B. 32767.
C. 2147483647.
D. 128.
Answer= 32767
Q31. Function rand() generates unique random numbers every time..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= false
Q32. What is the default value of seed if function rand() is called before srand()?.
A. srand(0).
B. srand(1).
C. srand(time(null)).
D. srand(-1).
Answer= srand(1)
Q33. Which header file contains the function rand() in C language?.
A. stdlib.
B. iostream.
C. stdio.
D. time.
Answer= stdlib
Q34. The dictionary ordering of elements is known as?.
A. Lexicographical order.
B. Colexicographical order.
C. Well order.
D. Sorting.
Answer= Lexicographical order
Q35. How many permutations will be formed from the array arr={1,2,3}?.
A. 2.
B. 4.
C. 6.
D. 8.
Answer= 6
Q36. What will be the lexicographical order of permutations formed from the array arr={1,2,3}?.
A. {{2,1,3},{3,2,1},{3,1,2},{2,3,1},{1,2,3},{1,3,2}}.
B. {{1,2,3},{1,3,2},{2,3,1},{2,1,3},{3,2,1},{3,1,2}}.
C. {{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}.
D. {{2,1,3},{3,1,2},{3,2,1},{2,3,1},{1,2,3},{1,3,2}}.
Answer= {{1,2,3},{1,3,2},{2,1,3},{2,3,1},{3,1,2},{3,2,1}}
Q37. What is the time complexity of Heap’s algorithm?.
A. O(n log n).
B. O(n^2).
C. O(n*n!).
D. O(n!).
Answer= O(n!)
Q38. What is meant by the term lexicographical order?.
A. dictionary ordering of elements.
B. reverse dictionary ordering of elements.
C. to sort according to value of first element.
D. to sort according to value of last element.
Answer= dictionary ordering of elements
Q39. How many combinations of 2 elements will be formed from the array arr={1,2,3}?.
A. 1.
B. 2.
C. 3.
D. 4.
Answer= 3
Q40. What will be the lexicographical order of combinations of 2 elements each formed from the array arr={1,2,3}?.
A. {{2,1},{3,2},{3,1}}.
B. {{1,2},{2,3},{1,3}}.
C. {{1,2},{1,3},{2,3}}.
D. {{2,1},{3,1},{3,2}}.
Answer= {{1,2},{1,3},{2,3}}
Q41. What will be the auxiliary space requirement (excluding call stack) of the program to print combinations of r elements each from array of size n?.
A. O(n*r).
B. O(n/r).
C. O(n).
D. O(r).
Answer= O(r)
Q42. The code for printing combinations is in-place..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= false
Q43. What will be the time complexity of the code to print combinations?.
A. O(n).
B. O(n^2).
C. O(n log n).
D. O(2n).
Answer= O(2n)
Q44. What is meant by integer partition?.
A. representing an integer as sum of positive and negative real numbers.
B. representing an integer as sum of positive and negative integers.
C. representing an integer as sum of positive integers.
D. representing an integer as sum of positive real numbers.
Answer= representing an integer as sum of positive integers
Q45. How many partitions will be formed for the integer 3?.
A. 2.
B. 3.
C. 4.
D. 8.
Answer= 3
Q46. What is meant by number theory?.
A. study of integers.
B. study of complex numbers.
C. numerology.
D. theory of origination of mathematics.
Answer= study of integers
Q47. Which of the following is true according to Ramanujan’s congruence?.
A. No. of partitions are divisible by 5 for a number 3 more than a multiple of 5.
B. No. of partitions are divisible by 5 for a number 4 more than a multiple of 5.
C. No. of partitions are divisible by 5 for a number 2 more than a multiple of 5.
D. No. of partitions are divisible by 5 for a number 1 more than a multiple of 5.
Answer= No. of partitions are divisible by 5 for a number 4 more than a multiple of 5
Q48. The no. of partitions of which of the following integer will be divisible by 5?.
A. 3.
B. 5.
C. 9.
D. 6.
Answer= 9
Q49. What is meant by the power set of a set?.
A. subset of all sets.
B. set of all subsets.
C. set of particular subsets.
D. empty set.
Answer= set of all subsets
Q50. Number of elements in the power set of set S={1,2,3} will be?.
A. 2.
B. 4.
C. 6.
D. 8.
Answer= 8
Q51. Number of elements in the power set of set S={1,2,2} will be?.
A. 2.
B. 4.
C. 6.
D. 8.
Answer= 6
Q52. Which one of the following problem types does inclusion-exclusion principle belong to?.
A. Numerical problems.
B. Graph problems.
C. String processing problems.
D. Combinatorial problems.
Answer= Combinatorial problems
Q53. ____________ is one of the most useful principles of enumeration in combinationatorics and discrete probability..
A. Inclusion-exclusion principle.
B. Quick search algorithm.
C. Euclid’s algorithm.
D. Set theory.
Answer= Inclusion-exclusion principle
Q54. Which of the following is not an application of inclusion-exclusion principle?.
A. Counting intersections.
B. Graph coloring.
C. Matching of bipartite graphs.
D. Maximum flow problem.
Answer= Maximum flow problem
Q55. Who invented the concept of inclusion-exclusion principle?.
A. Abraham de Moivre.
B. Daniel Silva.
C. J.J. Sylvester.
D. Sieve.
Answer= Abraham de Moivre
Q56. Which of the following statement is incorrect with respect to generalizing the solution using the inclusion-exclusion principle?.
A. including cardinalities of sets.
B. excluding cardinalities of pairwise intersections.
C. excluding cardinalities of triple-wise intersections.
D. excluding cardinalities of quadraple-wise intersections.
Answer= excluding cardinalities of triple-wise intersections
Q57. Counting intersections can be done using the inclusion-exclusion principle only if it is combined with De Morgan’s laws of complementing..
A. true.
B. false.
C. Nothing Can be Said.
D. None of the mentioned.
Answer= true
Q58. Using the inclusion-exclusion principle, find the number of integers from a set of 1-100 that are not divisible by 2, 3 and 5..
A. 22.
B. 25.
C. 26.
D. 33.
Answer= 26
Q59. ____________ is an arithmetic function that calculates the total number of positive integers less than or equal to some number n, that are relatively prime to n..
A. Euler’s phi function.
B. Euler’s omega function.
C. Cauchy’s totient function.
D. Legrange’s function.
Answer= Euler’s phi function
Q60. Let A={1,2,3} B={2,3,4} C={1,3,5} D={2,3}. Find the cardinality of sum of all the sets..
A. 6.
B. 5.
C. 4.
D. 7.
Answer= 5
Q61. The shortest distance between a line and a point is achieved when?.
A. a line is drawn at 90 degrees to the given line from the given point.
B. a line is drawn at 180 degrees to the given line from the given point.
C. a line is drawn at 60 degrees to the given line from the given point.
D. a line is drawn at 270 degrees to the given line from the given point.
Answer= a line is drawn at 90 degrees to the given line from the given point
Q62. What is the distance between the lines 3x-4y+7=0 and 3x-4y+5=0?.
A. 1 unit.
B. 0.5 unit.
C. 0.8 unit.
D. 0.4 unit.
Answer= 0.4 unit