Dynamic Programming part 1

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

We use dynamic programming approach when

• We need an optimal solution

• The solution has optimal substructure

• The given problem can be reduced to the 3-SAT problem

• It's faster than Greedy

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

• True

• False

Dynamic programming problems require making a sequence of interrelated decisions, where each decision corresponds to one stage of the problem.

• True

• False

Time complexity of longest common sub string using DP is

• O(n*m)

• O(n+m)

• O(n/m)

• O(n-m)

Dynamic programming problems always have a finite number of states

• False

• True

Let two strings A="BanHocVoNguToi11Gio" and B="HocVoGiHocHoai".

Find LCS(A, B)

• 6

• 9

• 8

• 12

To compute LCS(A, B), we will return?

• f[lenA - 1][lenB - 1]

• f[lenA][lenB]

• f[lenA - 1][lenB]

• f[i - 1][j - 1]

Find the longest increasing subsequence for the given sequence:

{10, -10, 12, 9, 10, 15, 13, 14}

• {10, 12, 15}

• {10, 12, 13, 14}

• {-10, 12, 13, 14}

• {-10, 9, 10, 13, 14}

You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?

• 170

• 160

• 69

• 210