DAA MCQ |Design and Analysis of Algorithms MCQ with Answers

by

1. The running time of an algorithm is given by

a. Total number of basic operations performed by the algorithm

b. Total number of statements

c. Maximum time taken to execute

d. None of the above

      2. What does time complexity measure in an algorithm?

      a. Number of operations executed

      b. Amount of memory used

      c. Number of lines of code

      d. Input size

      3. Which of the following best describes space complexity?

      a. The amount of time an algorithm takes to run

      b. The amount of memory an algorithm requires to execute

      c. The number of inputs an algorithm can handle

      d. The number of times an algorithm loops

      4. A problem

      a. Have only one algorithm

      b. May have multiple algorithm

      c. None of these

      5. What is the purpose of asymptotic notation in algorithm analysis?

      a. To precisely measure the exact number of operations in an algorithm

      b. To compare algorithms based on their exact execution times

      c. To simplify the comparison of algorithms based on their growth rates

      d. To provide a rough estimate of algorithmic performance

      6. Big Oh notation gives

      a. Upper Bound

      b. Lower Bound

      c. Strictly Upper Bound

      d. Strictly Lower Bound

      7. Which of the following notation is used to describe worst case time complexity

      a. Big Omega

      b. Theta

      c. Big O

      d. None of the above

      8. What does Θ(n) represent in asymptotic notation

      a. Best-case time complexity

      b. Tight bound on the time complexity

      c. Average-case time complexity

      d. Worst-case time complexity

      9. Which asymptotic notation represents the worst-case time complexity of an algorithm?

      a. Θ(n)

      b. O(n)

      c. Ω(n)

      d. All of the above

      10. Which notation describes Lower bound on the time complexity of an algorithm?

      a. Ω(n)

      b. Θ(n)

      c. O(n)

      d. All of the above

      11. If f(n) = θ(g(n)) then

      a. 0 ≤ c1g(n) ≤f(n) ≤ c2g(n) for all n ≥ n0

      b. 0 ≤ f(n) ≤c2g(n) for all n ≥ n0

      c. 0 ≤ c1g(n) ≤ f(n) for all n ≥ n0

      d. None of the above

      12. Which of the following is true about the relationship between O(n) and Ω(n)?

      a. O(n) is always greater than Ω(n)

      b. Ω(n) is always greater than O(n)

      c. O(n) and Ω(n) are equal

      d. There`s no relationship between O(n) and Ω(n)

      13. Which data structure is used to perform recursion?

      a. Queue

      b. Stack

      c. Priority Queue

      d. All of the above

      14. Which of the following problems can’t be solved using recursion?

      a. Length of a string

      b. Problems without base case

      c. Factorial of a number

      d. Nth Fibonacci number

      15. What is a recurrence relation?

      a. A relation between two variables that recurs infinitely

      b. A relation between two functions that recurs infinitely

      c. A mathematical expression that defines a function in terms of its value at smaller inputs

      d. A mathematical expression that defines a function in terms of its value at larger inputs

      16. Which of the following is a common notation for a recurrence relation?

      a. R(n) = R(n-1) + R(n-2)

      b. F(n) = F(n+1) – F(n-1)

      c. P(n) = P(n^2)

      d. Q(n) = 2 * Q(n/2)

      17. Which of the following method is used to solved a recurrence?

      a. Substitution Method

      b. Master Method

      c. Changing Variable

      d. All of the above

      18. Which method is commonly used to solve recurrence relations?

      a. Iterative method

      b. Dynamic programming

      c. Master theorem

      d. All of the above

      19. What is the base case in a recurrence relation?

      a. The case where the recurrence relation is true for all values of n

      b. The case where the recurrence relation is true for some specific value of n

      c. The smallest input value(s) for which the recurrence relation is defined directly

      d. The largest input value(s) for which the recurrence relation is defined directly

          20. Which of the following method uses mathematical induction to solve a recurrence.

          a. Substitution method

          b. Master method

          c. Recursion tree method

          d. None of the above

          • What is the Master Theorem based on?
            • Divide and conquer strategy
            • Dynamic programming
            • Linear algebra
            • Graph theory
          • What is the Master Theorem used for?
            • Solving differential equations
            • Solving recurrence relations
            • Analyzing algorithmic time complexity
            • Finding prime numbers
          • When applying the Master Theorem, what is compared to determine the complexity?
            • The number of subproblems and the size of each subproblem
            • The size of the original problem and the size of the subproblems
            • The number of recursive calls and the base case value
            • The coefficients of the leading terms in the recurrence relation
          • Which case of the Master Theorem applies when the work done at each level of recursion is asymptotically equal?
            • Case 1
            • Case 2
            • Case 3
            • None of the above
          • In the Master Theorem, what does “a” represent in the form T(n) = aT(n/+ f(n)?
            • The number of subproblems
            • The ratio of subproblem size to original problem size
            • The coefficient of the leading term in the recurrence relation
            • The base case value
          • What is the asymptotic notation for constant time complexity?
            • O(1)
            • O(n)
            • O(log n)
            • O(n^2)
          • What is the solution to the recurrence relation T(n) = 2T(n/2) + n?
            • O(n)
            • O(2n)
            • O(n2)
            • O(n log n)
          • What is the time complexity of the recurrence relation T(n) = T(n/3) + T(2n/3) + n?
            • O(n)
            • O(n log n)
            • O(n^2)
            • O(n^3)
          • In linear search worst case occurs if
            • Element to be searched is in the first position of the array
            • Element to be searched is in the last position of the array
            • Element to be searched is in the middle of the array
            • None of these
          • If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________
            • Dynamic programming
            • Greedy
            • Divide and conquer
            • Recursion
          • Which sorting adopt divide and conquer technique?
            • Merge Sort
            • Selection Sort
            • Bubble Sort
            • Insertion Sort
          • Merge sort uses which of the following technique to implement sorting?
            • Backtracking
            • greedy algorithm
            • divide and conquer
            • dynamic programming
          • Which of the following method is used for sorting in merge sort?
            • Merging
            • Partitioning
            • Selection
            • Exchanging
          • Which of the following sorting algorithms is the fastest?
            • Merge sort
            • Quick sort
            • Insertion sort
            • Bubble sort
          • Quick sort is an example of a sorting algorithm based on which strategy?
            • Dynamic programming
            • Greedy approach
            • Divide and conquer
            • Backtracking
          • Which of the following sorting algorithm adopts divide and conquer strategy
            • Insertion sort
            • Bubble sort
            • Merge sort
            • Selection sort
          • The running time of quick sort depends on the
            • No of input
            • Arrangement of element
            • Partitioning element
            • None of the above
          • What is the space complexity of an algorithm that creates a new array of size n?
            • O(1)
            • O(n)
            • O(log n)
            • O(n^2)
          • What will be the best-case time complexity of merge sort?
            • O(n log n)
            • O(n2)
            • O(n2 log n)
            • O(n log n2)
          • What is the worst-case time complexity of merge sort?
            • O(n * n)
            • O(n log n)
            • O(log n)
            • O(n)
          • What is the worst-case time complexity of a quick sort algorithm?
            • O(N)
            • O(N log N)
            • O(N2)
            • O(log N)
          • Strassen`s matrix multiplication is an algorithm that multiplies two matrices using which approach?
            • Brute force
            • Greedy approach
            • Dynamic programming
            • Divide and conquer
          • Time complexity of matrix chain multiplication problem is
            • O(n)
            • O(n2)
            • O(n3)
            • None of these
          • The time complexity of Kruskal’s algorithm is
            • O(logV)
            • O(E Log V)
            • O(V log E)
            • None of the above
          45. What defines a greedy algorithm?
          a.    An algorithm that tries every possible solution to find the best one.
          b.   An algorithm that makes the locally optimal choice at each step.
          c.    An algorithm that reconsiders previous decisions based on future choices.
          d.   An algorithm that uses backtracking to ensure all possibilities are covered.
          • Which of the following is a characteristic of greedy algorithms?
            • They are always the most efficient solution.
            • They can always backtrack to find the best solution.
            • They make a series of choices that are locally optimal, aiming for a global optimum.
            • They require complete knowledge of future decisions.
          • What can be a downfall of using a greedy algorithm for a particular problem?
            • They are too slow for large datasets.
            • They may not consider the overall problem, leading to suboptimal solutions.
            • They can only solve problems that can be expressed recursively.
            • They often require more memory than other algorithms.
          • In greedy method which type of solution is generated
            • Optimal solution
            • Worst solution
            • Best solution
            • All solutions
          • Why might a greedy algorithm not always produce an optimal solution?
            • Because it uses dynamic programming
            • Because it evaluates all possible choices at each step
            • Because it always makes the safest choice
            • Because it may make a choice that seems best at the moment but is not optimal overall
          • In which scenario is a greedy algorithm guaranteed to find the global optimum?
            • When the problem has overlapping subproblems and optimal substructure.
            • When the problem exhibits the property of “greedy choice property” and “optimal substructure.”
            • When the problem is NP-complete.
            • When the problem can be divided into smaller instances that can be solved independently.
          51. What is the "greedy choice property" in the context of greedy algorithms?
          a.    A global optimal solution can be arrived at by choosing the local optimum.
          b.   The choice made at each step is reversible.
          c.    The choice depends on choices made in previous steps.
          d.  Multiple choices are evaluated before making a decision.
           
          52. Which characteristic does a problem need to have for a greedy algorithm to be applicable?
          a.    The problem must be divisible into smaller independent subproblems.
          b.   The problem should allow a global optimal solution to be assembled from local optimal.
          c.    The problem requires the solution to consider future consequences of current decisions.
          d.   The problem must be solved in polynomial time.
           
          • What is the objective of the knapsack problem?
            • To Get Minimum Total Value in the Knapsack
            • To Get Maximum Total Value in the Knapsack
            • To Get Minimum Weight in the Knapsack
            • To Get maximum Weight in the Knapsack
          • In a knapsack problem, if a set of items are given, each with a weight and a value, the goal is to find the number of items that _____________ the total weight and the total value.
            • Maximizes, Maximizes
            • Minimizes, Minimizes
            • Maximizes, Minimizes
            • Minimizes, Maximizes
          • What is the objective of the 0/1 Knapsack Problem?
            • To maximize the total weight of the knapsack.
            • To maximize the total value of the knapsack.
            • To minimize the total weight of the knapsack.
            • To minimize the total value of the knapsack.
          • Which of the following problem has a greedy solution
            • 0-1 knapsack problem
            • Fractional knapsack problem
            • Coin change problem
            • Both (b) and (c)
          • What does the “0/1” in “0/1 Knapsack Problem” signify?
            • Each item can only be used once.
            • Each item can be divided into smaller parts.
            • Each item is available in unlimited quantities.
            • Each item has no value or weight.
          • Which approach is commonly used to solve the 0/1 Knapsack Problem?
            • Greedy algorithm
            • Dynamic programming
            • Depth-first search
            • Breadth-first search
          • What are the constraints of the 0/1 Knapsack Problem?
            • Items` weights and values are negative.
            • Knapsack`s capacity is unlimited.
            • Each item can only be chosen once, and the total weight must not exceed the knapsack`s capacity.
            • Each item can be chosen multiple times.
          • Which of the following algorithms is the best approach for solving Huffman codes?
            • exhaustive search
            • greedy algorithm
            • brute force algorithm
            • divide and conquer algorithm
          • In Huffman coding, data in a tree always occur?
            • Roots
            • Leaves
            • left sub trees
            • right sub trees
          • Which of the following approach should be used to find the solution of the activity selection problem?
            • Greedy approach
            • Divide and conquer
            • Brute-force approach
            • Dynamic programming
          • Which of the following is/are property/properties of a dynamic programming problem?
            • Require More Time
            • Evolutionary Approach
            • Optimal Substructure and Overlapping Sub problems
            • Greedy Approach
          • Which class includes decision problems that can be verified in polynomial time by a deterministic Turing machine, given a correct solution to the problem?
            • P
            • NP
            • NPC
            • NP-hard
          • Which statement best describes the NP class?
            • It contains problems that are solved and verified in non-polynomial time.
            • It includes problems that are solved in polynomial time and verified in non-polynomial time.
            • It includes problems whose solutions can be verified in polynomial time.
            • It includes only unsolvable problems.
          • What is the relationship between P and NP classes?
            • P and NP are equivalent and contain the same set of problems
            • P is a subset of NP
            • P and NP are completely disjoint sets
            • NP is a subset of P
          • Which of the following is a characteristic of an NP-Complete problem?
            • It is solvable in polynomial time.
            • It is both in NP and NP-Hard.
            • It cannot be verified or solved in polynomial time.
            • It has no known polynomial-time algorithm.
          • Which of the following statements is true regarding NP-complete problems?
            • They are the easiest problems in NP.
            • They are the hardest problems in NP.
            • They cannot be verified in polynomial time.
            • They do not belong to the class NP.
          • If a polynomial time algorithm is found for one NP-complete problem, what is the implication for other NP-complete problems?
            • They all remain NP-complete.
            • They all can also be solved in polynomial time.
            • They all become unsolvable.
            • No implications can be drawn.
          • Which of the following problems is a known NP-complete problem?
            • Binary search
            • Traveling Salesperson Problem (TSP)
            • Matrix multiplication
            • Calculating the greatest common divisor (GCD)
          Total Views: 19

          Leave a Comment