Dynamic Programming Basic Quiz

What is Dynamic Programming?

• A method for solving problems by dividing them into independent subproblems

• A technique used exclusively for sorting algorithms

• A method that solves problems by breaking them into overlapping subproblems and storing results

• A brute-force approach for optimization problems

Which of the following is a key property of problems solved using dynamic programming?

• Recursion

• Greedy choice

• Overlapping subproblems and optimal substructure

• Divide and conquer

Which approach is commonly used in dynamic programming?

• Top-down (Memoization)

• Bottom-up (Tabulation)

• Both a and b

• Neither a nor b

What is memoization in dynamic programming?

• A technique to store results of expensive function calls to avoid recomputation

• A method to sort elements efficiently

• A process of dividing a problem into smaller non-overlapping subproblems

• A technique to optimize memory allocation

Which of the following problems can be efficiently solved using dynamic programming?

• Traveling Salesman Problem

• Longest Common Subsequence

• 0/1 Knapsack Problem

• All of the above

What is the base case for computing Fibonacci numbers using dynamic programming?

• Fib(1) = 1, Fib(2) = 2

• Fib(0) = 1, Fib(1) = 1

• Fib(0) = 0, Fib(1) = 1

• Fib(0) = 1, Fib(1) = 0

Which of the following is the time complexity of computing the N-th Fibonacci number using dynamic programming (bottom-up approach)?

• O(2ⁿ)

• O(n)

• O(log n)

• O(n²)

What is the space complexity of computing the N-th Fibonacci number using the bottom-up dynamic programming approach?

• O(n)

• O(1)

• O(log n)

• O(2ⁿ)

Which approach provides the most efficient way to compute Fibonacci numbers in terms of time complexity?

• Recursive approach without memoization

• Dynamic programming (bottom-up)

• Using matrix exponentiation

• Both b and c

Which of the following statements about the Fibonacci sequence is true?

• It can only be computed recursively

• The iterative approach is faster than naive recursion

• Memoization increases time complexity

• The sequence always contains even numbers