Test: Miscellaneous - 1 - Software Development MCQ

The Range Minimum Query (RMQ) problem is concerned with finding the ____________ element in a given range.

Which of the following tasks can be efficiently solved using Dynamic Programming?

Consider the following code:

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(5))
What is the output of the code?

Consider the following code:

def knapsack(W, wt, val, n):
    if n == 0 or W == 0:
        return 0
    if wt[n-1] > W:
        return knapsack(W, wt, val, n-1)
    else:
        return max(val[n-1] + knapsack(W-wt[n-1], wt, val, n-1), knapsack(W, wt, val, n-1))

weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack(capacity, weights, values, len(weights)))
What is the output of the code?

Consider the following code:

def min_coin_change(coins, amount):
    if amount == 0:
        return 0
    res = float('inf')
    for coin in coins:
        if amount - coin >= 0:
            sub_res = min_coin_change(coins, amount - coin)
            if sub_res != float('inf') and sub_res + 1 < res:
                res = sub_res + 1
    return res

coins = [1, 2, 5]
target_amount = 11
print(min_coin_change(coins, target_amount))
What is the output of the code?

Consider the following code:

def max_subarray_sum(arr):
    max_sum = float('-inf')
    current_sum = 0
    for num in arr:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

array = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(array))
What is the output of the code?

Consider the following code:

def longest_increasing_subsequence(nums):
    n = len(nums)
    lis = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
    return max(lis)

sequence = [10, 22, 9, 33, 21, 50, 41, 60, 80]
print(longest_increasing_subsequence(sequence))
What is the output of the code?

Consider the following code:

def count_paths(n, m):
    if n == 1 or m == 1:
        return 1
    return count_paths(n-1, m) + count_paths(n, m-1)

print(count_paths(3, 4))
What is the output of the code?

Consider the following code:

def binomial_coefficient(n, k):
    if k == 0 or k == n:
        return 1
    return binomial_coefficient(n-1, k-1) + binomial_coefficient(n-1, k)

print(binomial_coefficient(5, 2))
What is the output of the code?

Consider the following code:

def matrix_chain_multiplication(dims, i, j):
    if i == j:
        return 0
    min_ops = float('inf')
    for k in range(i, j):
        ops = matrix_chain_multiplication(dims, i, k) + matrix_chain_multiplication(dims, k+1, j) + dims[i-1] * dims[k] * dims[j]
        min_ops = min(min_ops, ops)
    return min_ops

dimensions = [5, 10, 3, 12, 5, 50, 6]
n = len(dimensions)
print(matrix_chain_multiplication(dimensions, 1, n-1))
What is the output of the code?

Consider the following code:

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount]

coins = [1, 2, 5]
target_amount = 11
print(coin_change(coins, target_amount))
What is the output of the code?

Consider the following code:

def knapsack_dp(W, wt, val, n):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                dp[i][w] = 0
            elif wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7
print(knapsack_dp(capacity, weights, values, len(weights)))
 

What is the output of the code?