GATE 2024 Algorithms Foundation Quiz 69

Consider two strings A= "associategate" and B= "gateassociate". Consider " x " to be the length of the longest common subsequence between A and B . The value of x+2^x is:

Which of the following statement(s) is/are true regarding the bellman ford algorithm?

Four matrices M₁, M₂, M₃ and M₄ of dimension p×q, q×r, r×s and s×t respectively can be multiplied. If p = 10, q = 100, r = 5, s = 50 and t = 1, then what is the minimum number of addition and multiplication require to multiple the matrices M₁, M₂, M₃ and M₄?

Which of the following problems can be solved using the longest subsequence problem?

Consider the matrix‐chain multiply problem for a subchain

A_iA_i+1 ..A_j

We want to parenthesize the chain to get the minimum number of scalar multiplications possible (call this operation Scal). We decide to split the subchain at location k, and parenthesize it there. Scal(i,j) is the therefore the number of scalar multiplications to compute the subproducts A_{i . . k} and A_{k + 1 . . j} , plus the cost to multiply these together. The dimensions of every A_i are d_{i – 1} × d_i , so the cost of multiplying these 2 matrices is d_{i – 1} × d_k × d_j. What is the recurrence relation for the Scal() operation?