Assignment: Dynamic Programming | DSA in C++ - Software Development PDF Download

Multiple-Choice Questions (MCQs)

Q.1. Which of the following statements best describes dynamic programming?
(a) It is a design pattern used in object-oriented programming.
(b) It is an algorithmic technique used to solve problems by breaking them into overlapping subproblems.
(c) It is a method to analyze the time complexity of algorithms.
(d) It is a technique used to optimize space complexity in algorithms.

Ans. (b)

Q.2. Which of the following problems can be effectively solved using dynamic programming?

(a) Sorting a list of integers in ascending order.
(b) Finding the maximum element in an array.
(c) Calculating the Fibonacci sequence.
(d) Determining whether a number is prime or composite.

Ans. (c)

Q.3. Dynamic programming is based on which principle?

(a) Divide and conquer
(b) Greedy approach
(c) Backtracking
(d) Optimal substructure and overlapping subproblems

Ans. (d)

Q.4. What is the key idea behind dynamic programming?

(a) Memoization
(b) Recursion
(c) Tabulation
(d) Iteration

Ans. (c)

Q.5. Which of the following is NOT a characteristic of a problem that can be solved using dynamic programming?

(a) The problem can be divided into overlapping subproblems.

(b) The problem exhibits optimal substructure.

(c) The problem can be solved using a greedy approach.

(d) The problem has a recursive definition.

Ans. (c)

High Order Thinking Questions (HOTS):

Q.1. Explain the concept of memoization in dynamic programming.

Memoization is a technique in dynamic programming where the results of expensive function calls are stored and reused to avoid redundant calculations. It involves using a data structure (usually an array or a hash table) to store the computed values and checking if the value has already been computed before performing the calculation again.

Q.2. Discuss the difference between top-down and bottom-up approaches in dynamic programming.

Top-down and bottom-up are two approaches in dynamic programming. In the top-down approach, the problem is solved by breaking it down into smaller subproblems recursively and solving them by memoization. In the bottom-up approach, the problem is solved by solving the smallest subproblems first and building up to the larger problem iteratively.

Q.3. How can dynamic programming be used to solve the longest common subsequence problem?

The longest common subsequence problem can be solved using dynamic programming by building a table to store the lengths of the longest common subsequences of the prefixes of the two sequences. By filling the table from left to right and top to bottom, we can find the length of the longest common subsequence.

Q.4. When would you choose dynamic programming over other problem-solving techniques like divide and conquer or greedy algorithms?

Dynamic programming is chosen over other problem-solving techniques like divide and conquer or greedy algorithms when the problem can be divided into overlapping subproblems and has optimal substructure. It is particularly useful when the problem exhibits overlapping subproblems, and the same subproblems are solved multiple times.

Q.5. What are the key steps involved in solving a problem using dynamic programming?

The key steps involved in solving a problem using dynamic programming are as follows:

• Identify the problem that can be solved using dynamic programming.
• Break down the problem into smaller overlapping subproblems.
• Define the recurrence relation or formula to calculate the solution of the problem based on its subproblems.
• Determine the base cases or initial values.
• Choose between the top-down or bottom-up approach.
• Implement the solution using memoization or tabulation.
• Analyze the time and space complexity of the dynamic programming solution.

Fill in the Blanks

1. In dynamic programming, the process of storing the results of expensive function calls and reusing them is known as ____________.

memoization

2. Dynamic programming is often used to solve optimization problems that exhibit ____________ substructure.

optimal

3. The process of solving a problem by breaking it down into smaller overlapping subproblems and solving them once is called ____________.

memoization

4. Dynamic programming can be implemented using either a ____________ or a ____________ approach.

top-down, bottom-up

5. In dynamic programming, the time complexity can often be improved by using ____________ techniques.

optimization

True/False

1. Dynamic programming can only be used to solve problems that can be divided into subproblems.

True

2. Dynamic programming can be applied to problems that have optimal substructure but not overlapping subproblems.

False

3. Dynamic programming is an efficient technique for solving all types of problems.

False

4. The bottom-up approach in dynamic programming starts with the smallest subproblem and works towards the larger problem.

True

5. Memoization is a technique used to avoid redundant calculations in dynamic programming.

True

Hands-On Questions

Q.1. Write a dynamic programming solution in C++ to calculate the nth Fibonacci number.

#include <iostream>

using namespace std;

int fibonacci(int n) {

    int fib[n+1];

    fib[0] = 0;

    fib[1] = 1;

    for (int i = 2; i <= n; i++) {

        fib[i] = fib[i-1] + fib[i-2];

    }

    return fib[n];

}

