1. | Recursion is similar to which of the following? |
A. | switch case |
B. | loop |
C. | if-else |
D. | if elif else |
Answer» B. loop | |
Explanation: recursion is similar to a loop. |
2. | Recursion is a method in which the solution of a problem depends on |
A. | larger instances of different problems |
B. | larger instances of the same problem |
C. | smaller instances of the same problem |
D. | smaller instances of different problems |
Answer» C. smaller instances of the same problem | |
Explanation: in recursion, the solution of a problem depends on the solution of smaller instances of the same problem. |
3. | Which of the following problems can’t be solved using recursion? |
A. | factorial of a number |
B. | nth fibonacci number |
C. | length of a string |
D. | problems without base case |
Answer» D. problems without base case | |
Explanation: problems without base case leads to infinite recursion call. in general, we will assume a base case to avoid infinite recursion call. problems like finding factorial of a number, nth fibonacci number and |
4. | In general, which of the following methods isn’t used to find the factorial of a number? |
A. | recursion |
B. | iteration |
Answer» A. recursion | |
Explanation: the function counts the number of vowels in a string. in this case the number is vowels is 6. |
5. | Which of the following recursive formula can be used to find the factorial of a number? |
A. | fact(n) = n * fact(n) |
B. | fact(n) = n * fact(n+1) |
C. | fact(n) = n * fact(n-1) |
D. | fact(n) = n * fact(1) |
Answer» C. fact(n) = n * fact(n-1) | |
Explanation: fact(n) = n * fact(n – 1) can be used to find the factorial of a number. |
6. | Suppose the first fibonnaci number is 0 and the second is 1. What is the sixth fibonnaci number? |
A. | 5 |
B. | 6 |
C. | 7 |
D. | 8 |
Answer» A. 5 | |
Explanation: the sixth fibonnaci number is |
7. | Which of the following is not a fibonnaci number? |
A. | 8 |
B. | 21 |
C. | 55 |
D. | 14 |
Answer» D. 14 | |
Explanation: 14 is not a fibonnaci number. |
8. | Which of the following option is wrong? |
A. | fibonacci number can be calculated by using dynamic programming |
B. | fibonacci number can be calculated by using recursion method |
C. | fibonacci number can be calculated by using iteration method |
D. | no method is defined to calculate fibonacci number |
Answer» D. no method is defined to calculate fibonacci number | |
Explanation: fibonacci number can be calculated by using dynamic programming, recursion method, iteration method. |
9. | Which of the following recurrence relations can be used to find the nth fibonacci number? |
A. | f(n) = f(n) + f(n – 1) |
B. | f(n) = f(n) + f(n + 1) |
C. | f(n) = f(n – 1) |
D. | f(n) = f(n – 1) + f(n – 2) |
Answer» D. f(n) = f(n – 1) + f(n – 2) | |
Explanation: the relation f(n) = f(n – 1) + f(n – 2) can be used to find the nth fibonacci number. |
10. | Which of the following gives the sum of the first n natural numbers? |
A. | nc2 |
B. | (n-1)c2 |
C. | (n+1)c2 |
D. | (n+2)c2 |
Answer» C. (n+1)c2 | |
Explanation: the sum of first n natural numbers is given by n*(n+1)/2, which is equal to (n+1)c2. |
11. | If GCD of two number is 8 and LCM is 144, then what is the second number if first number is 72? |
A. | 24 |
B. | 2 |
C. | 3 |
D. | 16 |
Answer» D. 16 | |
Explanation: as a * b = gcd (a, b) * lcm (a, b). so b = (144 * 8)/72 = 16. |
12. | Which of the following is also known as GCD? |
A. | highest common divisor |
B. | highest common multiple |
C. | highest common measure |
D. | lowest common multiple |
Answer» A. highest common divisor | |
Explanation: gcm (greatest common measure), gcf (greatest common factor), hcf (highest common factor) and hcf (highest common divisor) are also known as gcd. |
13. | Which of the following is coprime number? |
A. | 54 and 24 |
B. | 4 and 8 |
C. | 6 and 12 |
D. | 9 and 28 |
Answer» D. 9 and 28 | |
Explanation: coprime numbers have gcd 1. so 9 and 28 are coprime numbers. while 54 |
14. | In terms of Venn Diagram, which of the following expression gives GCD (Given A ꓵ B ≠ Ø)? |
A. | multiplication of a u b terms |
B. | multiplication of a ꓵ b terms |
C. | multiplication of a*b terms |
D. | multiplication of a-b terms |
Answer» B. multiplication of a ꓵ b terms | |
Explanation: in terms of venn diagram, the gcd is given by the intersection of two sets. so a ꓵ b gives the gcd. while a u b gives the lcm. |
15. | What is the GCD according to the given Venn Diagram? |
A. | 2 |
B. | 3 |
C. | 5 |
D. | 6 |
Answer» C. 5 | |
Explanation: in terms of venn diagram, the gcd is given by the intersection of two sets. so a ꓵ b gives the gcd. while a u b gives the lcm. so here a ꓵ b is 5. |
16. | What is the GCD of a and b? |
A. | a + b |
B. | gcd (a-b, b) if a>b |
C. | gcd (a+b, a-b) |
D. | a – b |
Answer» B. gcd (a-b, b) if a>b | |
Explanation: as per euclid’s algorithm, gcd (a, b) = gcd (a-b, b) if a > b or gcd (a, b) = gcd (a, b-a) if b > a. |
17. | What is the GCD of 48, 18, 0? |
A. | 24 |
B. | 2 |
C. | 3 |
D. | 6 |
Answer» D. 6 | |
Explanation: gcd is largest positive integer that divides each of the integer. so the gcd of 48, 18, 0 is 6. |
18. | Is 9 and 28 coprime number? |
A. | true |
B. | false |
Answer» A. true | |
Explanation: coprime numbers have gcd 1. so 9 and 28 are coprime numbers. |
19. | If gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then what is the expression called? |
A. | bezout’s identity |
B. | multiplicative identity |
C. | sum of product |
D. | product of sum |
Answer» A. bezout’s identity | |
Explanation: if gcd (a, b) is defined by the expression, d=a*p + b*q where d, p, q are positive integers and a, b is both not zero, then the expression is called bezout’s identity and p, q can be calculated by extended form of euclidean algorithm. |
20. | Is gcd an associative function. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: the gcd function is an associative function as gcd (a, gcd (b, c)) = gcd (gcd (a, b), c). |
21. | Who gave the expression for the probability and expected value of gcd? |
A. | james e. nymann |
B. | riemann |
C. | thomae |
D. | euler |
Answer» A. james e. nymann | |
Explanation: in the year 1972, james e. nymann showed some result to show the probability and expected value of gcd. |
22. | What is the computational complexity of Binary GCD algorithm where a and b are integers? |
A. | o (log a + log b)2) |
B. | o (log (a + b)) |
C. | o (log ab) |
D. | o (log a-b) |
Answer» A. o (log a + log b)2) | |
Explanation: from the binary gcd algorithm, it is found that the computational complexity is o (log a + log b)2) as the total number of steps in the execution is at most the total sum of number of bits of a and b. |
23. | LCM is also called as |
A. | gcd |
B. | scm |
C. | gcf |
D. | hcf |
Answer» B. scm | |
Explanation: gcd (greatest common divisor), gcf (greatest common factor), hcf (highest common factor) is not an alias for lcm. lcm is also called as smallest common multiple(scm). |
24. | What is the LCM of 8 and 13? |
A. | 8 |
B. | 12 |
C. | 20 |
D. | 104 |
Answer» D. 104 | |
Explanation: 104 is the smallest positive integer that is divisible by both 8 and 12. |
26. | Which of the following is also known as LCM? | |
A. | lowest common divisor | |
B. | least common multiple | |
C. | lowest common measure | |
D. | highest common multiple | |
Answer» A. lowest common divisor | ||
Explanation: least common multiple is also known as lcm or lowest common multiple. | ||
27. | What is the LCM of two coprime numbers? |
A. | 1 |
B. | 0 |
C. | addition of two coprime numbers |
D. | multiplication of two coprime numbers |
Answer» D. multiplication of two coprime numbers | |
Explanation: coprime numbers have gcd 1. while lcm of coprime numbers is the product of those two coprime numbers. |
28. | In terms of Venn Diagram, which of the following expression gives LCM (Given A ꓵ B ≠ Ø)? |
A. | multiplication of a u b terms |
B. | multiplication of a ꓵ b terms |
C. | multiplication of a*b terms |
D. | multiplication of a-b terms |
Answer» A. multiplication of a u b terms | |
Explanation: in terms of venn diagram, the lcm is given by the union of two sets. so a u b gives the lcm. while a ꓵ b gives the gcd. |
29. | What is the LCM according to the given Venn Diagram? |
A. | 2 |
B. | 3 |
C. | 180 |
D. | 6 |
Answer» C. 180 | |
Explanation: in terms of venn diagram, the lcm is given by the union of two sets. so a u b gives the lcm. so product of all the terms is 180. |
30. | What is the lcm (a, b)? |
A. | a + b |
B. | gcd (a-b, b) if a>b |
C. | lcm (b, a) |
D. | a – b |
Answer» C. lcm (b, a) | |
Explanation: since the lcm function is commutative, so lcm (a, b) = lcm (b, a). |
31. | Is 9 and 28 coprime number. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: coprime numbers have gcd 1 |
32. | What is the following expression, lcm (a, lcm (b, c) equal to? |
A. | lcm (a, b, c) |
B. | a*b*c |
C. | a + b + c |
D. | lcm (lcm (a, b), c) |
Answer» D. lcm (lcm (a, b), c) | |
Explanation: since lcm function follows associativity, hence lcm (a, lcm (b, c) is equal to lcm (lcm (a, b), c). |
33. | Is lcm an associative function. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: the lcm function is an associative function as lcm (a, lcm (b, c) is equal to lcm (lcm (a, b), c). |
34. | What is the following expression, lcm (a, gcd (a, b)) equal to? |
A. | a |
B. | b |
C. | a*b |
D. | a + b |
Answer» A. a | |
Explanation: since the lcm function follows absorption laws so lcm (a, gcd (a, b)) equal to a. |
35. | Which algorithm is the most efficient numerical algorithm to obtain lcm? |
A. | euler’s algorithm |
B. | euclid’s algorithm |
C. | chebyshev function |
D. | partial division algorithm |
Answer» B. euclid’s algorithm | |
Explanation: the most efficient way of calculating the lcm of a given number is using euclid’s algorithm which computes the lcm in much lesser time compared to other algorithms. |
36. | Which of the following methods can be used to find the sum of digits of a number? |
A. | recursion |
B. | iteration |
C. | greedy algorithm |
D. | both recursion and iteration |
Answer» D. both recursion and iteration | |
Explanation: both recursion and iteration can be used to find the sum of digits of a number. |
37. | What can be the maximum sum of digits for a 4 digit number? |
A. | 1 |
B. | 16 |
C. | 36 |
D. | 26 |
Answer» C. 36 | |
Explanation: the sum of digits will be maximum when all the digits are 9. thus, the sum will be maximum for the number 9999, which is 36. |
38. | What can be the minimum sum of digits for a 4 digit number? |
A. | 0 |
B. | 1 |
C. | 16 |
D. | 36 |
Answer» B. 1 | |
Explanation: the sum of digits will be minimum for the number 1000 and the sum is 1. |
39. | What is the time complexity of the above code used to reverse a string? |
A. | copies a string to another string |
B. | compares two strings |
C. | reverses a string |
D. | checks if a string is a palindrome |
Answer» D. checks if a string is a palindrome | |
Explanation: the main purpose of the above code is to check if a string is a palindrome. |
40. | Which of the following is the binary representation of 100? |
A. | 1010010 |
B. | 1110000 |
C. | 1100100 |
D. | 1010101 |
Answer» C. 1100100 | |
Explanation: 100 = 64 + 32 + 4 = 26 + 25 + |
41. | What is the time complexity of the above recursive implementation used to reverse a string? |
A. | o(1) |
B. | o(n) |
C. | o(n2) |
D. | o(n3) |
Answer» B. o(n) | |
Explanation: the time complexity of the above recursive implementation used to |
42. | What is the time complexity of matrix multiplied recursively by Divide and Conquer Method? |
A. | o(n) |
B. | o(n2) |
C. | o(n3) |
D. | o(n!) |
Answer» C. o(n3) | |
Explanation: the time complexity of recursive multiplication of two square matrices by the divide and conquer method is found to be o(n3) since there are total of 8 recursive calls. |
43. | How many recursive calls are there in Recursive matrix multiplication by Strassen’s Method? |
A. | 5 |
B. | 7 |
C. | 8 |
D. | 4 |
Answer» B. 7 | |
Explanation: for the multiplication two square matrix recursively using strassen’s method, there are 7 recursive calls performed for high time complexity. |
44. | Matrix A is of order 3*4 and Matrix B is of order 4*5. How many elements will be there in a matrix A*B multiplied recursively. |
A. | 12 |
B. | 15 |
C. | 16 |
D. | 20 |
Answer» B. 15 | |
Explanation: the resultant matrix will be of order 3*5 when multiplied recursively and therefore the matrix will have 3*5=15 elements. |
45. | If Matrix X is of order A*B and Matrix Y is of order C*D, and B=C then the order of the Matrix X*Y is A*D? |
A. | true |
B. | false |
Answer» A. true | |
Explanation: given that b=c, so the two matrix can be recursively multiplied. |
46. | Is Coppersmith-Winograd algorithm better than Strassen’s algorithm in terms of time complexity? |
A. | true |
B. | false |
Answer» A. true | |
Explanation: since the coppersmith- winograd algorithm multiplies the matrices in o(n2.37) time. the time complexity of recursive multiplication of two square matrices by strassen’s method is found to be o(n2.80). therefore, coppersmith-winograd |
47. | Which of the following statement is true about stack? |
A. | pop operation removes the top most element |
B. | pop operation removes the bottom most element |
C. | push operation adds new element at the bottom |
D. | push operation removes the top most element |
Answer» A. pop operation removes the top most element | |
Explanation: as stack is based on lifo(last in first out) principle so the deletion takes place from the topmost element. thus pop operator removes topmost element. |
48. | What is the space complexity of program to reverse stack recursively? |
A. | o(1) |
B. | o(log n) |
C. | o(n) |
D. | o(n log n) |
Answer» C. o(n) | |
Explanation: the recursive program to reverse stack uses memory of the order n to store function call stack. |
49. | Stack can be reversed without using extra space by |
A. | using recursion |
B. | using linked list to implement stack |
C. | using an extra stack |
D. | it is not possible |
Answer» B. using linked list to implement stack | |
Explanation: if linked list is used for implementing stack then it can be reversed without using any extra space. |
51. | What is the time complexity of the program to reverse stack when linked list is used for its implementation? |
A. | o(n) |
B. | o(n log n) |
C. | o(n2) |
D. | o(log n) |
Answer» A. o(n) | |
Explanation: as a linked list takes o(n) time for getting reversed thus linked list version of stack will also take the same time. |
52. | Which of the following takes O(n) time in worst case in array implementation of stack? |
A. | pop |
B. | push |
C. | isempty |
D. | pop, push and isempty takes constant time |
Answer» D. pop, push and isempty takes constant time | |
Explanation: functions pop, push and isempty all are implemented in constant time in worst case. |
53. | What will be the time complexity of the code to reverse stack recursively? |
A. | o(n) |
B. | o(n log n) |
C. | o(log n) |
D. | o(n2) |
Answer» D. o(n2) | |
Explanation: the recurrence relation for the recursive code to reverse stack will be given by-t(n)=t(n-1)+n.this is calculated to be equal to o(n2). |
54. | Which of the following sorting algorithm has best case time complexity of O(n2)? |
A. | bubble sort |
B. | selection sort |
C. | insertion sort |
D. | stupid sort |
Answer» B. selection sort | |
Explanation: selection sort is not an adaptive sorting algorithm. it finds the index of minimum element in each iteration even if the |
55. | Which of the following is the biggest advantage of selection sort? |
A. | its has low time complexity |
B. | it has low space complexity |
C. | it is easy to implement |
D. | it requires only n swaps under any condition |
Answer» D. it requires only n swaps under any condition | |
Explanation: selection sort works by obtaining least value element in each iteration and then swapping it with the current index. so it will take n swaps under any condition which will be useful when memory write operation is expensive. |
56. | What will be the recurrence relation of the code of recursive selection sort? |
A. | t(n) = 2t(n/2) + n |
B. | t(n) = 2t(n/2) + c |
C. | t(n) = t(n-1) + n |
D. | t(n) = t(n-1) + c |
Answer» C. t(n) = t(n-1) + n | |
Explanation: function to find the minimum element index takes n time.the recursive call is made to one less element than in the previous call so the overall recurrence relation becomes t(n) = t(n-1) + n. |
57. | Which of the following sorting algorithm is NOT stable? |
A. | selection sort |
B. | brick sort |
C. | bubble sort |
D. | merge sort |
Answer» A. selection sort | |
Explanation: out of the given options selection sort is the only algorithm which is not stable. it is because the order of identical elements in sorted output may be different from input array. |
58. | What will be the best case time complexity of recursive selection sort? |
A. | o(n) |
B. | o(n2) |
C. | o(log n) |
D. | o(n log n) |
Answer» B. o(n2) | |
Explanation: selection sort’s algorithm is such that it finds the index of minimum element in each iteration even if the given array is already sorted. thus its best case time complexity becomes o(n2). |
59. | Recursive selection sort is a comparison based sort. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: in selection sort we need to compare elements in order to find the minimum element in each iteration. so we can say that it uses comparisons in order to sort the array. thus it qualifies as a comparison based sort. |
60. | What is the average case time complexity of recursive selection sort? |
A. | o(n) |
B. | o(n log n) |
C. | o(n2) |
D. | o(log n) |
Answer» C. o(n2) | |
Explanation: the overall recurrence relation of recursive selection sort is given by t(n) = t(n-1) + n. it is found to be equal to o(n2). it is unvaried throughout the three cases. |
61. | What is the bidirectional variant of selection sort? |
A. | cocktail sort |
B. | bogo sort |
C. | gnome sort |
D. | bubble sort |
Answer» A. cocktail sort | |
Explanation: a bidirectional variant of selection sort is called cocktail sort. it’s an algorithm which finds both the minimum and maximum values in the array in every pass. |
62. | Which of the following methods can be used to find the largest and smallest element in an array? |
A. | recursion |
B. | iteration |
C. | both recursion and iteration |
D. | no method is suitable |
Answer» C. both recursion and iteration | |
Explanation: both recursion and iteration can be used to find the largest and smallest element in an array. |
63. | What is the number of swaps required to sort the array arr={5,3,2,4,1} using recursive selection sort? |
A. | 0 |
B. | 1 |
C. | 2 |
D. | 3 |
Answer» C. 2 | |
Explanation: the first swap takes place between 1 and 5. the second swap takes place between 3 and 2 which sorts our array. |
64. | Which of the following methods can be used to find the largest and smallest number in a linked list? |
A. | recursion |
B. | iteration |
C. | both recursion and iteration |
D. | impossible to find the largest and smallest numbers |
Answer» C. both recursion and iteration | |
Explanation: both recursion and iteration can be used to find the largest and smallest |
65. | Which of the following techniques can be used to search an element in an unsorted array? |
A. | iterative linear search |
B. | recursive binary search |
C. | iterative binary search |
D. | normal binary search |
Answer» A. iterative linear search | |
Explanation: iterative linear search can be used to search an element in an unsorted array. |
66. | Consider the array {1,1,1,1,1}. Select the wrong option? |
A. | iterative linear search can be used to search for the elements in the given array |
B. | recursive linear search can be used to search for the elements in the given array |
C. | recursive binary search can be used to search for the elements in the given array |
D. | no method is defined to search for an element in the given array |
Answer» D. no method is defined to search for an element in the given array | |
Explanation: iterative linear search, recursive linear search and recursive binary search can be applied to search for an element in the above given array. |
67. | What is the time complexity of the above recursive implementation of binary search? |
A. | o(n) |
B. | o(2n) |
C. | o(logn) |
D. | o(n!) |
Answer» C. o(logn) | |
Explanation: the time complexity of the above recursive implementation of binary search is o(logn). |
68. | Which of the following methods can be used to search an element in a linked list? |
A. | iterative linear search |
B. | iterative binary search |
C. | recursive binary search |
D. | normal binary search |
Answer» A. iterative linear search | |
Explanation: iterative linear search can be used to search an element in a linked list. |
69. | Can binary search be applied on a sorted linked list in O(Logn) time? |
A. | no |
B. | yes |
Answer» A. no | |
Explanation: since linked list doesn’t allow random access, binary search cannot be applied on a sorted linked list in o(logn) |
70. | Recursive program to raise an integer x to power y uses which of the following algorithm? |
A. | dynamic programming |
B. | backtracking |
C. | divide and conquer |
D. | greedy algorithm |
Answer» C. divide and conquer | |
Explanation: the recursive approach uses divide and conquer algorithm as we break the problem into smaller parts and then solve the smaller parts and finally combine their results to get the overall solution. |
71. | What is the least time in which we can raise a number x to power y? |
A. | o(x) |
B. | o(y) |
C. | o(log x) |
D. | o(log y) |
Answer» D. o(log y) | |
Explanation: we can optimize the code for finding power of a number by calculating x raised to power y/2 only once and using it depending on whether y is even or odd. |
72. | What is the advantage of iterative code for finding power of number over recursive code? |
A. | iterative code requires less time |
B. | iterative code requires less space |
C. | iterative code is more compiler friendly |
D. | it has no advantage |
Answer» B. iterative code requires less space | |
Explanation: both iterative and recursive approach can be implemented in log n time but the recursive code requires memory in call stack which makes it less preferable. |
73. | Recursive approach to find power of a number is preferred over iterative approach. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: the recursive code requires memory in call stack which makes it less preferable as compared to iterative approach. |
74. | What is the objective of tower of hanoi puzzle? |
A. | to move all disks to some other rod by following rules |
B. | to divide the disks equally among the three rods by following rules |
C. | to move all disks to some other rod in random order |
D. | to divide the disks equally among three rods in random order |
Answer» A. to move all disks to some other rod by following rules | |
Explanation: objective of tower of hanoi problem is to move all disks to some other rod by following the following rules-1) only one disk can be moved at a time. 2) disk can |
76. | Tower of hanoi problem can be solved iteratively. | |
A. | true | |
B. | false | |
Answer» A. true | ||
Explanation: iterative solution to tower of hanoi puzzle also exists. its approach depends on whether the total numbers of disks are even or odd. | ||
77. | Minimum time required to solve tower of hanoi puzzle with 4 disks assuming one move takes 2 seconds, will be |
A. | 15 seconds |
B. | 30 seconds |
C. | 16 seconds |
D. | 32 seconds |
Answer» B. 30 seconds | |
Explanation: number of moves = 24-1=16- 1=15 |
78. | Master’s theorem is used for? |
A. | solving recurrences |
B. | solving iterative relations |
C. | analysing loops |
D. | calculating the time complexity of any code |
Answer» A. solving recurrences | |
Explanation: master’s theorem is a direct method for solving recurrences. we can solve any recurrence that falls under any one of the three cases of master’s theorem. |
79. | How many cases are there under Master’s theorem? |
A. | 2 |
B. | 3 |
C. | 4 |
D. | 5 |
Answer» B. 3 | |
Explanation: there are primarily 3 cases under master’s theorem. we can solve any recurrence that falls under any one of these three cases. |
80. | What is the result of the recurrences which fall under second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc? |
A. | none of the below |
B. | t(n) = o(nc log n) |
C. | t(n) = o(f(n)) |
D. | t(n) = o(n2) |
Answer» B. t(n) = o(nc log n) | |
Explanation: in second case of master’s theorem the necessary condition is that c = logba. if this condition is true then t(n) = o(nc log n) |
81. | What is the result of the recurrences which fall under third case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc? |
A. | none of the below |
B. | t(n) = o(nc log n) |
C. | t(n) = o(f(n)) |
D. | t(n) = o(n2) |
Answer» C. t(n) = o(f(n)) | |
Explanation: in third case of master’s theorem the necessary condition is that c > logba. if this condition is true then t(n) = o(f(n)). |
82. | We can solve any recurrence by using Master’s theorem. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: no we cannot solve all the recurrences by only using master’s theorem. we can solve only those which fall under the three cases prescribed in the theorem. |
83. | Under what case of Master’s theorem will the recurrence relation of merge sort fall? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | it cannot be solved using master’s theorem |
Answer» B. 2 | |
Explanation: the recurrence relation of merge sort is given by t(n) = 2t(n/2) + o(n). so we can observe that c = logba so it will fall under case 2 of master’s theorem. |
84. | Under what case of Master’s theorem will the recurrence relation of stooge sort fall? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | it cannot be solved using master’s theorem |
Answer» A. 1 | |
Explanation: the recurrence relation of stooge sort is given as t(n) = 3t(2/3n) + o(1). it is found too be equal to o(n2.7) using master’s theorem first case. |
85. | Which case of master’s theorem can be extended further? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | no case can be extended |
Answer» B. 2 | |
Explanation: the second case of master’s theorem can be extended for a case where f(n) |
86. | What is the result of the recurrences which fall under the extended second case of Master’s theorem (let the recurrence be given by T(n)=aT(n/b)+f(n) and f(n)=nc(log n)k? |
A. | none of the below |
B. | t(n) = o(nc log n) |
C. | t(n)= o(nc (log n)k+1 |
D. | t(n) = o(n2) |
Answer» C. t(n)= o(nc (log n)k+1 | |
Explanation: in the extended second case of master’s theorem the necessary condition is that c = logba. if this condition is true then t(n)= o(nc(log n))k+1. |
87. | Under what case of Master’s theorem will the recurrence relation of binary search fall? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | it cannot be solved using master’s theorem |
Answer» B. 2 | |
Explanation: the recurrence relation of binary search is given by t(n) = t(n/2) + o(1). so we can observe that c = logba so it will fall under case 2 of master’s theorem. |
88. | 7 T (n/2) + 1/n |
A. | t(n) = o(n) |
B. | t(n) = o(log n) |
C. | t(n) = o(n2log n) |
D. | cannot be solved using master’s theorem |
Answer» D. cannot be solved using master’s theorem | |
Explanation: the given recurrence cannot be solved by using the master’s theorem. it is because in this recurrence relation a < 1 so master’s theorem cannot be applied. |
89. | What is the worst case time complexity of KMP algorithm for pattern searching (m = length of text, n = length of pattern)? |
A. | o(n) |
B. | o(n*m) |
C. | o(m) |
D. | o(log n) |
Answer» C. o(m) | |
Explanation: kmp algorithm is an efficient pattern searching algorithm. it has a time complexity of o(m) where m is the length of text. |
90. | What is the time complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)? |
A. | o(n + m) |
B. | o(m) |
C. | o(n) |
D. | o(m * n) |
Answer» A. o(n + m) | |
Explanation: z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. it has a time complexity of o(m + n) where m is the length of text and n is the length of the pattern. |
91. | What is the auxiliary space complexity of Z algorithm for pattern searching (m = length of text, n = length of pattern)? |
A. | o(n + m) |
B. | o(m) |
C. | o(n) |
D. | o(m * n) |
Answer» B. o(m) | |
Explanation: z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. it an auxiliary space of o(m) for maintaining z array. |
92. | The naive pattern searching algorithm is an in place algorithm. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: the auxiliary space complexity required by naive pattern searching algorithm is o(1). so it qualifies as an in place algorithm. |
93. | Rabin Karp algorithm and naive pattern searching algorithm have the same worst case time complexity. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: the worst case time complexity of rabin karp algorithm is o(m*n) but it has a linear average case time complexity. so rabin karp and naive pattern searching algorithm have the same worst case time complexity. |
94. | Which of the following sorting algorithms is the fastest? |
A. | merge sort |
B. | quick sort |
C. | insertion sort |
D. | shell sort |
Answer» B. quick sort | |
Explanation: quick sort is the fastest known sorting algorithm because of its highly optimized inner loop. |
95. | Quick sort follows Divide-and-Conquer strategy. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: in quick sort, the array is divided into sub-arrays and then it is sorted (divide-and-conquer strategy). |
96. | What is the worst case time complexity of a quick sort algorithm? |
A. | o(n) |
B. | o(n log n) |
C. | o(n2) |
D. | o(log n) |
Answer» C. o(n2) | |
Explanation: the worst case performance of a quick sort algorithm is mathematically found to be o(n2). |
97. | Which of the following methods is the most effective for picking the pivot element? |
A. | first element |
B. | last element |
C. | median-of-three partitioning |
D. | random element |
Answer» C. median-of-three partitioning | |
Explanation: median-of-three partitioning is the best method for choosing an appropriate pivot element. picking a first, last or random element as a pivot is not much effective. |
98. | Which is the safest method to choose a pivot element? |
A. | choosing a random element as pivot |
B. | choosing the first element as pivot |
C. | choosing the last element as pivot |
D. | median-of-three partitioning method |
Answer» A. choosing a random element as pivot | |
Explanation: this is the safest method to choose the pivot element since it is very unlikely that a random pivot would consistently provide a poor partition. |
99. | What is the average running time of a quick sort algorithm? |
A. | o(n2) |
B. | o(n) |
C. | o(n log n) |
D. | o(log n) |
Answer» C. o(n log n) | |
Explanation: the best case and average case analysis of a quick sort algorithm are mathematically found to be o(n log n). |
101. | Quick sort uses join operation rather than merge operation. | |
A. | true | |
B. | false | |
Answer» A. true | ||
Explanation: quick sort uses join operation since join is a faster operation than merge. | ||
102. | How many sub arrays does the quick sort algorithm divide the entire array into? |
A. | one |
B. | two |
C. | three |
D. | four |
Answer» B. two | |
Explanation: the entire array is divided into two partitions, 1st sub array containing elements less than the pivot element and 2nd sub array containing elements greater than the pivot element. |
103. | Which is the worst method of choosing a pivot element? |
A. | first element as pivot |
B. | last element as pivot |
C. | median-of-three partitioning |
D. | random element as pivot |
Answer» A. first element as pivot | |
Explanation: choosing the first element as pivot is the worst method because if the input is pre-sorted or in reverse order, then the pivot provides a poor partition. |
104. | 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. a line is drawn at 90 degrees to the given line from the given point | |
Explanation: the shortest distance between a line and a point is achieved when a line is drawn at 90 degrees to the given line from the given point. |
105. | What is the shortest distance between the line given by -2x + 3y + 4 = 0 and the point (5,6)? |
A. | 4.5 units |
B. | 5.4 units |
C. | 4.3 units |
D. | 3.3 units |
Answer» D. 3.3 units | |
Explanation: the shortest distance between a line and a point is given by the formula (ax1+by1+c)/(√a2+b2). using this formula we get the answer 3.3 units. |
106. | 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» D. 0.4 unit | |
Explanation: as the given lines are parallel so the distance between them can be calculated by using the formula (c1- c2)/(√a2+b2). so we get the distance as 0.4 unit. |
107. | What will be the slope of the line given by ax + by + c = 0? |
A. | -a/b |
B. | -b/a |
C. | -c/a |
D. | a/c |
Answer» A. -a/b | |
Explanation: the slope of a line given by the equation ax + by + c=0 has the slope of -a/b. so two lines having the same ratio of the coefficient of x and y will be parallel to each other. |
108. | What will be the slope of the line given by 10x + 5y + 8=0? |
A. | -5 |
B. | -2 |
C. | -1.25 |
D. | 5 |
Answer» B. -2 | |
Explanation: the slope of a line given by the equation ax + by + c=0 has the slope of -a/b. so the slope of the given line will be -2. |
109. | Which of the following areas do closest pair problem arise? |
A. | computational geometry |
B. | graph colouring problems |
C. | numerical problems |
D. | string matching |
Answer» A. computational geometry | |
Explanation: closest pair problem arises in two most important areas- computational geometry and operational research. |
110. | What is the runtime efficiency of using brute force technique for the closest pair problem? |
A. | o(n) |
B. | o(n log n) |
C. | o(n2) |
D. | o(n3 log n) |
Answer» C. o(n2) | |
Explanation: the efficiency of closest pair algorithm by brute force technique is mathematically found to be o(n2). |
111. | The most important condition for which closest pair is calculated for the points (pi, pj) is? |
A. | i>j |
B. | i!=j |
C. | i=j |
D. | i<j |
Answer» D. i<j | |
Explanation: to avoid computing the distance between the same pair of points twice, we consider only the pair of points (pi, pj) for which i<=”” td=”” style=”box-sizing: border-box; border-width: 0px; border-style: solid; border-color: rgb(229, 231, 235); –tw-border-spacing-x: 0; –tw-border-spacing-y: 0; –tw-translate-x: 0; –tw-translate-y: 0; –tw-rotate: 0; –tw-skew-x: 0; –tw-skew-y: 0; –tw-scale-x: 1; –tw-scale-y: 1; –tw-pan-x: ; –tw-pan-y: ; –tw-pinch-zoom: ; –tw-scroll-snap-strictness: proximity; –tw-ordinal: ; –tw-slashed-zero: ; –tw-numeric-figure: ; –tw-numeric-spacing: ; –tw-numeric-fraction: ; –tw-ring-inset: ; –tw-ring-offset-width: 0px; –tw-ring-offset-color: #fff; –tw-ring-color: rgb(59 130 246 / .5); –tw-ring-offset-shadow: 0 0 #0000; –tw-ring-shadow: 0 0 #0000; –tw-shadow: 0 0 #0000; –tw-shadow-colored: 0 0 #0000; –tw-blur: ; –tw-brightness: ; –tw-contrast: ; –tw-grayscale: ; –tw-hue-rotate: ; –tw-invert: ; –tw-saturate: ; –tw-sepia: ; –tw-drop-shadow: ; –tw-backdrop-blur: ; –tw-backdrop-brightness: ; –tw-backdrop-contrast: ; –tw-backdrop-grayscale: ; –tw-backdrop-hue-rotate: ; –tw-backdrop-invert: ; –tw-backdrop-opacity: ; –tw-backdrop-saturate: ; –tw-backdrop-sepia: ;”> |
112. | What is the basic operation of closest pair algorithm using brute force technique? |
A. | euclidean distance |
B. | radius |
C. | area |
D. | manhattan distance |
Answer» A. euclidean distance | |
Explanation: the basic operation of closest |
113. | Which of the following is similar to Euclidean distance? |
A. | manhattan distance |
B. | pythagoras metric |
C. | chebyshev distance |
D. | heuristic distance |
Answer» B. pythagoras metric | |
Explanation: in older times, euclidean distance metric is also called a pythagoras metric which is the length of the line segment connecting two points. |
114. | Which of the following strategies does the following diagram depict? |
A. | divide and conquer strategy |
B. | brute force |
C. | exhaustive search |
D. | backtracking |
Answer» B. brute force | |
Explanation: brute force is a straight forward approach to solve critical problems. here, we use brute force technique to find the closest distance between p1 and p2. |
115. | Manhattan distance is an alternative way to define a distance between two points. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: manhattan distance is an alternative way to calculate distance. it is the distance between two points measured along axes at right angles. |
116. | What is the optimal time required for solving the closest pair problem using divide and conquer approach? |
A. | o(n) |
B. | o(log n) |
C. | o(n log n) |
D. | o(n2) |
Answer» C. o(n log n) | |
Explanation: the optimal time for solving using a divide and conquer approach is mathematically found to be o(n log n). |
117. | In divide and conquer, the time is taken for merging the subproblems is? |
A. | o(n) |
B. | o(n log n) |
C. | o(n2) |
D. | o(log n) |
Answer» B. o(n log n) | |
Explanation: the time taken for merging the smaller subproblems in a divide and conquer approach is mathematically found to be o(n log n). |
118. | The optimal time obtained through divide and conquer approach using merge sort is the best case efficiency. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: the optimal time obtained through divide and conquer approach is the best class efficiency and it is given by Ω(n log n). |
119. | Which of the following strategies does the following diagram depict? |
A. | brute force |
B. | divide and conquer |
C. | exhaustive search |
D. | branch and bound |
Answer» B. divide and conquer | |
Explanation: the above diagram depicts the implementation of divide and conquer. the problem is divided into sub problems and are separated by a line. |
120. | Which of the points are closer to each other? |
A. | p1 and p11 |
B. | p3 and p8 |
C. | p2 and p3 |
D. | p9 and p10 |
Answer» C. p2 and p3 | |
Explanation: from symmetry, we determine that the closest pair is p2 and p3. but the exact calculations have to be done using euclid’s algorithm. |
121. | Cross product is a mathematical operation performed between |
A. | 2 scalar numbers |
B. | a scalar and a vector |
C. | 2 vectors |
D. | any 2 numbers |
Answer» C. 2 vectors | |
Explanation: cross product is a mathematical operation that is performed on 2 vectors in a 3d plane. it has many applications in computer programming and physics. |
122. | Cross product is also known as? |
A. | scalar product |
B. | vector product |
C. | dot product |
D. | multiplication |
Answer» B. vector product | |
Explanation: cross product is also known as a vector product. it is a mathematical operation that is performed on 2 vectors in 3d plane. |
123. | The concept of cross product is applied in the field of computer graphics. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: the concept of cross product find its application in the field of computer graphics. it can be used to find the winding of polygon about a point. |
124. | Which of the following equals the a x b ( a and b are two vectors)? |
A. | – (a x b) |
B. | a.b |
C. | b x a |
D. | – (b x a) |
Answer» D. – (b x a) | |
Explanation: the vector product a x b is equal to – (b x a). the minus sign shows that these vectors have opposite directions. |
126. | What will be the cross product of the vectors 2i + 3j + k and 3i + 2j + k? | |
A. | i + 2j + k | |
B. | 2i + 3j + k | |
C. | i + j – 5k | |
D. | 2i – j – 5k | |
Answer» C. i + j – 5k | ||
Explanation: we can find the cross product of the given vectors by solving the determinant. | ||
127. | What will be the cross product of the vectors 2i + 3j + k and 6i + 9j + 3k? |
A. | i + 2j + k |
B. | i – j – 5k |
C. | 0 |
D. | 2i – j – 5k |
Answer» C. 0 | |
Explanation: the given vectors are parallel to each other. the cross product of parallel vectors is 0 because sin(0) is 0. |
128. | Which of the following operation will give a vector that is perpendicular to both vectors a and b? |
A. | a x b |
B. | a.b |
C. | b x a |
D. | both a x b and b x a |
Answer» D. both a x b and b x a | |
Explanation: the resultant vector from the cross product of two vectors is perpendicular to the plane containing both vectors. so both a x b and b x a will give a vector that is perpendicular to both vectors a and b. |
129. | is a method of constructing a smallest polygon out of n given points. |
A. | closest pair problem |
B. | quick hull problem |
C. | path compression |
D. | union-by-rank |
Answer» B. quick hull problem | |
Explanation: quick hull is a method of |
130. | What is the other name for quick hull problem? |
A. | convex hull |
B. | concave hull |
C. | closest pair |
D. | path compression |
Answer» A. convex hull | |
Explanation: the other name for quick hull problem is convex hull problem whereas the closest pair problem is the problem of finding the closest distance between two points. |
131. | How many approaches can be applied to solve quick hull problem? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | 4 |
Answer» B. 2 | |
Explanation: most commonly, two approaches are adopted to solve quick hull problem- brute force approach and divide and conquer approach. |
132. | What is the average case complexity of a quick hull algorithm? |
A. | o(n) |
B. | o(n log n) |
C. | o(n2) |
D. | o(log n) |
Answer» B. o(n log n) | |
Explanation: the average case complexity of quickhull algorithm using divide and conquer approach is mathematically found to be o(n log n). |
133. | What is the worst case complexity of quick hull? |
A. | o(n) |
B. | o(n log n) |
C. | o(n2) |
D. | o(log n) |
Answer» C. o(n2) | |
Explanation: the worst case complexity of quickhull algorithm using divide and conquer approach is mathematically found to be o(n2). |
134. | What does the following diagram depict? |
A. | closest pair |
B. | convex hull |
C. | concave hull |
D. | path compression |
Answer» B. convex hull | |
Explanation: the above diagram is a depiction of convex hull, also known as quick hull, since it encloses n points into a convex polygon. |
135. | Which of the following statement is not related to quickhull algorithm? |
A. | finding points with minimum and maximum coordinates |
B. | dividing the subset of points by a line |
C. | eliminating points within a formed triangle |
D. | finding the shortest distance between two points |
Answer» D. finding the shortest distance between two points | |
Explanation: finding the shortest distance between two points belongs to closest pair algorithm while the rest is quickhull. |
136. | The quick hull algorithm runs faster if the input uses non- extreme points. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: it is proved that the quick hull algorithm runs faster if the input uses non- |
137. | To which type of problems does quick hull belong to? |
A. | numerical problems |
B. | computational geometry |
C. | graph problems |
D. | string problems |
Answer» B. computational geometry | |
Explanation: quick hull problem and closest pair algorithms are some of the examples of computational problems. |
138. | Which of the following algorithms is similar to a quickhull algorithm? |
A. | merge sort |
B. | shell sort |
C. | selection sort |
D. | quick sort |
Answer» D. quick sort | |
Explanation: quickhull algorithm is similar to a quick sort algorithm with respect to the run time average case and worst case efficiencies. |
139. | Who formulated quick hull algorithm? |
A. | eddy |
B. | andrew |
C. | chan |
D. | graham |
Answer» A. eddy | |
Explanation: eddy formulated quick hull algorithm. graham invented graham scan. andrew formulated andrew’s algorithm and chan invented chan’s algorithm. |
140. | The time is taken to find the ‘n’ points that lie in a convex quadrilateral is? |
A. | o(n) |
B. | o(n log n) |
C. | o(n2) |
D. | o(log n) |
Answer» A. o(n) | |
Explanation: the time taken to find the ‘n’ points that lie in a convex quadrilateral is mathematically found to be o(n). |
141. | Chan’s algorithm is used for computing |
A. | closest distance between two points |
B. | convex hull |
C. | area of a polygon |
D. | shortest path between two points |
Answer» B. convex hull | |
Explanation: chan’s algorithm is an output- sensitive algorithm used to compute the convex hull set of n points in a 2d or 3d space. closest pair algorithm is used to compute the closest distance between two points. |
142. | What is the running time of Chan’s algorithm? |
A. | o(log n) |
B. | o(n log n) |
C. | o(n log h) |
D. | o(log h) |
Answer» C. o(n log h) | |
Explanation: the running time of chan’s algorithm is calculated to be o(n log h) where h is the number of vertices of the convex hull. |
143. | Who formulated Chan’s algorithm? |
A. | timothy |
B. | kirkpatrick |
C. | frank nielsen |
D. | seidel |
Answer» A. timothy | |
Explanation: chan’s algorithm was formulated by timothy chan. kirkpatrick and seidel formulated the kirkpatrick-seidel algorithm. frank nielsen developed a paradigm relating to chan’s algorithm. |
144. | The running time of Chan’s algorithm is obtained from combining two algorithms. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: the o(n log h) running time of chan’s algorithm is obtained by combining the running time of graham’s scan [o(n log n)] and jarvis match [o(nh)]. |
145. | Which of the following is called the “ultimate planar convex hull algorithm”? |
A. | chan’s algorithm |
B. | kirkpatrick-seidel algorithm |
C. | gift wrapping algorithm |
D. | jarvis algorithm |
Answer» B. kirkpatrick-seidel algorithm | |
Explanation: kirkpatrick-seidel algorithm is called as the ultimate planar convex hull algorithm. its running time is the same as that of chan’s algorithm (i.e.) o(n log h). |
146. | Which of the following algorithms is the simplest? |
A. | chan’s algorithm |
B. | kirkpatrick-seidel algorithm |
C. | gift wrapping algorithm |
D. | jarvis algorithm |
Answer» A. chan’s algorithm | |
Explanation: chan’s algorithm is very practical for moderate sized problems whereas kirkpatrick-seidel algorithm is not. although, they both have the same running time. gift wrapping algorithm is a non-output sensitive algorithm and has a longer running time. |
147. | What is the running time of Hershberger algorithm? |
A. | o(log n) |
B. | o(n log n) |
C. | o(n log h) |
D. | o(log h) |
Answer» B. o(n log n) | |
Explanation: hershberger’s algorithm is an output sensitive algorithm whose running |
148. | Which of the following statements is not a part of Chan’s algorithm? |
A. | eliminate points not in the hull |
B. | recompute convex hull from scratch |
C. | merge previously calculated convex hull |
D. | reuse convex hull from the previous iteration |
Answer» B. recompute convex hull from scratch | |
Explanation: chan’s algorithm implies that the convex hulls of larger points can be arrived at by merging previously calculated convex hulls. it makes the algorithm simpler instead of recomputing every time from scratch. |
149. | Which of the following factors account more to the cost of Chan’s algorithm? |
A. | computing a single convex hull |
B. | locating points that constitute a hull |
C. | computing convex hull in groups |
D. | merging convex hulls |
Answer» C. computing convex hull in groups | |
Explanation: the majority of the cost of the algorithm lies in the pre-processing (i.e.) computing convex hull in groups. to reduce cost, we reuse convex hulls from previous iterations. |
151. | Which of the following is false in the case of a spanning tree of a graph G? | |
A. | it is tree that spans g | |
B. | it is a subgraph of the g | |
C. | it includes every vertex of the g | |
D. | it can be either cyclic or acyclic | |
Answer» D. it can be either cyclic or acyclic | ||
Explanation: a graph can have many spanning trees. each spanning tree of a graph g is a subgraph of the graph g, and spanning trees include every vertex of the gram. | ||
152. | Every graph has only one minimum spanning tree. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: minimum spanning tree is a spanning tree with the lowest cost among all the spacing trees. sum of all of the edges in the spanning tree is the cost of the spanning tree. there can be many minimum spanning trees for a given graph. |
153. | Consider a complete graph G with 4 vertices. The graph G has spanning trees. |
A. | 15 |
B. | 8 |
C. | 16 |
D. | 13 |
Answer» C. 16 | |
Explanation: a graph can have many spanning trees. and a complete graph with n vertices has n(n-2) spanning trees. so, the complete graph with 4 vertices has 4(4-2) = 16 spanning trees. |
154. | The travelling salesman problem can be solved using |
A. | a spanning tree |
B. | a minimum spanning tree |
C. | bellman – ford algorithm |
D. | dfs traversal |
Answer» B. a minimum spanning tree | |
Explanation: in the travelling salesman problem we have to find the shortest possible route that visits every city exactly once and returns to the starting point for the given a set of cities. so, travelling salesman problem can be solved by contracting the minimum spanning tree. |
155. | Consider the graph M with 3 vertices. Its adjacency matrix is shown below. Which of the following is true? |
A. | graph m has no minimum spanning tree |
B. | graph m has a unique minimum spanning trees of cost 2 |
C. | graph m has 3 distinct minimum spanning trees, each of cost 2 |
D. | graph m has 3 spanning trees of different costs |
Answer» C. graph m has 3 distinct minimum spanning trees, each of cost 2 | |
Explanation: here all non-diagonal elements in the adjacency matrix are 1. so, every vertex is connected every other vertex of the graph. and, so graph m has 3 distinct minimum spanning trees. |
156. | Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false? |
A. | every minimum spanning tree of g must contain cd |
B. | if ab is in a minimum spanning tree, then its removal must disconnect g |
C. | no minimum spanning tree contains ab |
D. | g has a unique minimum spanning tree |
Answer» C. no minimum spanning tree contains ab | |
Explanation: every mst will contain cd as it is smallest edge. so, every minimum spanning tree of g must contain cd is true. and g has a unique minimum spanning tree is also true because the graph has edges with distinct weights. so, no minimum spanning tree contains ab is false. |
157. | If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum cost subgraph. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: a subgraph is a graph formed from a subset of the vertices and edges of the original graph. and the subset of vertices includes all endpoints of the subset of the edges. so, we can say mst of a graph is a subgraph when all weights in the original graph are positive. |
158. | Which of the following is not the algorithm to find the minimum spanning tree of the given graph? |
A. | boruvka’s algorithm |
B. | prim’s algorithm |
C. | kruskal’s algorithm |
D. | bellman–ford algorithm |
Answer» D. bellman–ford algorithm | |
Explanation: the boruvka’s algorithm, prim’s algorithm and kruskal’s algorithm are the algorithms that can be used to find the minimum spanning tree of the given graph. the bellman-ford algorithm is used to find the shortest path from the single source to all other vertices. |
159. | Which of the following is false? |
A. | the spanning trees do not have any cycles |
B. | mst have n – 1 edges if the graph has n edges |
C. | edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the msts of the graph |
D. | removing one edge from the spanning tree will not make the graph disconnected |
Answer» D. removing one edge from the spanning tree will not make the graph disconnected | |
Explanation: every spanning tree has n – 1 edges if the graph has n edges and has no cycles. the mst follows the cut property, edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the msts of the graph. |
160. | Kruskal’s algorithm is used to |
A. | find minimum spanning tree |
B. | find single source shortest path |
C. | find all pair shortest path algorithm |
D. | traverse the graph |
Answer» A. find minimum spanning tree | |
Explanation: the kruskal’s algorithm is used to find the minimum spanning tree of the connected graph. it construct the mst by finding the edge having the least possible weight that connects two trees in the forest. |
161. | Kruskal’s algorithm is a |
A. | divide and conquer algorithm |
B. | dynamic programming algorithm |
C. | greedy algorithm |
D. | approximation algorithm |
Answer» C. greedy algorithm | |
Explanation: kruskal’s algorithm uses a greedy algorithm approach to find the mst of the connected weighted graph. in the greedy method, we attempt to find an optimal solution in stages. |
162. | What is the time complexity of Kruskal’s algorithm? |
A. | o(log v) |
B. | o(e log v) |
C. | o(e2) |
D. | o(v log e) |
Answer» B. o(e log v) | |
Explanation: kruskal’s algorithm involves sorting of the edges, which takes o(e loge) time, where e is a number of edges in graph and v is the number of vertices. after sorting, all edges are iterated and union-find algorithm is applied. union-find algorithm requires o(logv) time. so, overall kruskal’s algorithm requires o(e log v) time. |
163. | Consider the following graph. Using Kruskal’s algorithm, which edge will be selected first? |
A. | gf |
B. | de |
C. | be |
D. | bg |
Answer» C. be | |
Explanation: in krsuskal’s algorithm the edges are selected and added to the spanning tree in increasing order of their weights. |
164. | Which of the following edges form minimum spanning tree on the graph using kruskals algorithm? |
A. | (b-e)(g-e)(e-f)(d-f) |
B. | (b-e)(g-e)(e-f)(b-g)(d-f) |
C. | (b-e)(g-e)(e-f)(d-e) |
D. | (b-e)(g-e)(e-f)(d-f)(d-g) |
Answer» A. (b-e)(g-e)(e-f)(d-f) | |
Explanation: using krushkal’s algorithm on the given graph, the generated minimum spanning tree is shown below. |
165. | Which of the following is false about the Kruskal’s algorithm? |
A. | it is a greedy algorithm |
B. | it constructs mst by selecting edges in increasing order of their weights |
C. | it can accept cycles in the mst |
D. | it uses union-find data structure |
Answer» C. it can accept cycles in the mst | |
Explanation: kruskal’s algorithm is a greedy algorithm to construct the mst of the given graph. it constructs the mst by selecting edges in increasing order of their weights and rejects an edge if it may form the cycle. so, using kruskal’s algorithm is never formed. |
166. | Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: prim’s algorithm outperforms the kruskal’s algorithm in case of the dense graphs. it is significantly faster if graph has more edges than the kruskal’s algorithm. |
167. | Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure. |
A. | s1 is true but s2 is false |
B. | both s1 and s2 are false |
C. | both s1 and s2 are true |
D. | s2 is true but s1 is false |
Answer» D. s2 is true but s1 is false | |
Explanation: in kruskal’s algorithm, the disjoint-set data structure efficiently identifies the components containing a vertex and adds the new edges. and kruskal’s algorithm always finds the mst for the connected graph. |
168. | Which of the following is true? |
A. | prim’s algorithm initialises with a vertex |
B. | prim’s algorithm initialises with a edge |
C. | prim’s algorithm initialises with a vertex which has smallest edge |
D. | prim’s algorithm initialises with a forest |
Answer» A. prim’s algorithm initialises with a vertex | |
Explanation: steps in prim’s algorithm: (i) select any vertex of given graph and add it to mst (ii) add the edge of minimum weight from a vertex not in mst to the vertex in mst; (iii) it mst is complete the stop, otherwise go to step (ii). |
169. | Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used? |
A. | o(log v) |
B. | o(v2) |
C. | o(e2) |
D. | o(v log e) |
Answer» B. o(v2) | |
Explanation: use of adjacency matrix provides the simple implementation of the prim’s algorithm. in prim’s algorithm, we need to search for the edge with a minimum for that vertex. so, worst case time complexity will be o(v2), where v is the number of vertices. |
170. | Prim’s algorithm is a |
A. | divide and conquer algorithm |
B. | greedy algorithm |
C. | dynamic programming |
D. | approximation algorithm |
Answer» B. greedy algorithm | |
Explanation: prim’s algorithm uses a greedy algorithm approach to find the mst of the connected weighted graph. in greedy method, we attempt to find an optimal solution in stages. |
171. | Prim’s algorithm resembles Dijkstra’s algorithm. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: in prim’s algorithm, the mst is constructed starting from a single vertex and adding in new edges to the mst that link the partial tree to a new vertex outside of the mst. and dijkstra’s algorithm also rely on the similar approach of finding the next closest vertex. so, prim’s algorithm |
172. | Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: prim’s algorithm and kruskal’s algorithm perform equally in case of the sparse graphs. but kruskal’s algorithm is simpler and easy to work with. so, it is best suited for sparse graphs. |
173. | Prim’s algorithm can be efficiently implemented using for graphs with greater density. |
A. | d-ary heap |
B. | linear search |
C. | fibonacci heap |
D. | binary search |
Answer» A. d-ary heap | |
Explanation: in prim’s algorithm, we add the minimum weight edge for the chosen vertex which requires searching on the array of weights. this searching can be efficiently implemented using binary heap for dense graphs. and for graphs with greater density, prim’s algorithm can be made to run in linear time using d-ary heap(generalization of binary heap). |
174. | Which of the following is false about Prim’s algorithm? |
A. | it is a greedy algorithm |
B. | it constructs mst by selecting edges in increasing order of their weights |
C. | it never accepts cycles in the mst |
D. | it can be implemented using the fibonacci heap |
Answer» B. it constructs mst by selecting edges in increasing order of their weights | |
Explanation: prim’s algorithm can be implemented using fibonacci heap and it never accepts cycles. and prim’s algorithm follows greedy approach. prim’s algorithms |
176. | How many priority queue operations are involved in Dijkstra’s Algorithm? | |
A. | 1 | |
B. | 3 | |
C. | 2 | |
D. | 4 | |
Answer» B. 3 | ||
Explanation: the number of priority queue operations involved is 3. they are insert, extract-min and decrease key. | ||
177. | How many times the insert and extract min operations are invoked per vertex? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | 0 |
Answer» A. 1 | |
Explanation: insert and extract min operations are invoked only once per vertex because each vertex is added only once to the set and each edge in the adjacency list is examined only once during the course of algorithm. |
178. | The maximum number of times the decrease key operation performed in Dijkstra’s algorithm will be equal to |
A. | total number of vertices |
B. | total number of edges |
C. | number of vertices – 1 |
D. | number of edges – 1 |
Answer» B. total number of edges | |
Explanation: if the total number of edges in all adjacency list is e, then there will be a total of e number of iterations, hence there will be a total of at most e decrease key operations. |
179. | What is running time of Dijkstra’s algorithm using Binary min- heap method? |
A. | o(v) |
B. | o(vlogv) |
C. | o(e) |
D. | o(elogv) |
Answer» D. o(elogv) | |
Explanation: time required to build a binary min heap is o(v). each decrease key operation takes o(logv) and there are still at most e such operations. hence total running time is o(elogv). |
180. | The running time of Bellmann Ford algorithm is lower than that of Dijkstra’s Algorithm. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: the number of iterations involved in bellmann ford algorithm is more than that of dijkstra’s algorithm. |
181. | Dijkstra’s Algorithm run on a weighted, directed graph G={V,E} with non-negative weight function w and source s, terminates with d[u]=delta(s,u) for all vertices u in V. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: the equality d[u]=delta(s,u) holds good when vertex u is added to set s and this equality is maintained thereafter by the upper bound property. |
182. | Dijkstra’s Algorithm is the prime example for |
A. | greedy algorithm |
B. | branch and bound |
C. | back tracking |
D. | dynamic programming |
Answer» A. greedy algorithm | |
Explanation: dijkstra’s algorithm is the prime example for greedy algorithms because greedy algorithms generally solve a problem in stages by doing what appears to be the best thing at each stage. |
183. | Bellmann ford algorithm provides solution for problems. |
A. | all pair shortest path |
B. | sorting |
C. | network flow |
D. | single source shortest path |
Answer» D. single source shortest path | |
Explanation: bellmann ford algorithm is used for finding solutions for single source shortest path problems. if the graph has no negative cycles that are reachable from the source then the algorithm produces the shortest paths and their weights. |
184. | Bellmann Ford algorithm is used to indicate whether the graph has negative weight cycles or not. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: bellmann ford algorithm returns true if the graph does not have any negative weight cycles and returns false when the graph has negative weight cycles. |
185. | How many solution/solutions are available for a graph having negative weight cycle? |
A. | one solution |
B. | two solutions |
C. | no solution |
D. | infinite solutions |
Answer» C. no solution | |
Explanation: if the graph has any negative weight cycle then the algorithm indicates that no solution exists for that graph. |
186. | What is the running time of Bellmann Ford Algorithm? |
A. | o(v) |
B. | o(v2) |
C. | o(elogv) |
D. | o(ve) |
Answer» D. o(ve) | |
Explanation: bellmann ford algorithm runs in time o(ve), since the initialization takes o(v) for each of v-1 passes and the for loop in the algorithm takes o(e) time. hence the total time taken by the algorithm is o(ve). |
187. | How many times the for loop in the Bellmann Ford Algorithm gets executed? |
A. | v times |
B. | v-1 |
C. | e |
D. | e-1 |
Answer» B. v-1 | |
Explanation: the for loop in the bellmann ford algorithm gets executed for v-1 times. after making v-1 passes, the algorithm checks for a negative weight cycle and returns appropriate boolean value. |
188. | Dijikstra’s Algorithm is more efficient than Bellmann Ford Algorithm. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: the running time of bellmann ford algorithm is o(ve) whereas dijikstra’s algorithm has running time of only o(v2). |
189. | What is the basic principle behind Bellmann Ford Algorithm? |
A. | interpolation |
B. | extrapolation |
C. | regression |
D. | relaxation |
Answer» D. relaxation | |
Explanation: relaxation methods which are also called as iterative methods in which an approximation to the correct distance is replaced progressively by more accurate values till an optimum solution is found. |
190. | Bellmann Ford Algorithm can be applied for |
A. | undirected and weighted graphs |
B. | undirected and unweighted graphs |
C. | directed and weighted graphs |
D. | all directed graphs |
Answer» C. directed and weighted graphs | |
Explanation: bellmann ford algorithm can be applied for all directed and weighted graphs. the weight function in the graph may either be positive or negative. |
191. | Bellmann Ford algorithm was first proposed by |
A. | richard bellmann |
B. | alfonso shimbe |
C. | lester ford jr |
D. | edward f. moore |
Answer» B. alfonso shimbe | |
Explanation: alfonso shimbe proposed bellmann ford algorithm in the year 1955. later it was published by richard bellmann in 1957 and lester ford jr in the year 1956. hence it is called bellmann ford algorithm. |
192. | Bellmann Ford Algorithm is an example for |
A. | dynamic programming |
B. | greedy algorithms |
C. | linear programming |
D. | branch and bound |
Answer» A. dynamic programming | |
Explanation: in bellmann ford algorithm the shortest paths are calculated in bottom up manner which is similar to other dynamic programming problems. |
193. | A graph is said to have a negative weight cycle when? |
A. | the graph has 1 negative weighted edge |
B. | the graph has a cycle |
C. | the total weight of the graph is negative |
D. | the graph has 1 or more negative weighted edges |
Answer» C. the total weight of the graph is negative | |
Explanation: when the total weight of the graph sums up to a negative number then the graph is said to have a negative weight cycle. bellmann ford algorithm provides no solution for such graphs. |
194. | Floyd Warshall’s Algorithm is used for solving |
A. | all pair shortest path problems |
B. | single source shortest path problems |
C. | network flow problems |
D. | sorting problems |
Answer» A. all pair shortest path problems | |
Explanation: floyd warshall’s algorithm is used for solving all pair shortest path problems. it means the algorithm is used for finding the shortest paths between all pairs of vertices in a graph. |
195. | Floyd Warshall’s Algorithm can be applied on |
A. | undirected and unweighted graphs |
B. | undirected graphs |
C. | directed graphs |
D. | acyclic graphs |
Answer» C. directed graphs | |
Explanation: floyd warshall algorithm can be applied in directed graphs. from a given directed graph, an adjacency matrix is framed and then all pair shortest path is computed by the floyd warshall algorithm. |
196. | What is the running time of the Floyd Warshall Algorithm? |
A. | big-oh(v) |
B. | theta(v2) |
C. | big-oh(ve) |
D. | theta(v3) |
Answer» D. theta(v3) | |
Explanation: the running time of the floyd warshall algorithm is determined by the triply nested for loops. since each execution of the for loop takes o(1) time, the algorithm runs in time theta(v3). |
197. | What approach is being followed in Floyd Warshall Algorithm? |
A. | greedy technique |
B. | dynamic programming |
C. | linear programming |
D. | backtracking |
Answer» B. dynamic programming | |
Explanation: floyd warshall algorithm follows dynamic programming approach because the all pair shortest paths are computed in bottom up manner. |
198. | Floyd Warshall Algorithm can be used for finding |
A. | single source shortest path |
B. | topological sort |
C. | minimum spanning tree |
D. | transitive closure |
Answer» D. transitive closure | |
Explanation: one of the ways to compute the transitive closure of a graph in theta(n3) time is to assign a weight of 1 to each edge of e and then run the floyd warshall algorithm. |
199. | What procedure is being followed in Floyd Warshall Algorithm? |
A. | top down |
B. | bottom up |
C. | big bang |
D. | sandwich |
Answer» B. bottom up | |
Explanation: bottom up procedure is being used to compute the values of the matrix elements dij(k). the input is an n x n matrix. |
201. | Who proposed the modern formulation of Floyd-Warshall Algorithm as three nested loops? |
A. | robert floyd |
B. | stephen warshall |
C. | bernard roy |
D. | peter ingerman |
Answer» D. peter ingerman | |
Explanation: the modern formulation of floyd-warshall algorithm as three nested for- loops was proposed by peter ingerman in the year 1962. |
202. | What happens when the value of k is 0 in the Floyd Warshall Algorithm? |
A. | 1 intermediate vertex |
B. | 0 intermediate vertex |
C. | n intermediate vertices |
D. | n-1 intermediate vertices |
Answer» B. 0 intermediate vertex | |
Explanation: when k=0, a path from vertex i to vertex j has no intermediate vertices at all. such a path has at most one edge and hence dij(0) = wij. |
203. | Using logical operator’s instead arithmetic operators saves time and space. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: in computers, logical operations on single bit values execute faster than arithmetic operations on integer words of data. |
204. | The time taken to compute the transitive closure of a graph is Theta(n2). |
A. | true |
B. | false |
Answer» B. false | |
Explanation: the time taken to compute the transitive closure of a graph is theta(n3). |
205. | If a problem can be broken into subproblems which are reused several times, the problem possesses property. |
A. | overlapping subproblems |
B. | optimal substructure |
C. | memoization |
D. | greedy |
Answer» A. overlapping subproblems | |
Explanation: overlapping subproblems is the property in which value of a subproblem is used several times. |
206. | When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don’t take advantage of overlapping subproblems. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: dynamic programming calculates the value of a subproblem only once, while other methods that don’t take advantage of the overlapping subproblems property may calculate the value of the same subproblem several times. so, dynamic programming saves the time of recalculation and takes far less time as compared to other methods that don’t take advantage of the overlapping subproblems property. |
207. | A greedy algorithm can be used to solve all the dynamic programming problems. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: a greedy algorithm gives optimal solution for all subproblems, but when these locally optimal solutions are combined it may not result into a globally optimal solution. hence, a greedy algorithm cannot be used to solve all the dynamic programming problems. |
208. | In dynamic programming, the technique of storing the previously calculated values is called |
A. | saving value property |
B. | storing value property |
C. | memoization |
D. | mapping |
Answer» C. memoization | |
Explanation: memoization is the technique |
209. | When a top-down approach of dynamic programming is applied to a problem, it usually |
A. | decreases both, the time complexity and the space complexity |
B. | decreases the time complexity and increases the space complexity |
C. | increases the time complexity and decreases the space complexity |
D. | increases both, the time complexity and the space complexity |
Answer» B. decreases the time complexity and increases the space complexity | |
Explanation: the top-down approach uses the memoization technique which stores the previously calculated values. due to this, the time complexity is decreased but the space complexity is increased. |
210. | Which of the following problems is NOT solved using dynamic programming? |
A. | 0/1 knapsack problem |
B. | matrix chain multiplication problem |
C. | edit distance problem |
D. | fractional knapsack problem |
Answer» D. fractional knapsack problem | |
Explanation: the fractional knapsack problem is solved using a greedy algorithm. |
211. | Which of the following problems should be solved using dynamic programming? |
A. | mergesort |
B. | binary search |
C. | longest common subsequence |
D. | quicksort |
Answer» C. longest common subsequence | |
Explanation: the longest common subsequence problem has both, optimal substructure and overlapping subproblems. hence, dynamic programming should be used the solve this problem. |
212. | What is the time complexity of the recursive implementation used to find the nth fibonacci term? |
A. | o(1) |
B. | o(n2) |
C. | o(n!) |
D. | exponential |
Answer» D. exponential | |
Explanation: the recurrence relation is given by fibo(n) = fibo(n – 1) + fibo(n – 2). so, the time complexity is given by: |
213. | What is the space complexity of the recursive implementation used to find the nth fibonacci term? |
A. | o(1) |
B. | o(n) |
C. | o(n2) |
D. | o(n3) |
Answer» A. o(1) | |
Explanation: the recursive implementation doesn’t store any values and calculates every value from scratch. so, the space complexity is o(1). |
214. | return fibo_terms[n] |
A. | o(1) |
B. | o(n) |
C. | o(n2) |
D. | exponential |
Answer» B. o(n) | |
Explanation: to calculate the nth term, the for loop runs (n – 1) times and each time a for loop is run, it takes a constant time. |
215. | You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using |
A. | greedy algorithm |
B. | dynamic programming |
C. | divide and conquer |
D. | backtracking |
Answer» B. dynamic programming | |
Explanation: the coin change problem has overlapping subproblems(same subproblems are solved multiple times) and optimal substructure(the solution to the problem can |
216. | Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer? |
A. | 14 |
B. | 10 |
C. | 6 |
D. | 100 |
Answer» D. 100 | |
Explanation: using the greedy algorithm, three coins {4,1,1} will be selected to make a sum of 6. but, the optimal answer is two coins {3,3}. similarly, four coins {4,4,1,1} will be selected to make a sum of 10. but, the optimal answer is three coins {4,3,3}. also, five coins {4,4,4,1,1} will be selected to make a sum of 14. but, the optimal answer is four coins {4,4,3,3}. for a sum of 100, twenty-five coins {all 4’s} will be selected and the optimal answer is also twenty-five coins {all 4’s}. |
217. | You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem? |
A. | o(n) |
B. | o(s) |
C. | o(n2) |
D. | o(s*n) |
Answer» D. o(s*n) | |
Explanation: the time complexity is o(s*n). |
218. | You are given infinite coins of denominations 1, 3, 4. What is the minimum number of coins required to achieve a sum of 7? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | 4 |
Answer» B. 2 | |
Explanation: a sum of 7 can be achieved by using a minimum of two coins {3,4}. |
219. | What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum? |
A. | o(n) |
B. | o(1) |
C. | o(n!) |
D. | o(n2) |
Answer» B. o(1) | |
Explanation: the divide and conquer algorithm uses a constant space. so, the space complexity is o(1). |
220. | Kadane’s algorithm is used to find |
A. | longest increasing subsequence |
B. | longest palindrome subsequence |
C. | maximum sub-array sum |
D. | longest decreasing subsequence |
Answer» C. maximum sub-array sum | |
Explanation: kadane’s algorithm is used to find the maximum sub-array sum for a given array. |
221. | Kadane’s algorithm uses which of the following techniques? |
A. | divide and conquer |
B. | dynamic programming |
C. | recursion |
D. | greedy algorithm |
Answer» B. dynamic programming | |
Explanation: kadane’s algorithm uses dynamic programming. |
222. | For which of the following inputs would Kadane’s algorithm produce a WRONG output? |
A. | {1,0,-1} |
B. | {-1,-2,-3} |
C. | {1,2,3} |
D. | {0,0,0} |
Answer» B. {-1,-2,-3} | |
Explanation: kadane’s algorithm doesn’t work for all negative numbers. so, the answer is {-1,-2,-3}. |
223. | What is the time complexity of Kadane’s algorithm? |
A. | o(1) |
B. | o(n) |
C. | o(n2) |
D. | o(5) |
Answer» B. o(n) | |
Explanation: the time complexity of kadane’s algorithm is o(n) because there is only one for loop which scans the entire array exactly once. |
224. | What is the space complexity of Kadane’s algorithm? |
A. | o(1) |
B. | o(n) |
C. | o(n2) |
D. | none of the mentioned |
Answer» A. o(1) | |
Explanation: kadane’s algorithm uses a constant space. so, the space complexity is |
226. | For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: for a given sequence, it is possible that there is more than one subsequence with the longest length. |
227. | Given a rod of length n and the selling prices of all pieces smaller than equal to n, find the most beneficial way of cutting the rod into smaller pieces. This problem is called the rod cutting problem. Which of these methods can be used to solve the rod cutting problem? |
A. | brute force |
B. | dynamic programming |
C. | recursion |
D. | brute force, dynamic programming and recursion |
Answer» D. brute force, dynamic programming and recursion | |
Explanation: brute force, dynamic programming and recursion can be used to solve the rod cutting problem. |
228. | Consider the brute force implementation of the rod cutting problem in which all the possible cuts are found and the maximum value is calculated. What is the time complexity of this brute force implementation? |
A. | o(n2) |
B. | o(n3) |
C. | o(nlogn) |
D. | o(2n) |
Answer» D. o(2n) | |
Explanation: the brute force implementation finds all the possible cuts. this takes o(2n) time. |
229. | For every rod cutting problem there will be a unique set of pieces that give the maximum price. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: consider a rod of length 3. the prices are {2,3,6} for lengths {1,2,3} respectively. the pieces {1,1,1} and {3} both give the maximum value of 6. |
230. | For a given array, there can be multiple ways to reach the end of the array using minimum number of jumps. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: consider the array {1,2,3,4,5}. it is possible to reach the end in the following ways: {1 -> 2 -> 3 -> 5} or {1 -> 2 -> 4 -> 5}. |
231. | For any array, given that at most one element is non-zero, it is ALWAYS possible to reach the end of the array using minimum jumps. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: consider the array {1,0,2,3,4}. |
232. | What is the space complexity of the following dynamic programming implementation used to find the minimum number of jumps? |
A. | o(1) |
B. | o(n) |
C. | o(n2) |
D. | o(5) |
Answer» B. o(n) | |
Explanation: the space complexity of the above dynamic programming implementation is o(n). |
233. | The Knapsack problem is an example of |
A. | greedy algorithm |
B. | 2d dynamic programming |
C. | 1d dynamic programming |
D. | divide and conquer |
Answer» B. 2d dynamic programming | |
Explanation: knapsack problem is an example of 2d dynamic programming. |
234. | Which of the following problems is equivalent to the 0-1 Knapsack problem? |
A. | you are given a bag that can carry a maximum weight of w. you are given n items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. you can break the items into smaller pieces. choose the items in such a way that you get the maximum value |
B. | you are studying for an exam and you have to study n questions. the questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. you can study for a maximum of t hours. you can either study a question or leave it. choose the questions in such a way that your score is maximized |
C. | you are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum s. you have to find the minimum number of coins required to get the sum s |
D. | you are given a suitcase that can carry a maximum weight of 15kg. you are given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}. you can break the items into smaller pieces. choose the items in such a way that you get the maximum value |
Answer» B. you are studying for an exam and you have to study n questions. the questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. you can study for a maximum of t hours. you can either study a question or leave it. choose the questions in such a way that your score is maximized | |
Explanation: in this case, questions are used instead of items. each question has a score which is same as each item having a value. |
235. | The 0-1 Knapsack problem can be solved using Greedy algorithm. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: the knapsack problem cannot be solved using the greedy algorithm. |
236. | Which of the following methods can be used to solve the matrix chain multiplication problem? |
A. | dynamic programming |
B. | brute force |
C. | recursion |
D. | dynamic programming, brute force, recursion |
Answer» D. dynamic programming, brute force, recursion | |
Explanation: dynamic programming, brute force, recursion methods can be used to solve the matrix chain multiplication problem. |
237. | Consider the matrices P, Q and R which are 10 x 20, 20 x 30 and 30 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the three matrices? |
A. | 18000 |
B. | 12000 |
C. | 24000 |
D. | 32000 |
Answer» A. 18000 | |
Explanation: the minimum number of multiplications are 18000. this is the case when the matrices are parenthesized as (p*q)*r. |
238. | Consider the brute force implementation in which we find all the possible ways of multiplying the given set of n matrices. What is the time complexity of this implementation? |
A. | o(n!) |
B. | o(n3) |
C. | o(n2) |
D. | exponential |
Answer» D. exponential | |
Explanation: the time complexity of finding all the possible ways of multiplying a set of n matrices is given by (n-1)th catalan number which is exponential. |
239. | Which of the following methods can be used to solve the longest common subsequence problem? |
A. | recursion |
B. | dynamic programming |
C. | both recursion and dynamic programming |
D. | greedy algorithm |
Answer» C. both recursion and dynamic programming | |
Explanation: both recursion and dynamic programming can be used to solve the longest subsequence problem. |
240. | Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence? |
A. | 9 |
B. | 8 |
C. | 7 |
D. | 6 |
Answer» C. 7 | |
Explanation: the longest common subsequence is “prtpqrs” and its length is 7. |
241. | Which of the following problems can be solved using the longest subsequence problem? |
A. | longest increasing subsequence |
B. | longest palindromic subsequence |
C. | longest bitonic subsequence |
D. | longest decreasing subsequence |
Answer» B. longest palindromic subsequence | |
Explanation: to find the longest palindromic subsequence in a given string, reverse the given string and then find the longest common subsequence in the given string and the reversed string. |
242. | Longest common subsequence is an example of |
A. | greedy algorithm |
B. | 2d dynamic programming |
C. | 1d dynamic programming |
D. | divide and conquer |
Answer» B. 2d dynamic programming | |
Explanation: longest common subsequence is an example of 2d dynamic programming. |
243. | What is the time complexity of the brute force algorithm used to find the longest common subsequence? |
A. | o(n) |
B. | o(n2) |
C. | o(n3) |
D. | o(2n) |
Answer» D. o(2n) | |
Explanation: the time complexity of the brute force algorithm used to find the longest common subsequence is o(2n). |
244. | Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and “cbhgrsfnmq” ? |
A. | hgmq |
B. | cfnq |
C. | bfmq |
D. | fgmna |
Answer» D. fgmna | |
Explanation: the length of the longest common subsequence is 4. but ‘fgmna’ is not the longest common subsequence as its length is 5. |
245. | Which of the following methods can be used to solve the longest palindromic subsequence problem? |
A. | dynamic programming |
B. | recursion |
C. | brute force |
D. | dynamic programming, recursion, brute force |
Answer» D. dynamic programming, recursion, brute force | |
Explanation: dynamic programming, recursion, brute force can be used to solve the longest palindromic subsequence problem. |
246. | Which of the following is not a palindromic subsequence of the string “ababcdabba”? |
A. | abcba |
B. | abba |
C. | abbbba |
D. | adba |
Answer» D. adba | |
Explanation: ‘adba’ is not a palindromic sequence. |
247. | For which of the following, the length of the string is not equal to the length of the longest palindromic subsequence? |
A. | a string that is a palindrome |
B. | a string of length one |
C. | a string that has all the same letters(e.g. aaaaaa) |
D. | some strings of length two |
Answer» D. some strings of length two | |
Explanation: a string of length 2 for eg: ab is not a palindrome. |
248. | What is the length of the longest palindromic subsequence for the string “ababcdabba”? |
A. | 6 |
B. | 7 |
C. | 8 |
D. | 9 |
Answer» B. 7 | |
Explanation: the longest palindromic subsequence is “abbabba” and its length is 7. |
249. | What is the time complexity of the brute force algorithm used to find the length of the longest palindromic subsequence? |
A. | o(1) |
B. | o(2n) |
C. | o(n) |
D. | o(n2) |
Answer» B. o(2n) | |
Explanation: in the brute force algorithm, all the subsequences are found and the length of the longest palindromic subsequence is calculated. this takes exponential time. |
251. | Longest palindromic subsequence is an example of |
A. | greedy algorithm |
B. | 2d dynamic programming |
C. | 1d dynamic programming |
D. | divide and conquer |
Answer» B. 2d dynamic programming | |
Explanation: longest palindromic subsequence is an example of 2d dynamic programming. |
252. | Which of the following methods can be used to solve the edit distance problem? |
A. | recursion |
B. | dynamic programming |
C. | both dynamic programming and recursion |
D. | greedy algorithm |
Answer» C. both dynamic programming and recursion | |
Explanation: both dynamic programming and recursion can be used to solve the edit distance problem. |
253. | The edit distance satisfies the axioms of a metric when the costs are non-negative. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: d(s,s) = 0, since each string can be transformed into itself without any change. d(s1, s2) > 0 when s1 != s2, since the transformation would require at least one operation. |
254. | Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: consider the strings “abcd” and “efghi”. the string “efghi” can be converted to “abcd” by deleting “i” and converting “efgh” to “abcd”. the cost of transformation is 5, which is equal to the length of the larger string. |
255. | Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings? |
A. | 3 |
B. | 4 |
C. | 5 |
D. | 6 |
Answer» B. 4 | |
Explanation: “monday” can be converted to “tuesday” by replacing “m” with “t”, “o” with “u”, “n” with “e” and inserting “s” at the appropriate position. so, the edit distance is 4. |
256. | Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings? |
A. | 0 |
B. | 4 |
C. | 2 |
D. | 3 |
Answer» B. 4 | |
Explanation: the empty string can be transformed into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate positions. thus, the edit distance is 4. |
257. | What is the time complexity of the Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings? |
A. | o(1) |
B. | o(n+m) |
C. | o(mn) |
D. | o(nlogm) |
Answer» C. o(mn) | |
Explanation: the time complexity of the wagner–fischer algorithm is o(mn). |
258. | Which of the following is NOT a Catalan number? |
A. | 1 |
B. | 5 |
C. | 14 |
D. | 43 |
Answer» D. 43 | |
Explanation: catalan numbers are given by: (2n!)/((n+1)!n!). |
259. | Which of the following methods can be used to find the nth Catalan number? |
A. | recursion |
B. | binomial coefficients |
C. | dynamic programming |
D. | recursion, binomial coefficients, dynamic programming |
Answer» D. recursion, binomial coefficients, dynamic programming | |
Explanation: all of the mentioned methods can be used to find the nth catalan number. |
260. | Which of the following implementations of Catalan numbers has the smallest time complexity? |
A. | dynamic programming |
B. | binomial coefficients |
C. | recursion |
D. | all have equal time complexity |
Answer» B. binomial coefficients | |
Explanation: The time complexities are as follows: Dynamic programming: O(n2) Recursion: Exponential Binomial coefficients: O(n). |
261. | Which of the following methods can be used to solve the assembly line scheduling problem? |
A. | recursion |
B. | brute force |
C. | dynamic programming |
D. | all of the mentioned |
Answer» D. all of the mentioned | |
Explanation: all of the above mentioned methods can be used to solve the assembly line scheduling problem. |
262. | What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem? |
A. | o(1) |
B. | o(n) |
C. | o(n2) |
D. | o(2n) |
Answer» D. o(2n) | |
Explanation: in the brute force algorithm, all the possible ways are calculated which are of the order of 2n. |
263. | In the dynamic programming implementation of the assembly line scheduling problem, how many lookup tables are required? |
A. | 0 |
B. | 1 |
C. | 2 |
D. | 3 |
Answer» C. 2 | |
Explanation: in the dynamic programming implementation of the assembly line scheduling problem, 2 lookup tables are required one for storing the minimum time and the other for storing the assembly line number. |
264. | What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem? |
A. | o(1) |
B. | o(n) |
C. | o(n2) |
D. | o(n3) |
Answer» B. o(n) | |
Explanation: the time complexity of the above dynamic programming implementation of the assembly line scheduling problem is o(n). |
265. | Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem? |
A. | greedy algorithm |
B. | recursion |
C. | dynamic programming |
D. | both recursion and dynamic programming |
Answer» D. both recursion and dynamic programming | |
Explanation: dynamic programming and recursion can be used to solve the problem. |
266. | In which of the following cases the minimum no of insertions to form palindrome is maximum? |
A. | string of length one |
B. | string with all same characters |
C. | palindromic string |
D. | non palindromic string |
Answer» D. non palindromic string | |
Explanation: in string of length one, string with all same characters and a palindromic string the no of insertions is zero since the strings are already palindromes. to convert a non-palindromic string to a palindromic string, the minimum length of string to be added is 1 which is greater than all the other above cases. hence the minimum no of insertions to form palindrome is maximum in non-palindromic strings. |
267. | In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string. |
A. | true |
B. | false |
C. | answer: b |
D. | explanation: in the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to length of the string minus one. for example, consider the string “abc”. the string can be converted to “abcba” by inserting “a” and “b”. the number of insertions is two, which is equal to length minus one. |
Answer» B. false | |
Explanation: the string can be converted to “efgfe” by inserting “f” or to “egfge” by inserting “g”. thus, only one insertion is required. |
268. | Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome? |
A. | 0 |
B. | 1 |
C. | 2 |
D. | 3 |
Answer» A. 0 | |
Explanation: the given string is already a palindrome. so, no insertions are required. |
269. | Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem? |
A. | minimum number of jumps problem |
B. | longest common subsequence problem |
C. | coin change problem |
D. | knapsack problems |
Answer» B. longest common subsequence problem | |
Explanation: a variation of longest common subsequence can be used to solve the minimum number of insertions to form a palindrome problem. |
270. | Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem? |
A. | brute force |
B. | recursion |
C. | dynamic programming |
D. | brute force, recursion, dynamic programming |
Answer» D. brute force, recursion, dynamic programming | |
Explanation: brute force, recursion and dynamic programming can be used to find the submatrix that has the maximum sum. |
271. | In which of the following cases, the maximum sum rectangle is the 2D matrix itself? |
A. | when all the elements are negative |
B. | when all the elements are positive |
C. | when some elements are positive and some negative |
D. | when diagonal elements are positive and rest are negative |
Answer» A. when all the elements are negative | |
Explanation: when all the elements of a matrix are positive, the maximum sum rectangle is the 2d matrix itself. |
272. | Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle? |
A. | 3 |
B. | 6 |
C. | 12 |
D. | 18 |
Answer» C. 12 | |
Explanation: since all the elements of the 2×3 matrix are positive, the maximum sum rectangle is the matrix itself and the sum of elements is 12. |
273. | Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle? |
A. | 0 |
B. | -1 |
C. | -7 |
D. | -12 |
Answer» B. -1 | |
Explanation: since all the elements of the 2×2 matrix are negative, the maximum sum rectangle is {-1}, a 1×1 matrix containing the largest element. the sum of elements of the maximum sum rectangle is -1. |
274. | The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm? |
A. | hirschberg’s algorithm |
B. | needleman-wunsch algorithm |
C. | kadane’s algorithm |
D. | wagner fischer algorithm |
Answer» C. kadane’s algorithm | |
Explanation: the dynamic programming implementation of the maximum sum rectangle problem uses kadane’s algorithm. |
276. | In which of the following cases, it is not possible to have two subsets with equal sum? |
A. | when the number of elements is odd |
B. | when the number of elements is even |
C. | when the sum of elements is odd |
D. | when the sum of elements is even |
Answer» C. when the sum of elements is odd | |
Explanation: when the sum of all the elements is odd, it is not possible to have two subsets with equal sum. |
277. | What is the time complexity of the brute force algorithm used to solve the balanced partition problem? |
A. | o(1) |
B. | o(n) |
C. | o(n2) |
D. | o(2n) |
Answer» D. o(2n) | |
Explanation: in the brute force implementation, all the possible subsets will be formed. this takes exponential time. |
278. | What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}? |
A. | 16 |
B. | 32 |
C. | 0 |
D. | 64 |
Answer» A. 16 | |
Explanation: the sum of all the elements of the array is 32. so, the sum of all the elements of each partition should be 16. |
279. | You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice throw problem. Which of the following methods can be used to solve the dice throw problem? |
A. | brute force |
B. | recursion |
C. | dynamic programming |
D. | brute force, recursion and dynamic programming |
Answer» D. brute force, recursion and dynamic programming | |
Explanation: brute force, recursion and dynamic programming can be used to solve the dice throw problem. |
280. | You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together? |
A. | n*n*n…f times |
B. | f*f*f…n times |
C. | n*n*n…n times |
D. | f*f*f…f times |
Answer» B. f*f*f…n times | |
Explanation: each die can take f values and there are n dice. so, the total number of permutations is f*f*f…n times. |
281. | You have 3 dice each having 6 faces. What is the number of permutations that can be obtained when you roll the 3 dice together? |
A. | 27 |
B. | 36 |
C. | 216 |
D. | 81 |
Answer» C. 216 | |
Explanation: the total number of permutations that can be obtained is 6 * 6 * 6 |
282. | You have 2 dice each of them having 6 faces numbered from 1 to 6. What is the number of ways in which a sum of 11 can be achieved? |
A. | 0 |
B. | 1 |
C. | 2 |
D. | 3 |
Answer» C. 2 | |
Explanation: the sum of 11 can be achieved when the dice show {6, 5} or {5, 6}. |
283. | There are n dice with f faces. The faces are numbered from 1 to f. What is the minimum possible sum that can be obtained when the n dice are rolled together? |
A. | 1 |
B. | f |
C. | n |
D. | n*f |
Answer» C. n | |
Explanation: the sum will be minimum when all the faces show a value 1. the sum in this case will be n. |
284. | There are n dice with f faces. The faces are numbered from 1 to f. What is the maximum possible sum that can be obtained when the n dice are rolled together? |
A. | 1 |
B. | f*f |
C. | n*n |
D. | n*f |
Answer» D. n*f | |
Explanation: the sum will be maximum when all the faces show a value f. the sum in this case will be n*f. |
285. | There are 10 dice having 5 faces. The faces are numbered from 1 to 5. What is the number of ways in which a sum of 4 can be achieved? |
A. | 0 |
B. | 2 |
C. | 4 |
D. | 8 |
Answer» A. 0 | |
Explanation: since there are 10 dice and the minimum value each die can take is 1, the minimum possible sum is 10. hence, a sum of 4 cannot be achieved. |
286. | Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)? |
A. | 0 |
B. | 1 |
C. | 2 |
D. | 3 |
Answer» C. 2 | |
Explanation: the expression can be parenthesized as (t & f) ∧ t or t & (f ∧ t), so that the output is t. |
287. | Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms? |
A. | n factorial |
B. | n square |
C. | n cube |
D. | nth catalan number |
Answer» D. nth catalan number | |
Explanation: the nth catalan number gives |
288. | What is the maximum number of ways in which a boolean expression with n + 1 terms can be parenthesized, such that the output is true? |
A. | nth catalan number |
B. | n factorial |
C. | n cube |
D. | n square |
Answer» A. nth catalan number | |
Explanation: the number of ways will be maximum when all the possible |
289. | Which of the following is true? |
A. | prim’s algorithm can also be used for disconnected graphs |
B. | kruskal’s algorithm can also run on the disconnected graphs |
C. | prim’s algorithm is simpler than kruskal’s algorithm |
D. | in kruskal’s sort edges are added to mst in decreasing order of their weights |
Answer» B. kruskal’s algorithm can also run on the disconnected graphs | |
Explanation: prim’s algorithm iterates from one node to another, so it can not be applied for disconnected graph. kruskal’s algorithm can be applied to the disconnected graphs to construct the minimum cost forest. kruskal’s algorithm is comparatively easier and simpler than prim’s algorithm. |
290. | Consider the graph shown below. Which of the following are the edges in the MST of the given graph? |
A. | (a-c)(c-d)(d-b)(d-b) |
B. | (c-a)(a-d)(d-b)(d-e) |
C. | (a-d)(d-c)(d-b)(d-e) |
D. | (c-a)(a-d)(d-c)(d-b)(d-e) |
Answer» C. (a-d)(d-c)(d-b)(d-e) | |
Explanation: the minimum spanning tree of the given graph is shown below. it has cost 56. |
291. | Fractional knapsack problem is also known as |
A. | 0/1 knapsack problem |
B. | continuous knapsack problem |
C. | divisible knapsack problem |
D. | non continuous knapsack problem |
Answer» B. continuous knapsack problem | |
Explanation: fractional knapsack problem is also called continuous knapsack problem. |
292. | Fractional knapsack problem is solved most efficiently by which of the following algorithm? |
A. | divide and conquer |
B. | dynamic programming |
C. | greedy algorithm |
D. | backtracking |
Answer» C. greedy algorithm | |
Explanation: greedy algorithm is used to solve this problem. we first sort items according to their value/weight ratio and then add item with highest ratio until we cannot add the next item as a whole. at the end, we add the next item as much as we can. |
293. | What is the objective of the knapsack problem? |
A. | to get maximum total value in the knapsack |
B. | to get minimum total value in the knapsack |
C. | to get maximum weight in the knapsack |
D. | to get minimum weight in the knapsack |
Answer» A. to get maximum total value in the knapsack | |
Explanation: the objective is to fill the knapsack of some given volume with different materials such that the value of selected items is maximized. |
294. | Which of the following statement about 0/1 knapsack and fractional knapsack problem is correct? |
A. | in 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible |
B. | both are the same |
C. | 0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming |
D. | in 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible |
Answer» D. in 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible | |
Explanation: in fractional knapsack problem we can partially include an item into the knapsack whereas in 0/1 knapsack we have to either include or exclude the item wholly. |
295. | Time complexity of fractional knapsack problem is |
A. | o(n log n) |
B. | o(n) |
C. | o(n2) |
D. | o(nw) |
Answer» A. o(n log n) | |
Explanation: as the main time taking a step is of sorting so it defines the time complexity of our code. so the time complexity will be o(n log n) if we use quick sort for sorting. |
296. | Fractional knapsack problem can be solved in time O(n). |
A. | true |
B. | false |
Answer» A. true | |
Explanation: it is possible to solve the problem in o(n) time by adapting the algorithm for finding weighted medians. |
297. | Find the maximum value output assuming items to be divisible. |
A. | 60 |
B. | 80 |
C. | 100 |
D. | 40 |
Answer» A. 60 | |
Explanation: the value/weight ratio are- |
298. | The result of the fractional knapsack is greater than or equal to 0/1 knapsack. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: as fractional knapsack gives extra liberty to include the object partially which is not possible with 0/1 knapsack, thus |
299. | The main time taking step in fractional knapsack problem is |
A. | breaking items into fraction |
B. | adding items into knapsack |
C. | sorting |
D. | looping through sorted items |
Answer» C. sorting | |
Explanation: the main time taking step is to sort the items according to their value/weight ratio. it defines the time complexity of the code. |
301. | Given G is a bipartite graph and the bipartitions of this graphs are U and V respectively. What is the relation between them? | |
A. | number of vertices in u = number of vertices in v | |
B. | sum of degrees of vertices in u = sum of degrees of vertices in v | |
C. | number of vertices in u > number of vertices in v | |
D. | nothing can be said | |
Answer» B. sum of degrees of vertices in u = sum of degrees of vertices in v | ||
Explanation: we can prove this by induction. by adding one edge, the degree of vertices in u is equal to 1 as well as in v. let us assume that this is true for n-1 edges and add one more edge. since the given edge adds exactly once to both u and v we can tell that this statement is true for all n vertices. | ||
302. | A k-regular bipartite graph is the one in which degree of each vertices is k for all the vertices in the graph. Given that the bipartitions of this graph are U and V respectively. What is the relation between them? |
A. | number of vertices in u=number of vertices in v |
B. | number of vertices in u not equal to number of vertices in v |
C. | number of vertices in u always greater than the number of vertices in v |
D. | nothing can be said |
Answer» A. number of vertices in u=number of vertices in v | |
Explanation: we know that in a bipartite graph sum of degrees of vertices in u=sum of degrees of vertices in v. given that the graph is a k-regular bipartite graph, we have k* (number of vertices in u)=k*(number of vertices in v). |
303. | A complete bipartite graph is a one in which each vertex in set X has an edge with set Y. Let n be the total number of vertices. For maximum number of edges, the total number of vertices hat should be present on set X is? |
A. | n |
B. | n/2 |
C. | n/4 |
D. | data insufficient |
Answer» B. n/2 | |
Explanation: we can prove this by calculus. let x be the total number of vertices on set x. therefore set y will have n-x. we have to maximize x*(n-x). this is true when x=n/2. |
304. | When is a graph said to be bipartite? |
A. | if it can be divided into two independent sets a and b such that each edge connects a vertex from to a to b |
B. | if the graph is connected and it has odd number of vertices |
C. | if the graph is disconnected |
D. | if the graph has at least n/2 vertices whose degree is greater than n/2 |
Answer» A. if it can be divided into two independent sets a and b such that each edge connects a vertex from to a to b | |
Explanation: a graph is said to be bipartite if it can be divided into two independent sets a and b such that each edge connects a vertex from a to b. |
305. | Are trees bipartite? |
A. | yes |
B. | no |
C. | yes if it has even number of vertices |
D. | no if it has odd number of vertices |
Answer» A. yes | |
Explanation: condition needed is that there should not be an odd cycle. but in a tree there are no cycles at all. hence it is bipartite. |
306. | A graph has 20 vertices. The maximum number of edges it can have is? (Given it is bipartite) |
A. | 100 |
B. | 140 |
C. | 80 |
D. | 20 |
Answer» A. 100 | |
Explanation: let the given bipartition x have x vertices, then y will have 20-x vertices. we need to maximize x*(20-x). this will be maxed when x=10. |
307. | Given that a graph contains no odd cycle. Is it enough to tell that it is bipartite? |
A. | yes |
B. | no |
Answer» A. yes | |
Explanation: it is required that the graph is connected also. if it is not then it cannot be called a bipartite graph. |
308. | Can there exist a graph which is both eulerian and is bipartite? |
A. | yes |
B. | no |
C. | yes if it has even number of edges |
D. | nothing can be said |
Answer» A. yes | |
Explanation: if a graph is such that there exists a path which visits every edge atleast once, then it is said to be eulerian. taking an example of a square, the given question evaluates to yes. |
309. | A graph is found to be 2 colorable. What can be said about that graph? |
A. | the given graph is eulerian |
B. | the given graph is bipartite |
C. | the given graph is hamiltonian |
D. | the given graph is planar |
Answer» B. the given graph is bipartite | |
Explanation: a graph is said to be colorable if two vertices connected by an edge are never of the same color. 2 colorable mean that this can be achieved with just 2 colors. |
310. | Which type of graph has no odd cycle in it? |
A. | bipartite |
B. | histogram |
C. | cartesian |
D. | pie |
Answer» A. bipartite | |
Explanation: the graph is known as bipartite if the graph does not contain any odd length cycle in it. odd length cycle means a cycle with the odd number of vertices in it. |
311. | What type of graph has chromatic number less than or equal to 2? |
A. | histogram |
B. | bipartite |
C. | cartesian |
D. | tree |
Answer» B. bipartite | |
Explanation: a graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. the smallest number of graphs needed to color the graph is chromatic number. |
312. | Which of the following is the correct type of spectrum of the bipartite graph? |
A. | symmetric |
B. | anti – symmetric |
C. | circular |
D. | exponential |
Answer» A. symmetric | |
Explanation: the spectrum of the bipartite graph is symmetric in nature. the spectrum is the property of graph that are related to polynomial, eigen values, eigen vectors of the matrix related to graph. |
313. | Which of the following is not a property of the bipartite graph? |
A. | no odd cycle |
B. | symmetric spectrum |
C. | chromatic number is less than or equal to 2 |
D. | asymmetric spectrum |
Answer» D. asymmetric spectrum | |
Explanation: a graph is known to be bipartite if it has odd length cycle number. it also has symmetric spectrum and the bipartite graph contains the total chromatic number less than or equal to 2. |
314. | Which one of the following is the chromatic number of bipartite graph? |
A. | 1 |
B. | 4 |
C. | 3 |
D. | 5 |
Answer» A. 1 | |
Explanation: a graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. the smallest number of graphs needed to color the graph is the chromatic number. |
315. | Which graph has a size of minimum vertex cover equal to maximum matching? |
A. | cartesian |
B. | tree |
C. | heap |
D. | bipartite |
Answer» D. bipartite | |
Explanation: the konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. bipartite graph has a size of minimum vertex cover equal to maximum matching. |
316. | Which theorem gives the relation between the minimum vertex cover and maximum matching? |
A. | konig’s theorem |
B. | kirchhoff’s theorem |
C. | kuratowski’s theorem |
D. | kelmans theorem |
Answer» A. konig’s theorem | |
Explanation: the konig’s theorem given the equivalence relation between the minimum vertex cover and the maximum matching in graph theory. bipartite graph has a size of minimum vertex cover equal to maximum matching. |
317. | Which of the following is not a property of perfect graph? |
A. | compliment of line graph of bipartite graph |
B. | compliment of bipartite graph |
C. | line graph of bipartite graph |
D. | line graph |
Answer» D. line graph | |
Explanation: tthe compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph is known as a perfect graph in graph theory. normal line graph is not a perfect graph whereas line perfect graph is a graph whose line graph is a perfect graph. |
318. | Which of the following has maximum clique size 2? |
A. | perfect graph |
B. | tree |
C. | histogram |
D. | cartesian |
Answer» A. perfect graph | |
Explanation: the perfect bipartite graph has clique size 2. also, the clique size of compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph is 2. |
319. | What is the chromatic number of compliment of line graph of bipartite graph? |
A. | 0 |
B. | 1 |
C. | 2 |
D. | 3 |
Answer» C. 2 | |
Explanation: the perfect bipartite graph has chromatic number 2. so the compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph has chromatic number 2. |
320. | What is the clique size of the line graph of bipartite graph? |
A. | 0 |
B. | 1 |
C. | 2 |
D. | 3 |
Answer» C. 2 | |
Explanation: the perfect bipartite graph has clique size 2. so the clique size of compliment of line graph of bipartite graph, compliment of bipartite graph, line graph of bipartite graph and every bipartite graph is 2. |
321. | It is possible to have a negative chromatic number of bipartite graph. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: a graph is known as bipartite graph if and only if it has the total chromatic number less than or equal to 2. the smallest number of graphs needed to color the graph is the chromatic number. but the chromatic number cannot be negative. |
322. | Every Perfect graph has forbidden graph characterization. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: berge theorem proves the forbidden graph characterization of every perfect graphs. because of that reason every bipartite graph is perfect graph. |
323. | Which structure can be modelled by using Bipartite graph? |
A. | hypergraph |
B. | perfect graph |
C. | hetero graph |
D. | directed graph |
Answer» A. hypergraph | |
Explanation: a combinatorial structure such as hypergraph can be made using the bipartite graphs. a hypergraph in graph |
324. | Which type of graph has all the vertex of the first set connected to all the vertex of the second set? |
A. | bipartite |
B. | complete bipartite |
C. | cartesian |
D. | pie |
Answer» B. complete bipartite | |
Explanation: the graph is known as bipartite if the graph does not contain any odd length cycle in it. the complete bipartite graph has all the vertex of first set connected to all the vertex of second set. |
326. | Which term defines all the complete bipartite graph that are trees? | |
A. | symmetric | |
B. | anti – symmetric | |
C. | circular | |
D. | stars | |
Answer» D. stars | ||
Explanation: star is a complete bipartite graph with one internal node and k leaves. therefore, all complete bipartite graph which is trees are known as stars in graph theory. | ||
327. | How many edges does a n vertex triangle free graph contains? |
A. | n2 |
B. | n2 + 2 |
C. | n2 / 4 |
D. | n3 |
Answer» C. n2 / 4 | |
Explanation: a n vertex triangle free graph contains a total of n2 / 4 number of edges. this is stated by mantel’s theorem which is a special case in turan’s theorem for r=2. |
328. | Which graph is used to define the claw free graph? |
A. | bipartite graph |
B. | claw graph |
C. | star graph |
D. | cartesian graph |
Answer» B. claw graph | |
Explanation: star is a complete bipartite graph with one internal node and k leaves. star with three edges is called a claw. hence this graph is used to define claw free graph. |
329. | What is testing of a complete bipartite subgraph in a bipartite graph problem called? |
A. | p problem |
B. | p-complete problem |
C. | np problem |
D. | np-complete problem |
Answer» D. np-complete problem | |
Explanation: np stands for nondeterministic polynomial time. in a bipartite graph, the testing of a complete bipartite subgraph in a bipartite graph is an np-complete problem. |
330. | Which graph cannot contain K3, 3 as a minor of graph? |
A. | planar graph |
B. | outer planar graph |
C. | non planar graph |
D. | inner planar graph |
Answer» A. planar graph | |
Explanation: minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off |
331. | Which of the following is not an Eigen value of the adjacency matrix of the complete bipartite graph? |
A. | (nm)1/2 |
B. | (-nm)1/2 |
C. | 0 |
D. | nm |
Answer» D. nm | |
Explanation: the adjacency matrix is a square matrix that is used to represent a finite graph. therefore, the eigen values for the complete bipartite graph is found to be (nm)1/2, (-nm)1/2, 0. |
332. | Which complete graph is not present in minor of Outer Planar Graph? |
A. | k3, 3 |
B. | k3, 1 |
C. | k3, 2 |
D. | k1, 1 |
Answer» C. k3, 2 | |
Explanation: minor graph is formed by deleting certain number of edges from a graph or by deleting certain number off vertices from a graph. hence outer planar graph cannot contain k3, 2 as a minor graph. |
333. | Is every complete bipartite graph a Moore Graph. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: in graph theory, moore graph is defined as a regular graph that has a degree d and diameter k. therefore, every complete bipartite graph is a moore graph. |
334. | What is the multiplicity for the adjacency matrix of complete bipartite graph for 0 Eigen value? |
A. | 1 |
B. | n + m – 2 |
C. | 0 |
D. | 2 |
Answer» B. n + m – 2 | |
Explanation: the adjacency matrix is a square matrix that is used to represent a finite graph. the multiplicity of the adjacency matrix off complete bipartite graph with eigen value 0 is n + m – 2. |
335. | Which of the following is not an Eigen value of the Laplacian matrix of the complete bipartite graph? |
A. | n + m |
B. | n |
C. | 0 |
D. | n*m |
Answer» D. n*m | |
Explanation: the laplacian matrix is used to represent a finite graph in the mathematical field of graph theory. therefore, the eigen values for the complete bipartite graph is found to be n + m, n, m, 0. |
336. | What is the multiplicity for the laplacian matrix of the complete bipartite graph for n Eigen value? |
A. | 1 |
B. | m-1 |
C. | n-1 |
D. | 0 |
Answer» B. m-1 | |
Explanation: the laplacian matrix is used to represent a finite graph in the mathematical field of graph theory. the multiplicity of the laplacian matrix of complete bipartite graph with eigen value n is m-1. |
337. | Is it true that every complete bipartite graph is a modular graph. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: yes, the modular graph in graph theory is defined as an undirected |
338. | How many spanning trees does a complete bipartite graph contain? |
A. | nm |
B. | mn-1 * nn-1 |
C. | 1 |
D. | 0 |
Answer» B. mn-1 * nn-1 | |
Explanation: spanning tree of a given graph is defined as the subgraph or the tree with all the given vertices but having minimum number of edges. so, there are a total of mn-1 |
339. | What does Maximum flow problem involve? |
A. | finding a flow between source and sink that is maximum |
B. | finding a flow between source and sink that is minimum |
C. | finding the shortest path between source and sink |
D. | computing a minimum spanning tree |
Answer» A. finding a flow between source and sink that is maximum | |
Explanation: the maximum flow problem involves finding a feasible flow between a source and a sink in a network that is maximum and not minimum. |
340. | A network can have only one source and one sink. |
A. | false |
B. | true |
Answer» B. true | |
Explanation: a network can have only one source and one sink inorder to find the feasible flow in a weighted connected graph. |
341. | What is the source? |
A. | vertex with no incoming edges |
B. | vertex with no leaving edges |
C. | centre vertex |
D. | vertex with the least weight |
Answer» A. vertex with no incoming edges | |
Explanation: vertex with no incoming edges is called as a source. vertex with no leaving edges is called as a sink. |
342. | Which algorithm is used to solve a maximum flow problem? |
A. | prim’s algorithm |
B. | kruskal’s algorithm |
C. | dijkstra’s algorithm |
D. | ford-fulkerson algorithm |
Answer» D. ford-fulkerson algorithm | |
Explanation: ford-fulkerson algorithm is used to compute the maximum feasible flow between a source and a sink in a network. |
343. | Does Ford- Fulkerson algorithm use the idea of? |
A. | naïve greedy algorithm approach |
B. | residual graphs |
C. | minimum cut |
D. | minimum spanning tree |
Answer» B. residual graphs | |
Explanation: ford-fulkerson algorithm uses the idea of residual graphs which is an extension of naïve greedy approach allowing undo operations. |
344. | The first step in the naïve greedy algorithm is? |
A. | analysing the zero flow |
B. | calculating the maximum flow using trial and error |
C. | adding flows with higher values |
D. | reversing flow if required |
Answer» A. analysing the zero flow | |
Explanation: the first step in the naïve greedy algorithm is to start with the zero flow followed by adding edges with higher values. |
345. | Under what condition can a vertex combine and distribute flow in any manner? |
A. | it may violate edge capacities |
B. | it should maintain flow conservation |
C. | the vertex should be a source vertex |
D. | the vertex should be a sink vertex |
Answer» B. it should maintain flow conservation | |
Explanation: a vertex can combine and distribute flow in any manner but it should not violate edge capacities and it should maintain flow conservation. |
346. | Find the maximum flow from the following graph. |
A. | 22 |
B. | 17 |
C. | 15 |
D. | 20 |
Answer» C. 15 | |
Explanation: initially, zero flow is computed. then, computing flow= 7+1+5+2=15. hence, maximum flow=15. |
347. | A simple acyclic path between source and sink which pass through only positive weighted edges is called? |
A. | augmenting path |
B. | critical path |
C. | residual path |
D. | maximum path |
Answer» A. augmenting path | |
Explanation: augmenting path between source and sink is a simple path without cycles. path consisting of zero slack edges is called critical path. |
348. | Dinic’s algorithm runs faster than the Ford-Fulkerson algorithm. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: dinic’s algorithm includes construction of level graphs and reslidual graphs and finding of augmenting paths along with blocking flow and is faster than the |
349. | Who is the formulator of Maximum flow problem? |
A. | lester r. ford and delbert r. fulkerson |
B. | t.e. harris and f.s. ross |
C. | y.a. dinitz |
D. | kruskal |
Answer» B. t.e. harris and f.s. ross | |
Explanation: the first ever people to |
351. | Stable marriage problem is an example of? | |
A. | branch and bound algorithm | |
B. | backtracking algorithm | |
C. | greedy algorithm | |
D. | divide and conquer algorithm | |
Answer» B. backtracking algorithm | ||
Explanation: stable marriage problem is an example for recursive algorithm because it recursively uses backtracking algorithm to find an optimal solution. | ||
352. | Which of the following algorithms does Stable marriage problem uses? |
A. | gale-shapley algorithm |
B. | dijkstra’s algorithm |
C. | ford-fulkerson algorithm |
D. | prim’s algorithm |
Answer» A. gale-shapley algorithm | |
Explanation: stable marriage problem uses gale-shapley algorithm. maximum flow problem uses ford-fulkerson algorithm. |
353. | An optimal solution satisfying men’s preferences is said to be? |
A. | man optimal |
B. | woman optimal |
C. | pair optimal |
D. | best optimal |
Answer» A. man optimal | |
Explanation: an optimal solution satisfying men’s preferences are said to be man optimal. an optimal solution satisfying woman’s preferences are said to be woman optimal. |
354. | When a free man proposes to an available woman, which of the following happens? |
A. | she will think and decide |
B. | she will reject |
C. | she will replace her current mate |
D. | she will accept |
Answer» D. she will accept | |
Explanation: when a man proposes to an available woman, she will accept his proposal irrespective of his position on his preference list. |
355. | If there are n couples who would prefer each other to their actual marriage partners, then the assignment is said to be unstable. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: if there are n couples such that a man and a woman are not married, and if they prefer each other to their actual partners, the assignment is unstable. |
356. | How many 2*2 matrices are used in this problem? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | 4 |
Answer» B. 2 | |
Explanation: two 2*2 matrices are used. one for men representing corresponding woman and ranking and the other for women. |
357. | What happens when a free man approaches a married woman? |
A. | she simply rejects him |
B. | she simply replaces her mate with him |
C. | she goes through her preference list and accordingly, she replaces her current mate with him |
D. | she accepts his proposal |
Answer» C. she goes through her preference list and accordingly, she replaces her current mate with him | |
Explanation: if the preference of the man is greater, she replaces her current mate with him, leaving her current mate free. |
358. | In case of stability, how many symmetric possibilities of trouble can occur? |
A. | 1 |
B. | 2 |
C. | 4 |
D. | 3 |
Answer» B. 2 | |
Explanation: possibilities- there might be a woman pw, preferred to w by m, who herself prefers m to be her husband and the same applies to man as well. |
359. | Which of the following happens? |
A. | w2 replaces m1 with m2 |
B. | w2 rejects m2 |
C. | w2 accepts both m1 and m2 |
D. | w2 rejects both m1 and m2 |
Answer» A. w2 replaces m1 with m2 | |
Explanation: w2 is married to m1. but the preference of w2 has m2 before m1. hence, w2 replaces m1 with m2. |
360. | Who formulated a straight forward backtracking scheme for stable marriage problem? |
A. | mcvitie and wilson |
B. | gale |
C. | ford and fulkerson |
D. | dinitz |
Answer» A. mcvitie and wilson | |
Explanation: mcvitie and wilson formulated a much faster straight forward backtracking scheme for stable marriage problem. ford and fulkerson formulated maximum flow problem. |
361. | Can stable marriage cannot be solved using branch and bound algorithm. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: stable marriage problem can be solved using branch and bound approach because branch and bound follows backtracking scheme with a limitation factor. |
362. | What is the prime task of the stable marriage problem? |
A. | to provide man optimal solution |
B. | to provide woman optimal solution |
C. | to determine stability of marriage |
D. | to use backtracking approach |
Answer» C. to determine stability of marriage | |
Explanation: the prime task of stable marriage problem is to determine stability of marriage (i.e) finding a man and a woman who prefer each other to others. |
363. | Which of the following problems is related to stable marriage problem? |
A. | choice of school by students |
B. | n-queen problem |
C. | arranging data in a database |
D. | knapsack problem |
Answer» A. choice of school by students | |
Explanation: choice of school by students is the most related example in the given set of options since both school and students will have a preference list. |
364. | What is the efficiency of Gale-Shapley algorithm used in stable marriage problem? |
A. | o(n) |
B. | o(n log n) |
C. | o(n2) |
D. | o(log n) |
Answer» C. o(n2) | |
Explanation: the time efficiency of gale- shapley algorithm is mathematically found to be o(n2) where n denotes stable marriage problem. |
365. | is a matching with the largest number of edges. |
A. | maximum bipartite matching |
B. | non-bipartite matching |
C. | stable marriage |
D. | simplex |
Answer» A. maximum bipartite matching | |
Explanation: maximum bipartite matching matches two elements with a property that no two edges share a vertex. |
366. | Maximum matching is also called as maximum cardinality matching. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: maximum matching is also called as maximum cardinality matching (i.e.) matching with the largest number of edges. |
367. | How many colours are used in a bipartite graph? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | 4 |
Answer» B. 2 | |
Explanation: a bipartite graph is said to be two-colourable so that every edge has its vertices coloured in different colours. |
368. | What is the simplest method to prove that a graph is bipartite? |
A. | it has a cycle of an odd length |
B. | it does not have cycles |
C. | it does not have a cycle of an odd length |
D. | both odd and even cycles are formed |
Answer» C. it does not have a cycle of an odd length | |
Explanation: it is not difficult to prove that a graph is bipartite if and only if it does not have a cycle of an odd length. |
369. | A matching that matches all the vertices of a graph is called? |
A. | perfect matching |
B. | cardinality matching |
C. | good matching |
D. | simplex matching |
Answer» A. perfect matching | |
Explanation: a matching that matches all the vertices of a graph is called perfect matching. |
370. | What is the length of an augmenting path? |
A. | even |
B. | odd |
C. | depends on graph |
D. | 1 |
Answer» B. odd | |
Explanation: the length of an augmenting path in a bipartite graph is always said to be always odd. |
371. | In a bipartite graph G=(V,U,E), the matching of a free vertex in V to a free vertex in U is called? |
A. | bipartite matching |
B. | cardinality matching |
C. | augmenting |
D. | weight matching |
Answer» C. augmenting | |
Explanation: a simple path from a free vertex in v to a free vertex in u whose edges alternate between edges not in m and edges in m is called a augmenting path. |
372. | A matching M is maximal if and only if there exists no augmenting path with respect to M. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: according to the theorem discovered by the french mathematician claude berge, it means that the current matching is maximal if there is no augmenting path. |
373. | Which one of the following is an application for matching? |
A. | proposal of marriage |
B. | pairing boys and girls for a dance |
C. | arranging elements in a set |
D. | finding the shortest traversal path |
Answer» B. pairing boys and girls for a dance | |
Explanation: pairing boys and girls for a dance is a traditional example for matching. proposal of marriage is an application of stable marriage problem. |
374. | Which is the correct technique for finding a maximum matching in a graph? |
A. | dfs traversal |
B. | bfs traversal |
C. | shortest path traversal |
D. | heap order traversal |
Answer» B. bfs traversal | |
Explanation: the correct technique for finding a maximum matching in a bipartite graph is by using a breadth first search(bfs). |
376. | Who was the first person to solve the maximum matching problem? |
A. | jack edmonds |
B. | hopcroft |
C. | karp |
D. | claude berge |
Answer» A. jack edmonds | |
Explanation: jack edmonds was the first person to solve the maximum matching problem in 1965. |
377. | From the given graph, how many vertices can be matched using maximum matching in bipartite graph algorithm? |
A. | 5 |
B. | 4 |
C. | 3 |
D. | 2 |
Answer» A. 5 | |
Explanation: one of the solutions of the matching problem is given by a-w,b-v,c-x,d- y,e-z. hence the answer is 5. |
378. | The worst-case efficiency of solving a problem in polynomial time is? |
A. | o(p(n)) |
B. | o(p( n log n)) |
C. | o(p(n2)) |
D. | o(p(m log n)) |
Answer» A. o(p(n)) | |
Explanation: the worst-case efficiency of solving an problem in polynomial time is o(p(n)) where p(n) is the polynomial time of input size. |
379. | Problems that can be solved in polynomial time are known as? |
A. | intractable |
B. | tractable |
C. | decision |
D. | complete |
Answer» B. tractable | |
Explanation: problems that can be solved in polynomial time are known as tractable. |
380. | The sum and composition of two polynomials are always polynomials. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: one of the properties of polynomial functions states that the sum and composition of two polynomials are always polynomials. |
381. | is the class of decision problems that can be solved by non- deterministic polynomial algorithms? |
A. | np |
B. | p |
C. | hard |
D. | complete |
Answer» A. np | |
Explanation: np problems are called as non- deterministic polynomial problems. they are a class of decision problems that can be solved using np algorithms. |
382. | Problems that cannot be solved by any algorithm are called? |
A. | tractable problems |
B. | intractable problems |
C. | undecidable problems |
D. | decidable problems |
Answer» C. undecidable problems | |
Explanation: problems cannot be solved by any algorithm are called undecidable problems. problems that can be solved in polynomial time are called tractable problems. |
383. | The Euler’s circuit problem can be solved in? |
A. | o(n) |
B. | o( n log n) |
C. | o(log n) |
D. | o(n2) |
Answer» D. o(n2) | |
Explanation: mathematically, the run time of euler’s circuit problem is determined to be o(n2). |
384. | To which class does the Euler’s circuit problem belong? |
A. | p class |
B. | np class |
C. | partition class |
D. | complete class |
Answer» A. p class | |
Explanation: euler’s circuit problem can be solved in polynomial time. it can be solved in o(n2). |
385. | Halting problem is an example for? |
A. | decidable problem |
B. | undecidable problem |
C. | complete problem |
D. | trackable problem |
Answer» B. undecidable problem | |
Explanation: halting problem by alan turing cannot be solved by any algorithm. hence, it is undecidable. |
386. | How many stages of procedure does a non- deterministic algorithm consist of? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | 4 |
Answer» B. 2 | |
Explanation: a non-deterministic algorithm is a two-stage procedure- guessing stage and verification stage. |
387. | A non-deterministic algorithm is said to be non-deterministic polynomial if the time- efficiency of its verification stage is polynomial. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: one of the properties of np class problems states that a non-deterministic algorithm is said to be non-deterministic polynomial if the time-efficiency of its verification stage is polynomial. |
388. | How many conditions have to be met if an NP- complete problem is polynomially reducible? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | 4 |
Answer» B. 2 | |
Explanation: a function t that maps all yes instances of decision problems d1 and d2 and t should be computed in polynomial time are the two conditions. |
389. | To which of the following class does a CNF-satisfiability problem belong? |
A. | np class |
B. | p class |
C. | np complete |
D. | np hard |
Answer» C. np complete | |
Explanation: the cnf satisfiability problem belongs to np complete class. it deals with boolean expressions. |
390. | How many steps are required to prove that a decision problem is NP complete? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | 4 |
Answer» B. 2 | |
Explanation: first, the problem should be np. next, it should be proved that every problem in np is reducible to the problem in question in polynomial time. |
391. | Which of the following problems is not NP complete? |
A. | hamiltonian circuit |
B. | bin packing |
C. | partition problem |
D. | halting problem |
Answer» D. halting problem | |
Explanation: hamiltonian circuit, bin packing, partition problems are np complete problems. halting problem is an undecidable problem. |
392. | 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 |
Answer» A. computational complexity | |
Explanation: an extensive theory called computational complexity seeks to classify problems according to their inherent difficulty. |
393. | Which of the following algorithm can be used to solve the Hamiltonian path problem efficiently? |
A. | branch and bound |
B. | iterative improvement |
C. | divide and conquer |
D. | greedy algorithm |
Answer» A. branch and bound | |
Explanation: the hamiltonian path problem can be solved efficiently using branch and bound approach. it can also be solved using a backtracking approach. |
394. | The problem of finding a path in a graph that visits every vertex exactly once is called? |
A. | hamiltonian path problem |
B. | hamiltonian cycle problem |
C. | subset sum problem |
D. | turnpike reconstruction problem |
Answer» A. hamiltonian path problem | |
Explanation: hamiltonian path problem is a problem of finding a path in a graph that visits every node exactly once whereas hamiltonian cycle problem is finding a cycle in a graph. |
395. | Hamiltonian path problem is |
A. | np problem |
B. | n class problem |
C. | p class problem |
D. | np complete problem |
Answer» D. np complete problem | |
Explanation: hamiltonian path problem is found to be np complete. hamiltonian cycle problem is also an np- complete problem. |
396. | There is no existing relationship between a Hamiltonian path problem and Hamiltonian circuit problem. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: there is a relationship between hamiltonian path problem and hamiltonian circuit problem. the hamiltonian path in graph g is equal to hamiltonian cycle in graph h under certain conditions. |
397. | Which of the following problems is similar to that of a Hamiltonian path problem? |
A. | knapsack problem |
B. | closest pair problem |
C. | travelling salesman problem |
D. | assignment problem |
Answer» C. travelling salesman problem | |
Explanation: hamiltonian path problem is similar to that of a travelling salesman problem since both the problem traverses all the nodes in a graph exactly once. |
398. | Who formulated the first ever algorithm for solving the Hamiltonian path problem? |
A. | martello |
B. | monte carlo |
C. | leonard |
D. | bellman |
Answer» A. martello | |
Explanation: the first ever problem to solve the hamiltonian path was the enumerative algorithm formulated by martello. |
399. | In what time can the Hamiltonian path problem can be solved using dynamic programming? |
A. | o(n) |
B. | o(n log n) |
C. | o(n2) |
D. | o(n2 2n) |
Answer» D. o(n2 2n) | |
Explanation: using dynamic programming, the time taken to solve the hamiltonian path problem is mathematically found to be o(n2 2n). |
401. | Who invented the inclusion-exclusion principle to solve the Hamiltonian path problem? |
A. | karp |
B. | leonard adleman |
C. | andreas bjorklund |
D. | martello |
Answer» C. andreas bjorklund | |
Explanation: andreas bjorklund came up with the inclusion-exclusion principle to reduce the counting of number of hamiltonian cycles. |
402. | For a graph of degree three, in what time can a Hamiltonian path be found? |
A. | o(0.251n) |
B. | o(0.401n) |
C. | o(0.167n) |
D. | o(0.151n) |
Answer» A. o(0.251n) | |
Explanation: for a graph of maximum degree three, a hamiltonian path can be found in time o(0.251n). |
403. | What is the time complexity for finding a Hamiltonian path for a graph having N vertices (using permutation)? |
A. | o(n!) |
B. | o(n! * n) |
C. | o(log n) |
D. | o(n) |
Answer» B. o(n! * n) | |
Explanation: for a graph having n vertices traverse the permutations in n! iterations and it traverses the permutations to see if adjacent vertices are connected or not takes n iterations (i.e.) o(n! * n). |
404. | How many Hamiltonian paths does the following graph have? |
A. | 1 |
B. | 2 |
C. | 3 |
D. | 4 |
Answer» A. 1 | |
Explanation: the above graph has only one hamiltonian path that is from a-b-c-d-e. |
405. | How many Hamiltonian paths does the following graph have? |
A. | 1 |
B. | 2 |
C. | 0 |
D. | 3 |
Answer» C. 0 | |
Explanation: the above graph has no hamiltonian paths. that is, we cannot traverse the graph with meeting vertices exactly once. |
406. | Under what condition any set A will be a subset of B? |
A. | if all elements of set b are also present in set a |
B. | if all elements of set a are also present in set b |
C. | if a contains more elements than b |
D. | if b contains more elements than a |
Answer» B. if all elements of set a are also present in set b | |
Explanation: any set a will be called a subset of set b if all elements of set a are also present in set b. so in such a case set a will be a part of set b. |
407. | What is a subset sum problem? |
A. | finding a subset of a set that has sum of elements equal to a given number |
B. | checking for the presence of a subset that has sum of elements equal to a given number and printing true or false based on the result |
C. | finding the sum of elements present in a set |
D. | finding the sum of all the subsets of a set |
Answer» B. checking for the presence of a subset that has sum of elements equal to a given number and printing true or false based on the result | |
Explanation: in subset sum problem check for the presence of a subset that has sum of elements equal to a given number. if such a |
408. | Which of the following is true about the time complexity of the recursive solution of the subset sum problem? |
A. | it has an exponential time complexity |
B. | it has a linear time complexity |
C. | it has a logarithmic time complexity |
D. | it has a time complexity of o(n2) |
Answer» A. it has an exponential time complexity | |
Explanation: subset sum problem has both recursive as well as dynamic programming solution. the recursive solution has an exponential time complexity as it will require to check for all subsets in worst case. |
409. | Subset sum problem is an example of NP- complete problem. |
A. | true |
B. | false |
Answer» A. true | |
Explanation: subset sum problem takes exponential time when we implement a recursive solution. subset sum problem is known to be a part of np complete problems. |
410. | Recursive solution of subset sum problem is faster than dynamic problem solution in terms of time complexity. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: the recursive solution to subset sum problem takes exponential time complexity whereas the dynamic programming solution takes polynomial time complexity. so dynamic programming solution is faster in terms of time complexity. |
411. | Which of the following is not true about subset sum problem? |
A. | the recursive solution has a time complexity of o(2n) |
B. | there is no known solution that takes polynomial time |
C. | the recursive solution is slower than dynamic programming solution |
D. | the dynamic programming solution has a time complexity of o(n log n) |
Answer» D. the dynamic programming solution has a time complexity of o(n log n) | |
Explanation: recursive solution of subset sum problem is slower than dynamic problem solution in terms of time complexity. |
412. | 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. | an empty set |
Answer» B. set of all subsets | |
Explanation: power set of a set is defined as the set of all subsets. ex- if there is a set s= |
413. | What is the set partition problem? |
A. | finding a subset of a set that has sum of elements equal to a given number |
B. | checking for the presence of a subset that has sum of elements equal to a given number |
C. | checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result |
D. | finding subsets with equal sum of elements |
Answer» C. checking whether the set can be divided into two subsets of with equal sum of elements and printing true or false based on the result | |
Explanation: in set partition problem we check whether a set can be divided into 2 subsets such that the sum of elements in each subset is equal. if such subsets are present then we print true otherwise false. |
414. | Which of the following is true about the time complexity of the recursive solution of set partition problem? |
A. | it has an exponential time complexity |
B. | it has a linear time complexity |
C. | it has a logarithmic time complexity |
D. | it has a time complexity of o(n2) |
Answer» A. it has an exponential time complexity | |
Explanation: set partition problem has both recursive as well as dynamic programming solution. the recursive solution has an exponential time complexity as it will require to check for all subsets in the worst case. |
415. | What is the worst case time complexity of dynamic programming solution of set partition problem(sum=sum of set elements)? |
A. | o(n) |
B. | o(sum) |
C. | o(n2) |
D. | o(sum*n) |
Answer» D. o(sum*n) | |
Explanation: set partition problem has both recursive as well as dynamic programming solution. the dynamic programming solution has a time complexity of o(n*sum) as it as a nested loop with limits from 1 to n and 1 to sum respectively. |
416. | Recursive solution of Set partition problem is faster than dynamic problem solution in terms of time complexity. |
A. | true |
B. | false |
Answer» B. false | |
Explanation: the recursive solution to set partition problem takes exponential time complexity whereas the dynamic programming solution takes polynomial time complexity. so dynamic programming solution is faster in terms of time complexity. |
417. | What will be the auxiliary space complexity of dynamic programming solution of set partition problem(sum=sum of set elements)? |
A. | o(n log n) |
B. | o(n2) |
C. | o(2n) |
D. | o(sum*n) |
Answer» D. o(sum*n) | |
Explanation: the auxiliary space complexity of set partition problem is required in order to store the partition table. it takes up a space of n*sum, so its auxiliary space requirement becomes o(n*sum). |
Tags
Question and answers in Design and Analysis of Algorithms,Design and Analysis of Algorithms multiple choice questions and answers,Design and Analysis of Algorithms Important MCQs,Solved MCQs for Design and Analysis of Algorithms,Design and Analysis of Algorithms MCQs with answers PDF download