II CSE B DP

Which of the following is/are property/properties of a dynamic programming problem?

• Optimal substructure

• Overlapping subproblems

• Greedy approach

• Both optimal substructure and overlapping subproblems

If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property.

• Overlapping subproblems

• Optimal substructure

• Memoization

• Greedy

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________

• Dynamic programming

• Greedy

• Divide and conquer

• Recursion

When a top-down approach of dynamic programming is applied to a problem, it usually _____________

• Decreases both, the time complexity and the space complexity

• Decreases the time complexity and increases the space complexity

• Increases the time complexity and decreases the space complexity

• Increases both, the time complexity and the space complexity

Which of the following standard algorithms is not Dynamic Programming based?

• Bellman–Ford Algorithm for single source shortest path

• Floyd Warshall Algorithm for all pairs shortest paths

• 0-1 Knapsack problem

• Prim’s Minimum Spanning Tree

Which of the following problems should be solved using dynamic programming?

• Merge sort

• Binary search

• Longest common subsequence

• Quicksort

Dijkstra’s Algorithm is the prime example for ___________

• Dynamic programming

• Back tracking

• Branch and bound

• Greedy algorithm

Which of the following algorithms is the best approach for solving Huffman codes?

• greedy algorithm

• exhaustive search

• divide and conquer algorithm

• brute force algorithm

Which of the following is false about the Kruskal’s algorithm?

• It constructs MST by selecting edges in increasing order of their weights

• It is a greedy algorithm

• It uses union-find data structure

• It can accept cycles in the MST

Fractional knapsack problem is also known as __________

• 0/1 knapsack problem

• Continuous knapsack problem

• Divisible knapsack problem

• Non continuous knapsack problem