Back to the 2024 paper
Similar questions
Design and Analysis of Algorithms Write short notes on the following: (i) Approximation algorithms. (ii) Why are they important in the context of NP-hard optimization problems? (iii) Describe how approximation algorithms can be applied to the Vertex Cover problem.20247mDesign & Analysis of AlgorithmsDiscuss what you mean by polynomial reduction.20232mDesign and Analysis of Algorithms What is the primary technique used to prove that a problem is NP-complete? (i) Divide and conquer (ii) Dynamic programming (iii) Polynomial-time reduction from a known NP-complete problem (iv) Space complexity calculation20242mFORMAL LANGUAGE & AUTOMATA THEORYWrite short notes on: NP-hard and NP-complete problems.20237m
PreviousAnswer the following: (i) Describe complexity classes P, NP, NP-complete, and NP-hard. (ii) State and explain Cook's Theorem. (iii) Why is it considered a foundational result in computational complexity theory?NextAnswer the following: (i) Describe randomized algorithms. (ii) Write the algorithm for randomized quick sort. (iii) Give the time complexity of randomized quick sort.