Which of these problems is typically NOT solved using dynamic programming?
Computing the edit distance between two strings
Solving the knapsack problem
Finding the convex hull of a set of points
Finding the longest common subsequence of two strings
Which of these problems is well-suited for a top-down dynamic programming approach?
Finding the shortest path in a directed acyclic graph.
Calculating the factorial of a number.
Finding the Fibonacci sequence.
Sorting an array of integers in ascending order.
Which of the following terms is NOT directly related to dynamic programming?
Tabulation
Optimal substructure
Divide and conquer
Memoization
Which of the following best describes the principle of overlapping subproblems in dynamic programming?
Storing and reusing the results of already solved subproblems.
Solving the same subproblems multiple times, leading to redundant computations.
Breaking down a problem into smaller, independent subproblems.
Finding the optimal solution without considering all possible solutions.
What is the core principle behind the bottom-up approach (tabulation) in dynamic programming?
Building a table of solutions to subproblems, starting from the smallest subproblems and moving up.
Using recursion to break down the problem into smaller subproblems.
Solving the problem in reverse order of subproblems.
Applying a greedy algorithm to find a locally optimal solution at each step.
What is the difference between memoization and tabulation in dynamic programming?
Memoization is less efficient than tabulation in terms of space complexity.
Memoization solves the problem top-down, while tabulation solves it bottom-up.
Memoization uses iteration, while tabulation uses recursion.
Memoization stores results in a table, while tabulation uses a recursive stack.
What does a recurrence relation in dynamic programming represent?
A technique for storing and retrieving previously computed results.
The base case of the recursive algorithm.
A formula for breaking down the problem into smaller, self-similar subproblems.
The final solution to the overall problem.
The computation of the nth Catalan number can be efficiently performed using dynamic programming. What is the primary advantage of employing dynamic programming in this scenario?
Dynamic programming improves the space complexity but does not affect the time complexity.
Dynamic programming eliminates the need for recursion.
Catalan numbers have a closed-form solution, making dynamic programming unnecessary.
Dynamic programming reduces the time complexity from exponential to linear.
What is the primary benefit of using a top-down dynamic programming approach (memoization) over a purely recursive approach?
It improves the asymptotic time complexity of all algorithms.
It reduces the need for complex data structures.
It eliminates the need for recursion entirely.
It avoids redundant computations by storing and reusing previously calculated results.
Which of the following problems exhibits optimal substructure, making it suitable for a dynamic programming approach?
Finding the shortest path between two nodes in a graph.
Checking if a given string is a palindrome.
Finding the largest element in an unsorted array.