Q#1: Random Access Machine (RAM) is a/an
(A) Machine built by Al-Khwarizmi
(B) Mechanical machine
(C) Electronics machine
(D) Mathematical model
Answer: (D) Mathematical model
Q#2: ______ is a graphical representation of an algorithm.
(A) Σ notation
(B) Θ notation
(C) Flowchart
(D) Asymptotic notation
Answer: (C) Flowchart
Q#3: A RAM is an idealized machine with ______ random-access memory.
(A) 256 MB
(B) 512 MB
(C) an infinitely large
(D) 100 GB
Answer: (C) an infinitely large
Q#4: What type of instructions can a Random Access Machine (RAM) execute?
(A) Algebraic and logic
(B) Geometric and arithmetic
(C) Arithmetic and logic
(D) Parallel and recursive
Answer: (C) Arithmetic and logic
Q#5: Total number of maximum comparisons if we run brute-force maxima algorithm with n elements?
(A) n²
(B) n
(C) n² / n
(D) n⁸
Answer: (A) n²
Q#6: Solution to the recurrence T(n) = T(n/2) + n:
(A) O(log n)
(B) O(n)
(C) O(n log n)
(D) O(n²)
Answer: (C) O(n log n)
Q#9: Total time to heapify:
(A) O(log n)
(B) O(n log n)
(C) O(n² log n)
(D) O(log² n)
Answer: (B) O(n log n)
Q#10: When calling heapify, comparison performed at each level takes time:
(A) Θ(1)
(B) Varies according to input data
(C) Cannot be predicted
(D) Θ(log n)
Answer: (A) Θ(1)
Q#11: In Quick sort, we don’t have control over the sizes of recursive calls:
(A) True
(B) False
(C) Less information to decide
(D) Either true or false
Answer: (A) True
Q#12: Is it possible to sort without making comparisons?
(A) Yes
(B) No
Answer: (A) Yes
Q#13: If there are Θ(n²) entries in edit distance matrix, total running time is:
(A) Θ(1)
(B) Θ(n²)
(C) Θ(n)
(D) Θ(n log n)
Answer: (B) Θ(n²)
Q#14: For Chain Matrix Multiplication we cannot use divide and conquer because:
(A) We do not know the optimum k
(B) Divide and conquer is only for sorting
(C) Linear time is easy
(D) Size of data not given
Answer: (A) We do not know the optimum k
Q#15: The Knapsack problem belongs to the domain of ______ problems.
(A) Optimization
(B) NP Complete
(C) Linear Solution
(D) Sorting
Answer: (A) Optimization