DSBS-AN-31.01.2024

Consider two strings A = "qpqrr" and B = "pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.

• 33
• 23
• 43
• 34

Let A1, A2, A3, and A4 be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5, respectively. The minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix multiplication method is

• 1500
• 2000
• 200
• 100

What happens when a top-down approach of dynamic programming is applied to any problem?

• It increases both, the time complexity and the space complexity
• It increases the space complexity and decreases the time complexity.
• It increases the time complexity and decreases the space complexity
• It decreases both, the time complexity and the space complexity

The Fibonacci sequence is often used to illustrate dynamic programming concepts. What is the time complexity of a naive recursive implementation of Fibonacci numbers?

• O(1)
• O(log n)
• O(n)
• O(2^n)

time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}} time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}} entry_time[2] = {8, 10} exit_time[2] = {10, 7} num_of_stations = 4 For the optimal solution which should be the starting assembly line?

• Line 1
• Line 2
• All of the mentioned
• None of the mentioned

Consider the following array: {1, 3, 5, 8, 9, 2, 6, 7, 6} What is the minimum number of jumps required to reach the end of the array?

• 1
• 2
• 3
• 4

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}

Find the length of the longest increasing subsequence for the given sequence: {-10, 24, -9, 35, -21, 55, -41, 76, 84}

• 5
• 4
• 3
• 6

The number of increasing subsequences with the longest length for the given sequence are: {10, 9, 8, 7, 6, 5}

• 3
• 4
• 5
• 6

Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?

• 14
• 10
• 6
• 100