What is the time complexity of the brute force approach for finding the longest common subsequence?

O(n * 2ⁿ)

Fill in the blank: The LCS problem possesses both properties of a Dynamic Programming problem: ______ and Overlapping Subproblems.

Optimal Substructure

True or False: The recursive implementation of the LCS problem has a time complexity of O(mn).

False. The naive recursive implementation has exponential time complexity.

What is the primary goal of the Matrix Chain Multiplication problem?

To find the most efficient way to multiply a given chain of matrices.

Riddle: I can be represented as a tree, and my cost is minimized through specific arrangements. What am I?

Minimum Spanning Tree (MST)

In the context of dynamic programming, what does the term 'memoization' refer to?

Storing the results of expensive function calls and reusing them when the same inputs occur again.

What is the significance of the Triangle Inequality in the context of the Traveling Salesman Problem?

It allows for the design of approximate algorithms that guarantee a solution no worse than twice the optimal.

Fill in the blank: The time complexity of the dynamic programming approach for the 0-1 Knapsack problem is ______.

O(N * W)

True or False: The Fibonacci series can be computed using a dynamic programming approach to reduce time complexity.

True.

What are the two main approaches used in dynamic programming?

Top-down and Bottom-up.

Riddle: I am a method of optimization, breaking problems into smaller pieces. What am I?

Dynamic Programming

In dynamic programming, what property indicates that a problem can be solved using optimal solutions of its subproblems?

Optimal Substructure

What is the main advantage of using the bottom-up approach in dynamic programming?

It avoids recursion, thus saving memory and preventing stack overflow.

Fill in the blank: The time complexity for the naive recursive approach to the Subset Sum problem is ______.

Exponential

True or False: The LCS problem has overlapping subproblems property.

True.

What does the term 'Optimal Substructure' imply in the context of dynamic programming problems?

The optimal solution can be constructed from optimal solutions of its subproblems.

What is the time complexity of the brute force approach to find the longest common subsequence?

O(n * 2ⁿ)