What are decision problems and Optimisation problems? Differentiate the decision problems and Optimisation problems with the help of at least two problem statements of each.
Decision problems and optimization problems are two fundamental types of computational problems in the field of Design and Analysis of Algorithms.
Decision Problems:
Decision problems involve determining whether a given input satisfies a certain property or condition. The answer to a decision problem is typically "yes" or "no." Here _________ ___ ___ ______ _____ __________.
_______ _________ _________ __________ ______ _______ ___ _____ __________.
_________ ________ ___ ________ _________ ____ _________ _________ _______ _________.
_______ _______ ___ ________ ________ ____ _________ ________.
_________ __________ ____ ______ ________ ________ _________.
______ __________ _______ _____ ______ _________ ____ _______ __________.
____ ___ ________ ___ __________ __________ ______ ___ _____ ________.
_________ _____ __________ ____ _________ ______ _______ ________ _____ ________.
____ __________ ___ ___ ______ _______ ___ __________ ___ ____ ______ ________.
______ ______ _______ ___ _____.
_______ _______ ____ __________ _______ _________ _________ _______ _______ ______ ____ ____.
____ __________ __________ _________ __________ _______ ___.
_________ ___ _______ ___ ___ ______ _____ _________ _______.
__________ _________ ______ ____ ____ ________ ______ _________ _________ _________ ___ __________.
_________ __________ ________ ________ _________.
_________ ______ ____ ____ ______ __________ ______ _______.
________ ___ ________ ______ _______ ______ _______ ___ _______ _______ ________ ______.
________ _______ _________ _____ _____ _____ _______ _____ ____ ________ ______.
______ _______ ________ __________ ______.
_____ _____ ____ ___ ____ _____.
________ ______ _____ _____ ___ ______ _______ _________.
________ _________ _________ _________ __________ __________.
____ _________ _________ ________ ___ ___ __________ ________ __________ ___ _________.
____ ____ ______.
Get Full Answer on WhatsApp
Explain the divide and conquer apprach of multiplying two matrices of large size. Also, explain the Strassen’s matric multiplication algorithm. Find the time complexity of both these approaches.
Write and explain the linear search algorithm and discuss its best and worstcase time complexity. Show the working of the linear search algorithm for the data: 12, 11, 3, 9, 15, 20, 18, 19, 13, 8, 2, 1, 16.
Using Horner's rule, evaluate the polynomialAnalyse the computation time required for polynomial evaluation using Horner’s rule against the Brute force method.
Vertex cover problem
What is a Greedy Approach to Problem-solving? Formulate the fractional Knapsack Problem as an optimisation problem and write a greedy algorithm to solve this problem. Solve the following fractional Knapsack problem using this algorithm. Show all the steps. Suppose there is a knapsack of capacity 15 Kg and 6 items are to packed in it. The weight and profit of the items are as under:
(p1, p2,…, p6) = (3, 2, 4, 5, 1, 6)
(w1, w2,…, w6) = (2, 1, 2, 1, 5, 1)
Vertex cover problem
What is the use of Topological sorting? Write and explain the Topological sorting algorithm. Also, compute the time complexity for the topological sorting algorithm.