Dynamic programing 2

The solution for TSP problem using bitmask-DP has the complexity:

• N³

• N!*N

• N²*2^N

• 2^N*N

Which of following are a technique used to optimize DP?

(Multiple choices)

• Gradient descent

• Open and Close interval trick

• Knuth's Optimization

• max flow

What does dynamic programing want to optimize?

• Money

• Time complexity

• Memory

• Number of code line

What is overlapping subproblems ?

• A. It refers to the occurrence of subproblems that share common sub-subproblems during the computation.

• B. An other name of divide and conquer

• C. A property of problems where the optimal solution can be derived from the optimal solutions of its subproblems

• D. Don't know

Which problems can be solved by dynamic programing?

• Problems that can be solved using divide and conquer.

• Problems that can be solved recursively.

• Problems that have optimal substructure and overlapping subproblems.

• Problems that have optimal substructure or overlapping subproblems.

Which problems below can be solved by dp on tree?

• Find the shortest path between 2 vertices in a graph

• Find tree diameter

• Optimal binary search tree

• Finding minimum spanning tree

Tabulation is an approach in dynamic programming that involves:

• A. Storing computed solutions in a table or array.

• B. Using recursion to solve subproblems.

• C. Rearranging elements in a data structure.

• D. Finding the maximum or minimum value in a sequence.

Which of the following is an advantage of using dynamic programming?

• A. It guarantees the optimal solution for any problem.

• B. It is always faster than other algorithmic techniques.

• C. It reduces the complexity of solving a problem.

• D. It can solve any type of problem, regardless of its characteristics.

A dp algorithm can be used to solve all the greedy problems.

• True

• False

Which of the following standard algorithms is not Dynamic Programming based.

• Bellman–Ford Algorithm for single source shortest path

• Floyd Warshall Algorithm for all pairs shortest paths

• 0-1 Knapsack problem

• Prim's Minimum Spanning Tree