Software Development Exam  >  Software Development Tests  >  DSA in C++  >  Test: Dynamic Programming - 1 - Software Development MCQ

Test: Dynamic Programming - 1 - Software Development MCQ


Test Description

15 Questions MCQ Test DSA in C++ - Test: Dynamic Programming - 1

Test: Dynamic Programming - 1 for Software Development 2024 is part of DSA in C++ preparation. The Test: Dynamic Programming - 1 questions and answers have been prepared according to the Software Development exam syllabus.The Test: Dynamic Programming - 1 MCQs are made for Software Development 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Dynamic Programming - 1 below.
Solutions of Test: Dynamic Programming - 1 questions in English are available as part of our DSA in C++ for Software Development & Test: Dynamic Programming - 1 solutions in Hindi for DSA in C++ course. Download more important topics, notes, lectures and mock test series for Software Development Exam by signing up for free. Attempt Test: Dynamic Programming - 1 | 15 questions in 30 minutes | Mock test for Software Development preparation | Free important questions MCQ to study DSA in C++ for Software Development Exam | Download free PDF with solutions
Test: Dynamic Programming - 1 - Question 1

Which of the following best describes Dynamic Programming?

Detailed Solution for Test: Dynamic Programming - 1 - Question 1

Dynamic Programming is a method to solve complex problems by breaking them down into smaller, overlapping subproblems. It optimizes the solution by avoiding redundant calculations through the use of memoization or tabulation.

Test: Dynamic Programming - 1 - Question 2

What is the main advantage of using Dynamic Programming?

Detailed Solution for Test: Dynamic Programming - 1 - Question 2

Dynamic Programming can reduce the time complexity of a problem by reusing previously computed results. It eliminates redundant calculations, leading to faster execution and improved efficiency.

1 Crore+ students have signed up on EduRev. Have you? Download the App
Test: Dynamic Programming - 1 - Question 3

What is memoization in Dynamic Programming?

Detailed Solution for Test: Dynamic Programming - 1 - Question 3

Memoization is a technique used in Dynamic Programming to store the results of expensive function calls and reuse them when the same inputs occur again. It helps avoid redundant calculations and improves the overall performance of the algorithm.

Test: Dynamic Programming - 1 - Question 4

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

Detailed Solution for Test: Dynamic Programming - 1 - Question 4

The Fibonacci sequence is a classic example that can be efficiently solved using Dynamic Programming. By using memoization or tabulation, we can avoid redundant calculations and solve the Fibonacci sequence in linear time complexity.

Test: Dynamic Programming - 1 - Question 5

Which of the following is NOT a required characteristic for a problem to be solved using Dynamic Programming?

Detailed Solution for Test: Dynamic Programming - 1 - Question 5

While Dynamic Programming can be used in conjunction with a greedy approach, it is not a required characteristic for a problem to be solved using Dynamic Programming. Overlapping subproblems and optimal substructure are the main characteristics required for applying Dynamic Programming.

Test: Dynamic Programming - 1 - Question 6

What is the output of the following code?
#include <iostream>
using namespace std;

int fibonacci(int n) {
    int dp[n+1];
    dp[0] = 0;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

int main() {
    cout << fibonacci(6);
    return 0;
}

Detailed Solution for Test: Dynamic Programming - 1 - Question 6

The code calculates the 6th Fibonacci number using Dynamic Programming. The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, ... The function returns the 6th Fibonacci number, which is 8.

Test: Dynamic Programming - 1 - Question 7

What is the output of the following code?
#include <iostream>
using namespace std;

int knapsack(int W, int wt[], int val[], int n) {
    int dp[n+1][W+1];
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (i == 0 || w == 0)
                dp[i][w] = 0;
            else if (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];
}

int main() {
    int val[] = {60, 100, 120};
    int wt[] = {10, 20, 30};
    int W = 50;
    int n = sizeof(val)/sizeof(val[0]);
    cout << knapsack(W, wt, val, n);
    return 0;
}

Detailed Solution for Test: Dynamic Programming - 1 - Question 7

The code solves the 0-1 Knapsack problem using Dynamic Programming. Given weights and values of items, the knapsack function calculates the maximum value that can be obtained by selecting items with a total weight not exceeding W. In this case, the maximum value that can be obtained is 220.

Test: Dynamic Programming - 1 - Question 8

What is the output of the following code?
#include <iostream>
using namespace std;

int coinChange(int coins[], int n, int amount) {
    int dp[amount + 1];
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        dp[i] = INT_MAX;
        for (int j = 0; j < n; j++) {
            if (coins[j] <= i)
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
        }
    }
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    int coins[] = {1, 2, 5};
    int n = sizeof(coins)/sizeof(coins[0]);
    int amount = 11;
    cout << coinChange(coins, n, amount);
    return 0;
}

