Q1: The sequence of merge sort algorithm is:
(A) Divide Combine-Conquer
(B) Conquer-Divide-Combine
(C) Divide-Conquer-Combine
(D) Combine-Divide-Conquer
Answer: (C) Divide-Conquer-Combine
Q2: In Knapsack Problem, limitation is that an item can either be put in the bag or not. Fractional items are not allowed.
(A) 0
(B) 1
(C) 0/1
(D) Fractional
Answer: (C) 0/1
Q3: In Selection algorithm, we assume pivot selection takes theta running time.
(A) n
(B) n²
(C) n³
(D) log(n)
Answer: (A) n
Q4: In Heap Sort algorithm (using max heap), when every time maximum elements removed from top:
(A) We call merge Sort Algorithm
(B) It becomes Order n² Algorithm
(C) Divide and Conquer strategy helps us
(D) We are left with a hole
Answer: (D) We are left with a hole
Q5: If matrix A of dimension p x q is multiplied with matrix B of dimension q x r, then each entry in resultant matrix takes ___ time.
(A) O(q)
(B) O(1)
(C) O(p × q)
(D) O(q × r)
Answer: (A) O(q)
Q6: ___ is a method of solving a problem in which we check all possible solutions to the problem to find the solution we need.
(A) Plane-Sweep Algorithm
(B) Sorting Algorithm
(C) Brute-Force Algorithm
(D) Greedy approach
Answer: (C) Brute-Force Algorithm
Q7: The worst case running time of Quick sort algorithm:
(A) Cannot be quadratic
(B) Is quadratic
(C) Is always Exponential
(D) Is linear
Answer: (B) Is quadratic
Q8: In max heap (for Heap Sort algorithm), when every time maximum element is removed from top we replace it with ___ in the tree.
(A) second last
(B) Last
(C) First
(D) Any
Answer: (B) Last
Q9: Quick sort algorithm was developed by:
(A) Alferd Aho
(B) Sedgewick
(C) John Vincent Atanasoff
(D) Tony Hoare
Answer: (D) Tony Hoare
Q10: If Matrix-A has dimensions “3×2” and Matrix-B has dimensions “2×3”, then multiplication of Matrix-A and Matrix-B will result a new Matrix-C having dimensions:
(A) 3×2
(B) 2×3
(C) 2×2
(D) 3×3
Answer: (D) 3×3
Q11: For comparison-based sorting algorithms, it is possible to sort more efficiently than Ω(n log n) time.
(A) Always
(B) Not
(C) Sometimes
(D) Sometimes not
Answer: (B) Not
Q12: Dynamic Programming approach is usually useful in solving optimization problems.
(A) True
(B) False
Answer: (A) True
Q13: In Sorting the key value or attribute is from an ordered domain:
(A) Must be
(B) Not always
(C) May be
(D) Occasionally
Answer: (A) Must be
Q14: Result of asymptotical analysis of n(n -3) and 4n² is that:
(A) n(n-1) is asymptotically Less
(B) n(n-1) is asymptotically Greater
(C) Both are asymptotically Not equivalent
(D) Both are asymptotically Equivalent
Answer: (D) Both are asymptotically Equivalent
Q15: Floor and ceiling are ___ to calculate while analyzing algorithms:
(A) Very easy
(B) Usually considered difficult
(C) 3rd Option is missing
(D) 4th Option is missing
Answer: (B) Usually considered difficult
Q16: ___ of reference is an important fact of current processor technology.
(A) Defining
(B) Assigning
(C) Formality
(D) Locality
Answer: (D) Locality
Q17: In max-heap, largest element is stored at root node. Where is the smallest element stored?
(A) Right Node
(B) Leaf Node
(C) Middle Node
(D) Left Node
Answer: (B) Leaf Node
Q18: In average-case time analysis of Quick sort algorithm, the most balanced case for partition is when we divide the list of elements into:
(A) Equal no. of pieces as of input elements
(B) Single piece exactly
(C) Two nearly equal pieces
(D) Three nearly equal pieces
Answer: (C) Two nearly equal pieces
Q19: Which of the following is calculated with Big O notation?
(A) Medium bounds
(B) Upper bounds
(C) Lower bounds
(D) Both upper and lower bounds
Answer: (B) Upper bounds
Q20: Edit distance algorithm is based on ___ strategy.
(A) Greedy
(B) Dynamic Programming
(C) Divide and Conquer
(D) Searching
Answer: (B) Dynamic Programming
Q21: In Heapsort Algorithm, total time taken by heapify procedure is:
(A) O(log n)
(B) O(log² n)
(C) O(n log n)
(D) O(n² log n)
Answer: (C) O(n log n)
Q22: Al-Khwarizmi was a/an:
(A) Artist
(B) Mathematician
(C) Astronomer
(D) Khalifah
Answer: (B) Mathematician
Q23: When matrix A of 5×3 is multiplied with matrix B of 3×4, then the number of multiplications required is:
(A) 15
(B) 12
(C) 36
(D) 60
Answer: (D) 60
Q24: Pseudo code of algorithms are to be read by:
(A) People
(B) RAM
(C) Computer
(D) Compiler
Answer: (A) People
Q25: The sieve technique is a special case, where the number of sub-problems is just:
(A) 1
(B) 2
(C) 3
(D) 4
Answer: (A) 1
Q26: When a recursive algorithm revisits the same problem over and over again, we say that the optimization problem has ___ sub-problems.
(A) Overlapping
(B) Over costing
(C) Optimized
(D) Three
Answer: (A) Overlapping
Q27: Sieve technique is a very important special case of Divide-and-Conquer strategy.
(A) True
(B) False
Answer: (A) True
Q28: In order to say anything meaningful about our algorithms, it will be important for us to settle on a:
(A) Java Program
(B) C++ Program
(C) Pseudo program
(D) Mathematical model of computation
Answer: (D) Mathematical model of computation
Q29: Merge sort is based on:
(A) Brute-force
(B) Plan-sweep
(C) Axis-sweep
(D) Divide and Conquer
Answer: (D) Divide and Conquer