Explain the term Decision problem with the help of an example. Define the following problems and identify if they are decision problem or optimisation problem? Give reasons in support of your answer.

(i) Travelling Salesman Problem

(ii) Graph Colouring Problem

(iii) 0-1 Knapsack Problem

A decision problem is a problem where the answer is either "yes" or "no." It asks whether a specific condition or set of conditions holds for a given problem instance. In the context of algorithms, decision problems often involve checking whether a solution exists that satisfies certain criteria.

Example of a Decision Problem:

Consider the problem of determining whether there exists a subset of a given set of integers such that their sum is exactly equal to a given number. This is a decision problem because the answer is either "yes" _____ __________ _____ _______ ____ ___ ______ _______.
_________ ________ ______ __________ ____ ______ _______ _______.
________ _________ ___ ___ __________.
________ _______ _____ _______ ___.
________ __________ _________ ______ __________ _______ _______ _________.
___ __________ __________ _________ ____ ________.
______ ______ __________ ________ ____ ____ _______ ________ _____ ____.
__________ ______ _______ _________ _____ ________ _____ ______ ___ ______ _____.
__________ _________ _______ _____ ___ ___ _____ ______.
________ __________ _________ _________ ____ _______ ________ ________ ___ __________ _____ ____.
___ _________ ______ _________ ____ ________ ___ _________ ______ ____.
_________ _______ _______ ______ _______ ____ _____.
_________ _______ __________ __________ ________ ________ ____ ________ ________.
__________ __________ ________ ___ ___ _________ _______.
_____ ___ ________ ________ ___.
_______ _____ _____ ___ ____ _____ ___ _______ _________ ___ ______ ________.
________ ___ ___ ______ ____ _______ ______ ________ ____ _______ _____.
_________ _______ ___ ________ ____ ________ ________ ___ _________ _______ ___ ______.
___ ___ ________ ________ __________ ________ ___ __________ ___.
______ _______ _______ _________ __________ ________ ______.
__________ _____ __________ _________ _______ _________ ____ ____ ________ ________ ___ _____.
_________ ________ _____ ___ ______.
______ _________ _____ _______ ______ ______ ______ ________ _________.
____ _________ ___ ________ _________ _____ ____ _______ ________ ___ ________ _______.
_______ ______ _________ _______ _____ _____ ____ _______ ___.
________ ____ _______ ______ _________ __________.
__________ __________ ______ ______ ____ _____ _____ ________ ___ __________ _____.
_______ __________ _____ __________ ________ _____.
_____ _________ ____ ________ _____ ________ ______ ________ ____.
_______ _____ _______ _____ ____ __________ _______.
_____ _________ ____ __________ ____ _______ ___ ______ __________ ________.
__________ ____ ____ _________ _____ __________ ___ ___ ___.
___ _______ ________ __________ __________ ______.
_______ __________ ________ _____ _____ ________ __________ ______.
________ ______ ________ ___ _________ _____ _____ _____ _________ _______.
________ ____ _____ __________ ____ ______ ___ _________ _________ _______.
_________ _________ _________ _____ _______ ________ _________ _______.
______ ___ ______ ______ _______ _________ __________ ___ ____ ____ ______ _____.
_______ ____ _____ _______ ____ ___ ____ _____.
_____ __________ ___ __________ ______ ______.
_____ ________ ______ __________ ____ _______ _________ ___ __________ ________ ________ _____.
________ ____ __________ ________ _______ ___ _______ ______ ____ _________ _______.
Get Full Answer on WhatsApp