Detailed Solution for Test: Dynamic Programming - 1 - Question 8

The code calculates the minimum number of coins required to make a given amount using the coin change problem and Dynamic Programming. The coins available are {1, 2, 5}, and the amount to be made is 11. The minimum number of coins required to make 11 is 3.

Test: Dynamic Programming - 1 - Question 9

What is the output of the following code?
#include <iostream>
using namespace std;

int longestIncreasingSubsequence(int arr[], int n) {
    int dp[n];
    for (int i = 0; i < n; i++) {
        dp[i] = 1;
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j])
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] > maxLen)
            maxLen = dp[i];
    }
    return maxLen;
}

int main() {
    int arr[] = {3, 10, 2, 1, 20};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << longestIncreasingSubsequence(arr, n);
    return 0;
}

Detailed Solution for Test: Dynamic Programming - 1 - Question 9

The code calculates the length of the longest increasing subsequence in an array using Dynamic Programming. The array is {3, 10, 2, 1, 20}, and the longest increasing subsequence is {3, 10, 20}. The length of this subsequence is 3, which is the output of the function.

Test: Dynamic Programming - 1 - Question 10

What is the output of the following code?
#include <iostream>
using namespace std;

int editDistance(string word1, string word2) {
    int m = word1.length();
    int n = word2.length();
    int dp[m+1][n+1];
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = j;
            else if (j == 0)
                dp[i][j] = i;
            else if (word1[i-1] == word2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + min(dp[i][j-1], min(dp[i-1][j], dp[i-1][j-1]));
        }
    }
    return dp[m][n];
}

int main() {
    string word1 = "intention";
    string word2 = "execution";
    cout << editDistance(word1, word2);
    return 0;
}

Detailed Solution for Test: Dynamic Programming - 1 - Question 10

The code calculates the minimum number of operations required to transform one string into another using the edit distance problem and Dynamic Programming. The strings are "intention" and "execution". The minimum number of operations required to transform "intention" into "execution" is 5, which is the output of the function.

Test: Dynamic Programming - 1 - Question 11

What is the output of the following code?

```cpp
#include <iostream>
using namespace std;

int eggDrop(int eggs, int floors) {
    int dp[eggs + 1][floors + 1];
    for (int i = 1; i <= eggs; i++) {
        dp[i][1] = 1;
        dp[i][0] = 0;
    }
    for (int j = 1; j <= floors; j++)
        dp[1][j] = j;
    for (int i = 2; i <= eggs; i++) {
        for (int j = 2; j <= floors; j++) {
            dp[i][j] = INT_MAX;
            for (int x = 1; x <= j; x++) {
                int res = 1 + max(dp[i-1][x-1], dp[i][j-x]);
                dp[i][j] = min(dp[i][j], res);
            }
        }
    }
    return dp[eggs][floors];
}

int main() {
    int eggs = 2;
    int floors = 10;
    cout << eggDrop(eggs, floors);
    return 0;
}
```

Detailed Solution for Test: Dynamic Programming - 1 - Question 11

