Which of these problems is typically NOT solved using dynamic programming?
Finding the longest common subsequence of two strings
Finding the convex hull of a set of points
Computing the edit distance between two strings
Solving the knapsack problem
Which data structure is commonly used to implement the tabulation table in a bottom-up dynamic programming solution?
A linked list.
A stack.
A binary tree.
An array or a matrix.
What is the fundamental principle behind dynamic programming?
Sorting data to find the optimal solution
Breaking down problems into smaller, overlapping subproblems
Always choosing the locally optimal choice
Using brute-force to explore all possible solutions
Which of the following is a common technique for implementing memoization in a top-down dynamic programming solution?
Converting the problem into an iterative approach.
Employing a recursive function with a cache (like a dictionary or array) to store results.
Sorting the input data before processing.
Using a stack data structure.
What is the primary purpose of memoization in dynamic programming?
To define the relationship between the problem and its subproblems.
To optimize space complexity by storing only the most recent subproblem results.
To avoid redundant computations by storing and reusing previously calculated results.
To reduce the need for recursion in the algorithm.
Which of the following best describes the principle of Dynamic Programming?
Finding the locally optimal solution at each step to reach a globally optimal solution.
Dividing a problem into smaller subproblems and solving each subproblem independently.
Solving a problem by storing and reusing solutions to overlapping subproblems.
Using probabilistic methods to approximate the solution to a problem.
What is the difference between memoization and tabulation in dynamic programming?
Memoization is less efficient than tabulation in terms of space complexity.
Memoization stores results in a table, while tabulation uses a recursive stack.
Memoization uses iteration, while tabulation uses recursion.
Memoization solves the problem top-down, while tabulation solves it bottom-up.
Which of the following is a real-world application of dynamic programming?
Sorting a list of customer names.
Sending an email.
Displaying a webpage in a web browser.
Finding the optimal strategy for playing a game of chess.
What is the primary benefit of using a top-down dynamic programming approach (memoization) over a purely recursive approach?
It reduces the need for complex data structures.
It improves the asymptotic time complexity of all algorithms.
It avoids redundant computations by storing and reusing previously calculated results.
It eliminates the need for recursion entirely.
Why is dynamic programming often preferred over a purely recursive approach for problems with overlapping subproblems?
Dynamic programming always uses less memory than recursion.
Dynamic programming is easier to implement and understand than recursion.
Recursion cannot solve problems with overlapping subproblems.
Dynamic programming avoids the function call overhead associated with recursion, leading to better time complexity.