How does Dynamic Programming differ from a greedy algorithm?
Greedy algorithms make locally optimal choices, while Dynamic Programming considers all subproblems.
Dynamic Programming always results in a faster solution than a greedy algorithm.
Greedy algorithms always find the globally optimal solution.
Dynamic Programming cannot be used to solve problems that can be solved with a greedy algorithm.
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 eliminates the need for recursion entirely.
It reduces the need for complex data structures.
It avoids redundant computations by storing and reusing previously calculated results.
How does dynamic programming approach the problem of overlapping subproblems?
It uses heuristics to approximate the solutions to overlapping subproblems
It employs backtracking to explore all possible solutions to overlapping subproblems
It avoids overlapping subproblems altogether by breaking down the problem differently
It solves each subproblem only once and stores its solution for later reuse
Which of the following problems exhibits optimal substructure, making it suitable for a dynamic programming approach?
Sorting an array of integers in ascending order.
Finding the largest element in an unsorted array.
Checking if a given string is a palindrome.
Finding the shortest path between two nodes in a graph.
What is the difference between memoization and tabulation in dynamic programming?
Memoization uses iteration, while tabulation uses recursion.
Memoization solves the problem top-down, while tabulation solves it bottom-up.
Memoization is less efficient than tabulation in terms of space complexity.
Memoization stores results in a table, while tabulation uses a recursive stack.
What is the core principle behind the bottom-up approach (tabulation) in dynamic programming?
Solving the problem in reverse order of subproblems.
Building a table of solutions to subproblems, starting from the smallest subproblems and moving up.
Applying a greedy algorithm to find a locally optimal solution at each step.
Using recursion to break down the problem into smaller subproblems.
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 eliminates the need for recursion.
Dynamic programming reduces the time complexity from exponential to linear.
Dynamic programming improves the space complexity but does not affect the time complexity.
Catalan numbers have a closed-form solution, making dynamic programming unnecessary.
What does a recurrence relation in dynamic programming represent?
A formula for breaking down the problem into smaller, self-similar subproblems.
A technique for storing and retrieving previously computed results.
The base case of the recursive algorithm.
The final solution to the overall problem.
What is the role of a recurrence relation in dynamic programming?
It determines the order in which subproblems should be solved.
It calculates the time complexity of the dynamic programming algorithm.
It expresses the solution to a problem in terms of solutions to its smaller subproblems.
It defines a non-recursive solution to the problem.
What is the primary benefit of using memoization in dynamic programming?
Reducing the need for recursion
Eliminating the need for iteration
Avoiding redundant computations by storing and reusing results
Sorting data more efficiently