Advanced Data Structure and Algorithm Analysis CT-5 Remedial

Which of the following methods can be used to solve the Knapsack problem?

• Brute force algorithm

• Recursion

• Dynamic programming

• Brute force, Recursion and Dynamic Programming

The 0-1 Knapsack problem can be solved using Greedy algorithm.

• True

• False

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

What are the different techniques to solve dynamic programming problems:

• Memoization

• Bottom-Up

• Both

• None

What is memoization in the context of dynamic programming?

• A technique to write memory-efficient programs.

• A way to avoid solving subproblems by storing their solutions and reusing them.

• A process of converting recursive algorithms into iterative ones.

• A method of analyzing the time complexity of algorithms.

The time complexity of solving the 0-1 Knapsack Problem using dynamic programming with a bottom-up approach (tabulation) is:

• O(n)

• O(n log n)

• O(n * capacity)

• O(n * capacity^2)

The Knapsack problem is an example of ____________

• Greedy algorithm

• 2D dynamic programming

• 1D dynamic programming

• Divide and conquer

In which of the following cases will the edit distance between two strings be zero?

• When one string is a substring of another

• When the lengths of the two strings are equal

• When the two strings are equal

• The edit distance can never be zero

Which of the following problems is NOT solved using dynamic programming?

• 0/1 knapsack problem

• Matrix chain multiplication problem

• Edit distance problem

• Fractional knapsack problem

Placing n-queens so that no two queens attack each other is called?

• n-queen’s problem

• 8-queen’s problem

• Hamiltonian circuit problem

• subset sum problem