Which data structure is commonly used to implement the tabulation table in a bottom-up dynamic programming solution?
A linked list.
A stack.
An array or a matrix.
A binary tree.
Who is credited as the pioneer of dynamic programming?
Edsger W. Dijkstra
Donald Knuth
Richard Bellman
Alan Turing
Which of the following is a common technique for implementing memoization in a top-down dynamic programming solution?
Sorting the input data before processing.
Converting the problem into an iterative approach.
Employing a recursive function with a cache (like a dictionary or array) to store results.
Using a stack data structure.
What is the primary benefit of using a top-down dynamic programming approach (memoization) over a purely recursive approach?
It avoids redundant computations by storing and reusing previously calculated results.
It improves the asymptotic time complexity of all algorithms.
It reduces the need for complex data structures.
It eliminates the need for recursion entirely.
What does a recurrence relation in dynamic programming represent?
The final solution to the overall problem.
A technique for storing and retrieving previously computed results.
A formula for breaking down the problem into smaller, self-similar subproblems.
The base case of the recursive algorithm.
Which of these problems is well-suited for a top-down dynamic programming approach?
Finding the Fibonacci sequence.
Finding the shortest path in a directed acyclic graph.
Calculating the factorial of a number.
Sorting an array of integers in ascending order.
What is the core principle behind the bottom-up approach (tabulation) in dynamic programming?
Using recursion to break down the problem into smaller subproblems.
Applying a greedy algorithm to find a locally optimal solution at each step.
Solving the problem in reverse order of subproblems.
Building a table of solutions to subproblems, starting from the smallest subproblems and moving up.
Which of the following problems exhibits optimal substructure, making it suitable for a dynamic programming approach?
Checking if a given string is a palindrome.
Finding the shortest path between two nodes in a graph.
Finding the largest element in an unsorted array.
What is the role of a recurrence relation in dynamic programming?
It determines the order in which subproblems should be solved.
It expresses the solution to a problem in terms of solutions to its smaller subproblems.
It calculates the time complexity of the dynamic programming algorithm.
It defines a non-recursive solution to the problem.
What is the difference between memoization and tabulation in dynamic programming?
Memoization stores results in a table, while tabulation uses a recursive stack.
Memoization solves the problem top-down, while tabulation solves it bottom-up.
Memoization uses iteration, while tabulation uses recursion.
Memoization is less efficient than tabulation in terms of space complexity.