CUET PG 2021 — Computer PYQ

Solution

Sahi jawab hai: Bellman-Ford Algorithm (ya koi bhi Dynamic Programming algorithm jaise 0/1 Knapsack ya Matrix Chain Multiplication).

Logic aur Explanation

Algorithmic paradigm ko samajhne ke liye hum niche di gayi equation aur categorization ka upyog kar sakte hain:

1. Greedy Algorithms ($\text{Local Optimum}=\text{Global Optimum}$):

Yeh algorithms har step par "greedy" choice karte hain. Inke pramukh udaharan hain:

• Dijkstra's Algorithm: Single source shortest path (non-negative weights).

• Prim's & Kruskal's: Minimum Spanning Tree (MST) banane ke liye.

• Huffman Coding: Data compression ke liye.

• Fractional Knapsack: Items ko tod kar store karne ke liye.

2. Non-Greedy (Dynamic Programming) ($\text{Global Search through Subproblems}$):

Bellman-Ford algorithm Greedy nahi hai kyunki yeh Dynamic Programming par aadharit hai. Yeh tab bhi kaam karta hai jab edges negative ho, jo Greedy approach nahi kar sakti.

Comparison Table

Algorithm	Type	Use Case
Dijkstra	Greedy	Shortest Path (Positive weights)
Prim's	Greedy	Minimum Spanning Tree
Kruskal's	Greedy	Minimum Spanning Tree
Bellman-Ford	Dynamic Programming	Shortest Path (Negative weights included)

Sahi Answer: Bellman-Ford Algorithm (ya jo bhi option Dynamic Programming ka diya gaya ho).