15

19

کا

0501

OR
Give the different steps for finding the shortest path in the all-pair shortest path (6)
algorithm with a suitable example.
Module गा
Discuss the sum of subsets algorithm with the following cxample (6)

A= {1.2.4.6.8} , Find the all-possible combinations whose sum is equal to the
given value ۷ = 9

OR
Expisin the Branch and Bound algorithm used for solving a 8-puzzle problem (6)
Module [V
Discuss Complexity classes. Prove that Vector cover problem is NP Complete (6)
OR 3
Compute the maximum flow in the below network using Ford- Fulkerson (6)

Module ४
Explain the 2-Approximation algorithm for vertex cover und justify its (6)

approximation ratio

OR
What is Randomised Quick sort? Explain its working and why is it used (6)

+ 2 of 2