Advanced Design Techniques

• 
• 
• 

Which of the following is the correct definition of the optimal substructure of a problem?

• A way to rearrange problem parameters so that the data of problem is represented in the shortest form possible

• A set of all the subproblems that must be solved to construct a solution to the initial problem

• A set of all the optimal solutions to a problem

Which of the following strategies can be used to solve a 0-1 knapsack problem effectively?

• Brute force

• Dynamic programming

• Linear programming

• O(n^2)

• O(nW)

• O(n)

• O(n long W)

Is the solution to the knapsack problem unique?

• yes

• no

• Any knapsack problem has many solutions

When does a problem have the optimal substructure?

• When the problem solution can be optimally constructed from optimal solutions of its subproblems

• When the data structures of the problem are well organized

• When the fastest algorithm is used to solve the problem

Are subproblems less complex and smaller than the source problem when building substructures?

• yes

• No, there can be subproblems that have the same complexity as the source problem.

Are permutations of chars in source strings considered while detecting their LCS?

• Yes

• No

Why are an additional row and column used in a memorization table?

• To use more memory

• To make the solution algorithm more efficient

• 

How much memory is used to memorize the solutions to subproblems?

• O(m + n)

• O(m -n)

• O(mn)

• O(m long n)