DSA_Unit4

Which algorithmic paradigm follows the approach of making the locally optimal choice at each stage with the hope of finding a global optimum?

• Dynamic Programming

• Divide and Conquer

• Greedy Algorithm

• Backtracking

The Greedy Algorithm is useful for which of the following problems?

• 0/1 Knapsack Problem

• Fractional Knapsack Problem

• Longest Common Subsequence

• Matrix Chain Multiplication

Which of the following problems can be solved efficiently using a greedy algorithm?

• All-Pairs Shortest Path

• Job Sequencing with Deadlines

• Longest Common Subsequence

• Traveling Salesman Problem

In the Fractional Knapsack problem, the time complexity of the greedy approach is:

• O(n)

• O(n²)

• O(n log n)

• O(2ⁿ)

Which of the following statements is true about the 0/1 Knapsack problem?

• It can be solved optimally using the greedy method.

• It requires dynamic programming for an optimal solution.

• It can be solved in polynomial time using a greedy approach.

• It does not have a solution.

Which of the following problems does NOT use a greedy approach?

• Huffman Coding

• Kruskal’s Algorithm

• Bellman-Ford Algorithm

• Prim’s Algorithm

In Job Sequencing with Deadlines, the main objective is to:

• Maximize the number of jobs scheduled

• Minimize the number of jobs scheduled

• Minimize the completion time of jobs

• Maximize profit by scheduling jobs within their deadlines

Which algorithm is used for finding the Minimum Cost Spanning Tree?

• Dijkstra’s Algorithm

• Floyd-Warshall Algorithm

• Prim’s Algorithm

• Bellman-Ford Algorithm

Which of the following techniques is used in Huffman coding?

• Backtracking

• Greedy Algorithm

• Divide and Conquer

• Dynamic Programming

Kruskal’s Algorithm is used for:

• Finding the shortest path in a graph

• Constructing a minimum spanning tree

• Solving the All-Pairs Shortest Path problem

• Topological sorting of a graph