GATE Computer Science Engineering(CSE) 2027 Test: Dynamic Programing Free

Prim's Minimum Spanning Tree is a Greedy Algorithm. All other are dynamic programming based.

The time complexity of the above Dynamic Programming (DP) solution is O(n^2) and there is a O(N log N) solution for the LIS problem. We have not discussed the O(N log N) solution here as the purpose of this post is to explain Dynamic Programming with a simple example. See below post for O(N log N) solution. 

Option (D) is incorrect because Greedy algorithms are generally faster than Dynamic programming.

It is basically matrix chain multiplication problem. We get minimum number of multiplications using ((M1 X (M2 X M3)) X M4). Total number of multiplications = 100x20x5 (for M2 x M3) + 10x100x5 + 10x5x80 = 19000.

Kadane algorithm is used to find the maximum sum subarray in an array. It runs in O(n) time complexity. 

If we get the entry X[n, W] as true then there is a subset of {a1, a2, .. an} that has sum as W.

X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true 1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true. 2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j

The LCS is of length 4. There are 3 LCS of length 4 "qprr", "pqrr" and qpqr   A subsequence is a sequence that can be derived from another sequence by selecting zero or more elements from it, without changing the order of the remaining elements. Subsequence need not be contiguous. Since the length of given strings A = “qpqrr” and B = “pqprqrp” are very small, we don’t need to build a 5x7 matrix and solve it using dynamic programming. Rather we can solve it manually just by brute force. We will first check whether there exist a subsequence  of length 5 since min_length(A,B) = 5. Since there is no subsequence , we will now check for length 4. “qprr”, “pqrr” and “qpqr” are common in both strings. X = 4 and Y = 3 X + 10Y = 34

In Longest common subsequence problem, there are two cases for X[0..i] and Y[0..j]
1) The last characters of two strings match. 
   The length of lcs is length of lcs of X[0..i-1] and Y[0..j-1]
2) The last characters don't match.
   The length of lcs is max of following two lcs values
   a) LCS of X[0..i-1] and Y[0..j]
   b) LCS of X[0..i] and Y[0..j-1]

We have many ways to do matrix chain multiplication because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result of the matrix chain multiplication obtained will remain the same. Here we have four matrices A1, A2, A3, and A4, we would have: ((A1A2)A3)A4 = ((A1(A2A3))A4) = (A1A2)(A3A4) = A1((A2A3)A4) = A1(A2(A3A4)). However, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. Here, A1 is a 10 × 5 matrix, A2 is a 5 x 20 matrix, and A3 is a 20 x 10 matrix, and A4 is 10 x 5. If we multiply two matrices A and B of order l x m and m x n respectively,then the number of scalar multiplications in the multiplication of A and B will be lxmxn. Then, The number of scalar multiplications required in the following sequence of matrices will be : A1((A2A3)A4) = (5 x 20 x 10) + (5 x 10 x 5) + (10 x 5 x 5) = 1000 + 250 + 250 = 1500. All other parenthesized options will require number of multiplications more than 1500.

First we will pick item_4 (Value weight ratio is highest). Second highest is item_1, but cannot be picked because of its weight. Now item_3 shall be picked. item_2 cannot be included because of its weight. Therefore, overall profit by V_greedy = 20+24 = 44 Hence, V_opt - V_greedy = 60-44 = 16 So, answer is 16.

F₀₀(0) = 1, F₀₀(1) = 1 F₀₀(n) = 10 ∗ F₀₀(n – 1) + 100 F₀₀(2) = 10 * F₀₀(1) + 100 = 10 * 1 + 100 = 10 + 100 = 110 Similarly: F₀₀(3) = 10 * F₀₀(2) + 100 = 10 * 110 + 100 = 1100 + 100 = 1200 The sequence will be (1, 110, 1200).

So, (A) will be the answer.

Initially, We check for length 5 sub-sequence between both given sequences but couldn't find. Then checked for length 4 sub-sequences and CDBC and CDCB two sub-sequences found.

As the mentioned approach uses the memoization technique it always stores the previously calculated values. Due to this, the time complexity is decreased but the space complexity is increased.

Given problem is Subset-sum problem in which a set of non-negative integers, and a value sum is given, to determine if there is a subset of the given set with sum equal to given sum. With recursion technique, time complexity of the above problem is exponential. We can solve the problem in Pseudo-polynomial time using Dynamic programming. Refer: Subset Sum Problem Option (B) is correct