DAA FINALS

What is the primary characteristic of a greedy algorithm?

• It always finds the globally optimal solution

• It uses backtracking to explore all possible solutions.

• It makes locally optimal choices at each step.

• It randomly selects choices without considering future consequences.

What does the Coin Change Problem involve?

• Finding the maximum number of coins needed to make change

• Selecting coins to maximize profit

• Finding the minimum number of coins needed to make a given amount of change

• Sorting coins in descending order based on their denominations

In job sequencing with deadlines, what is the goal of the greedy method?

• Minimize the number of jobs scheduled

• Maximize the total profit by respecting job deadlines

• Maximize the number of jobs completed after the deadline

• Randomly schedule jobs without considering deadlines

Which algorithm is used to find the minimum spanning tree of a graph by selecting edges based on their weights?

• Dijkstra's Algorithm

• Prim's Algorithm

• Kruskal's Algorithm

• Bellman-Ford Algorithm

Which algorithm is used to find the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights?

• Dijkstra's Algorithm

• Bellman-Ford Algorithm

• Floyd's Algorithm

• Prim's Algorithm

In Huffman coding, which elements are assigned shorter codes?

• Least frequent elements

• Elements with the longest codes

• Most frequent elements

• Randomly selected elements

What is the primary data structure used in implementing Heaps?

• Linked List

• Stack

• Priority Queue

• Hash Table

Which variant of the Knapsack Problem allows taking fractions of items?

• 0/1 Knapsack Problem

• Fractional Knapsack Problem

• Subset Sum Problem

• Job Sequencing Problem

How does Kruskal's Algorithm select edges to form the minimum spanning tree?

• It starts from a source vertex and expands outward.

• It adds the shortest available edge that does not form a cycle.

• It uses a priority queue to select edges with the smallest weights.

• It sorts edges in descending order based on their weights.

What does Warshall’s Algorithm compute for a directed graph?

• Shortest paths between all pairs of vertices

• Transitive closure, indicating reachability between all pairs of vertices

• Maximum flow in the graph

• Minimum spanning tree