int main() {

    int n;

    cout << "Enter the value of n: ";

    cin >> n;

    int result = fibonacci(n);

    cout << "The " << n << "th Fibonacci number is: " << result << endl;

    return 0;

}

Q.2. Implement a dynamic programming solution in C++ to find the length of the longest increasing subsequence in an array.

#include <iostream>

#include <vector>

using namespace std;

int longestIncreasingSubsequence(vector<int>& nums) {

    int n = nums.size();

    vector<int> dp(n, 1);

    for (int i = 1; i < n; i++) {

        for (int j = 0; j < i; j++) {

            if (nums[i] > nums[j]) {

                dp[i] = max(dp[i], dp[j] + 1);

            }

        }

    }

    int maxLength = 0;

    for (int i = 0; i < n; i++) {

        maxLength = max(maxLength, dp[i]);

    }

    return maxLength;

}

int main() {

    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};

    int length = longestIncreasingSubsequence(nums);

    cout << "The length of the longest increasing subsequence is: " << length << endl;

    return 0;

}

Q.3. Solve the 0/1 knapsack problem using dynamic programming in C++.

#include <iostream>

#include <vector>

using namespace std;

int knapsack(int W, vector<int>& weights, vector<int>& values) {

    int n = weights.size();

    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {

        for (int w = 1; w <= W; w++) {

            if (weights[i - 1] <= w) {

                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);

            } else {

                dp[i][w] = dp[i - 1][w];

            }

        }

    }

    return dp[n][W];

}

int main() {

    int W = 10;

    vector<int> weights = {2, 3, 4, 5};

    vector<int> values = {3, 4, 5, 6};

    int maxValue = knapsack(W, weights, values);

    cout << "The maximum value that can be obtained is: " << maxValue << endl;

    return 0;

}

Q.4. Write a C++ program to find the shortest path in a directed acyclic graph using dynamic programming.

#include <iostream>

#include <vector>

#include <climits>

using namespace std;

struct Edge {

    int source;

    int destination;

    int weight;

};

void shortestPathDAG(int source, vector<Edge>& edges, int V) {

    vector<int> dist(V, INT_MAX);

    dist[source] = 0;

    for (int i = 0; i < V - 1; i++) {

        for (auto edge : edges) {

            int u = edge.source;

            int v = edge.destination;

            int weight = edge.weight;

            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {

                dist[v] = dist[u] + weight;

            }

        }

    }

    cout << "Shortest distances from source " << source << ":\n";

    for (int i = 0; i < V; i++) {

        cout << "Vertex " << i << ": " << dist[i] << endl;

    }

}

int main() {

    int V = 6;

    vector<Edge> edges = {

        {0, 1, 2},

        {0, 4, 1},

        {1, 2, 3},

        {4, 2, 2},

        {4, 5, 4},

        {2, 3, 6},

        {5, 3, 1}

    };

    int source = 0;

    shortestPathDAG(source, edges, V);

    return 0;

}

Q.5. Implement the Floyd Warshall algorithm in C++ to find the shortest path between all pairs of vertices in a graph.

#include <iostream>

#include <vector>

#include <climits>

using namespace std;

void floydWarshall(vector<vector<int>>& graph) {

    int V = graph.size();

    vector<vector<int>> dist(V, vector<int>(V, INT_MAX));

    for (int i = 0; i < V; i++) {

        for (int j = 0; j < V; j++) {

            if (graph[i][j] != 0) {

                dist[i][j] = graph[i][j];

            }

        }

    }

    for (int k = 0; k < V; k++) {

        for (int i = 0; i < V; i++) {

            for (int j = 0; j < V; j++) {

                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && dist[i][k] + dist[k][j] < dist[i][j]) {

                    dist[i][j] = dist[i][k] + dist[k][j];

                }

            }

        }

    }

    cout << "Shortest distances between all pairs of vertices:\n";

    for (int i = 0; i < V; i++) {

        for (int j = 0; j < V; j++) {

            if (dist[i][j] == INT_MAX) {

                cout << "INF ";

            } else {

                cout << dist[i][j] << " ";

            }

        }

        cout << endl;

    }

}

int main() {

    int V = 4;

    vector<vector<int>> graph = {

        {0, 3, INT_MAX, 5},

        {2, 0, INT_MAX, 1},

        {INT_MAX, INT_MAX, 0, 2},

        {INT_MAX, INT_MAX, INT_MAX, 0}

    };

    floydWarshall(graph);

    return 0;

}