1️⃣ What is the basic idea behind the Greedy Method?
The basic idea behind the Greedy Method is to make a series of choices, each of which looks best at the moment (locally optimal), with the hope that these local choices will lead to a globally optimal solution.
1️⃣ Explain the Job Sequencing with Deadlines problem in brief
The Job Sequencing with Deadlines problem schedules jobs to maximize profit, where each job has a deadline and profit.
Only one job can be executed at a time, and a job must finish before or on its deadline.
👉 The goal is to find the sequence of jobs that gives maximum total profit.
2️⃣ Difference between Fractional Knapsack and 0/1 Knapsack problem
| Basis | Fractional Knapsack | 0/1 Knapsack |
|---|---|---|
| Selection | Items can be taken in fractions | Items are taken fully or not at all |
| Type | Greedy approach | Dynamic programming / Backtracking |
| Time Complexity | O(n log n) | O(n × W) |
| Example | Taking part of gold bar | Taking full items only |
3️⃣ Define Minimum Cost Spanning Tree (MST) and give an example
A Minimum Cost Spanning Tree (MST) is a subset of edges that connects all the vertices in a weighted graph with minimum total edge cost and no cycles.
Example: Using Kruskal’s or Prim’s algorithm to find MST in a connected weighted graph.
4️⃣ What is Prim’s Algorithm, and how does it differ from Kruskal’s Algorithm?
-
Prim’s Algorithm: Builds the MST by starting from a single vertex and adding the smallest edge that connects a visited vertex to an unvisited one.
Kruskal’s Algorithm: Builds the MST by sorting all edges and adding them one by one (avoiding cycles).
