Who is credited as the pioneer of dynamic programming?
Donald Knuth
Richard Bellman
Edsger W. Dijkstra
Alan Turing
How does dynamic programming approach the problem of overlapping subproblems?
It solves each subproblem only once and stores its solution for later reuse
It avoids overlapping subproblems altogether by breaking down the problem differently
It employs backtracking to explore all possible solutions to overlapping subproblems
It uses heuristics to approximate the solutions to overlapping subproblems
Which characteristic of a problem suggests that dynamic programming might be a suitable approach?
The problem requires processing data in sorted order
The problem exhibits optimal substructure, where the optimal solution can be constructed from optimal solutions to subproblems
The problem involves traversing a tree data structure
The problem can be broken down into smaller, independent subproblems
Which of the following problems exhibits optimal substructure, making it suitable for a dynamic programming approach?
Finding the largest element in an unsorted array.
Checking if a given string is a palindrome.
Sorting an array of integers in ascending order.
Finding the shortest path between two nodes in a graph.
A problem can be solved using dynamic programming if it has:
Both overlapping subproblems and optimal substructure
Neither overlapping subproblems nor optimal substructure
Optimal substructure
Overlapping subproblems
Which data structure is commonly used to implement the tabulation table in a bottom-up dynamic programming solution?
A linked list.
A binary tree.
An array or a matrix.
A stack.
Which of these problems is well-suited for a top-down dynamic programming approach?
Finding the shortest path in a directed acyclic graph.
Finding the Fibonacci sequence.
Calculating the factorial of a number.
Why is dynamic programming often preferred over a purely recursive approach for problems with overlapping subproblems?
Recursion cannot solve problems with overlapping subproblems.
Dynamic programming avoids the function call overhead associated with recursion, leading to better time complexity.
Dynamic programming always uses less memory than recursion.
Dynamic programming is easier to implement and understand than recursion.
What is the core principle behind the bottom-up approach (tabulation) in dynamic programming?
Using recursion to break down the problem into smaller subproblems.
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.
What is the primary benefit of using a top-down dynamic programming approach (memoization) over a purely recursive approach?
It eliminates the need for recursion entirely.
It improves the asymptotic time complexity of all algorithms.
It reduces the need for complex data structures.
It avoids redundant computations by storing and reusing previously calculated results.