The code solves the Egg Dropping Puzzle using Dynamic Programming. Given the number of eggs and the number of floors, the eggDrop function calculates the minimum number of attempts required to find the critical floor (the highest floor from which an egg doesn't break). In this case, with 2 eggs and 10 floors, the minimum number of attempts required is 14.

Test: Dynamic Programming - 1 - Question 12

What is the output of the following code?
```cpp
#include <iostream>
using namespace std;

int lps(string str) {
    int n = str.length();
    int dp[n][n];
    for (int i = 0; i < n; i++)
        dp[i][i] = 1;
    for (int cl = 2; cl <= n; cl++) {
        for (int i = 0; i < n - cl + 1; i++) {
            int j = i + cl - 1;
            if (str[i] == str[j] && cl == 2)
                dp[i][j] = 2;
            else if (str[i] == str[j])
                dp[i][j] = dp[i+1][j-1] + 2;
            else
                dp[i][j] = max(dp[i][j-1], dp[i+1][j]);
        }
    }
    return dp[0][n-1];
}

int main() {
    string str = "BBABCBCAB";
    cout << lps(str);
    return 0;
}
```

Detailed Solution for Test: Dynamic Programming - 1 - Question 12

The code calculates the length of the longest palindromic subsequence in a given string using Dynamic Programming. The string is "BBABCBCAB". The longest palindromic subsequence is "BABCBAB", which has a length of 7.

Test: Dynamic Programming - 1 - Question 13

What is the output of the following code?
```cpp
#include <iostream>
using namespace std;

int maxSumSubsequence(int arr[], int n) {
    int dp[n];
    for (int i = 0; i < n; i++) {
        dp[i] = arr[i];
        for (int j = 0; j < i; j++) {
            if (arr[i] > arr[j] && dp[i] < dp[j] + arr[i])
                dp[i] = dp[j] + arr[i];
        }
    }
    int maxSum = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] > maxSum)
            maxSum = dp[i];
    }
    return maxSum;
}

int main() {
    int arr[] = {1, 101, 2, 3, 100};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << maxSumSubsequence(arr, n);
    return 0;
}
```

Detailed Solution for Test: Dynamic Programming - 1 - Question 13

The code calculates the maximum sum increasing subsequence in an array using Dynamic Programming. The array is {1, 101, 2, 3, 100}. The maximum sum increasing subsequence is {1, 2, 3, 100}, and the sum of this subsequence is 105.

Test: Dynamic Programming - 1 - Question 14

What is the output of the following code?
```cpp
#include <iostream>
using namespace std;

int coinChange(int coins[], int n, int amount) {
    int dp[amount + 1];
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = coins[i]; j <= amount; j++) {
            dp[j] += dp[j - coins[i]];
        }
    }
    return dp[amount];
}

int main() {
    int coins[] = {1, 2, 5};
    int n = sizeof(coins)/sizeof(coins[0]);
    int amount = 5;
    cout << coinChange(coins, n, amount);
    return 0;
}
```

Detailed Solution for Test: Dynamic Programming - 1 - Question 14

The code calculates the number of ways to make change for a given amount using a set of coins and Dynamic Programming. The coins available are {1, 2, 5}, and the amount to be made is 5. There are three ways to make change for 5: {1, 1, 1, 1, 1}, {1, 1, 1, 2}, and {5}.

Test: Dynamic Programming - 1 - Question 15

What is the output of the following code?
```cpp
#include <iostream>
using namespace std;

int maxSubarraySum(int arr[], int n) {
    int maxSum = arr[0];
    int currMax = arr[0];
    for (int i = 1; i < n; i++) {
        currMax = max(arr[i], currMax + arr[i]);
        maxSum = max(maxSum, currMax);
    }
    return maxSum;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << maxSubarraySum(arr, n);
    return 0;
}
```

Detailed Solution for Test: Dynamic Programming - 1 - Question 15

The code calculates the maximum sum subarray in an array using Kadane's algorithm and Dynamic Programming. The array is {-2, 1, -3, 4, -1, 2, 1, -5, 4}. The maximum sum subarray is {4, -1, 2, 1}, and the sum of this subarray is 8.

153 videos|115 docs|24 tests
Information about Test: Dynamic Programming - 1 Page
In this test you can find the Exam questions for Test: Dynamic Programming - 1 solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Dynamic Programming - 1, EduRev gives you an ample number of Online tests for practice

Top Courses for Software Development

153 videos|115 docs|24 tests
Download as PDF

Top Courses for Software Development