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)
### Greedy Approach to Problem-Solving A Greedy Approach is a problem-solving strategy that makes the locally optimal choice at each stage with the hope of finding the global optimum. In other words, the algorithm makes the best choice at each step, assuming that this will lead to the best overall solution. ### Fractional Knapsack Problem The Fractional Knapsack Problem is a variation of the Knapsack Problem where we are allowed to take fractions of items. Given a knapsack with a certain weight capacity, the goal is to maximize the total profit by selecting a subset of items to pack, where each item can be included fractionally (i.e., we can take part of an item if needed). #### Formulating the Fractional Knapsack Problem as an Optimization Problem: - Objective: Maximize the total profit, \( P \), ______ ________ _____ _______ ____ _________ _____ _______ ______ _______.
___ ____ ___ ___ _______ _______ _______ ________ _____ ____ _____.
________ _____ _____ _____ ________ _________ _______ _________ __________ _________ _________ ________.
_____ ________ _______ ____ _________ ____ ___ _________ __________.
__________ ________ _____ __________ __________ ______ _______ ______.
________ ____ ________ __________ _________ _______ ______ _____.
_________ _________ _____ ____ ____ ___ ________ _________.
________ ______ ____ _______ ___ _______ ____ _______ __________ ___ _________.
___ _______ ______ ______ ________ ___ ________ _____.
____ _____ ______ ______ ___ ______ __________ ___ ________ ______ ___.
________ ___ ________ __________ __________ ________ _________ _________ ____ ___.
____ _________ ________ __________ ________.
________ ______ _____ _________ _______ __________.
__________ __________ _________ __________ _________ ______ _______.
_________ ___ __________ __________ _______ ________ ______ __________ __________ __________ _____.
___ _____ ____ ___ _______ ____ ______ _____ _________ _________ ________.
________ ________ __________ _________ _________ ____ _______ ______.
___ ___ ____ _________ _____ _______.
_________ ______ ________ __________ _________ ___ ___ ______ _____.
__________ _____ ________ ______ ____ ___ _____ ___ ________ ___.
_____ _________ ________ _________ ______ _________.
_____ _________ ____ ___ _______ __________ _________ ________ ____.
_______ __________ _____ _____ ______ _________.
_________ _______ _________ _____ ______ _____ _________ ______ _____ __________ _________ _________.
___ ______ ___ _____ ________ ____ __________ ___ __________ ______ ______ ______.
_____ ____ __________ _____ ___ ____ _________ ____ _______ ___ ________.
____ ______ _______ ______ ___ ______.
_______ ___ ______ _________ ____ ___.
_______ ___ _____ ______ ___ ________.
________ __________ _____ __________ _________ ________ ____ ___ _____ _______ ___ ______.
________ ___ ______ __________ ____ _______ _______ ____ _____.
___ ___ ____ _________ ________ ______ ______ ________ ________ ___ ____ ___.
_______ _____ ______ _________ ________ ___ ____ _______ ___ _______ ____.
________ ______ _________ __________ __________ _________ _____.
_______ _________ ________ __________ ___ _________ ________ __________.
________ ________ __________ ______ _______ ____ ___.
_______ _____ _______ _______ _______ _______ ________ _____ _________ ______ _____ ___.
____ ___ ____ _____ _____.
_______ ______ _______ _______ _____ _________ _________ _______ __________.
___ ___ ________ _______ ___ _____ __________.
___ _________ __________ _______ ________ ________.
______ ________ _________ ___ _____ ______ __________.
______ ________ ___ ______ __________ _____ _________ ______ _______ ____.
__________ _________ _____ __________ ________ _________ _________ _______ _____ ___.
___ ___ ______ __________ ______.
____ _________ ____ _______ ________ __________ __________ _______ ________ _____ _____ __________.
_________ ________ _____ _______ _____ _____ ______ ____ __________ _______.
_______ __________ _________ ____ _________.
_____ _________ ____ ________ ____.
______ _____ ______ _____ ______.
___ ________ __________ _________ ____ ____ ________ __________ _______ ______ ________.
__________ __________ ___ ______ ________.
______ ______ __________ ______ ____ _________.
_____ _____ _________ ________ _________ _____.
_________ ________ ___ ___ __________ _____ _________.
____ ________ __________ _________ ______.
________ ____ ____ _____ _________.
____ ___ _______ _________ _____ ____ ____ _______ _______ _____.
______ _____ ____ _____ ________ ______ __________ ______ ______.
________ ________ ______ ____ _______ _________.
____ __________ _____ ________ ______ _____ ________.
________ _________ _____ _______ ______ ____ ________ _________ ___.
_______ _____ ______ _____ ________ ___ ____ _____.
__________ ___ _______ _______ _______ __________ ___ __________ _________ _____.
___ ______ ______ _____ _____ _____ ___ ___ _________ __________ ___ ____.
______ ___ _____ ____ _________ ________ _________ ________ _____ __________ ___.
_________ _________ _________ _______ _______ _____.
_______ _______ ______ _________ ____ ____ ____ ________ ____ _____.
____ _________ _______ ___ __________ __________ _______ _____.
_________ ___ _______ _________ _____ ______ _________ ______ ____ __________ ____.
___ _____ _______ ____ __________ _________ _______.
______ _______ ____ ________ __________ _________.
____ __________ ____ ___ ___ _________ ________ _______ ________ ____ ________.
____ _________ _________ ________ ________ ______ ____ _____ ______ _______ ___.
__________ _______ ___ __________ _________ _______ ________ ____ ___ _________.
________ ________ _______ ______ _____ _______ _____ _________ ________ _______ __________ ____.
__________ _________ __________ _______ _____ __________ ______ ___ ___ ____ _______ __________.
________ _____ ___ ________ ________ __________.
__________ ____ _________ ____ __________ _____ ____ _________.
____ ____ _________ ______.
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.
What is the purpose of using Huffman Codes? Explain the steps of building a huffman tree. Design the Huffman codes for the following set of characters and their frequencies: a:15, e:19, s:5, d:6, f:4, g:7, h:8, t:10.
Graph Colouring Problem
3-CNF SAT
Consider the following Graph:
Figure 1: Graph for Problem 3(a) and 3(b)
a) Write the Kruskal’s algorithm and Prim’s algorithm to find the minimum cost
spanning tree of the graph given in Figure 1. Show all the steps of computation.
Also, compute the time complexity of both the algorithms.
b) In the Figure 1, find the shortest path from the vertex ‘a’ using Dijkstra’s shortest
path algorithm. Show all the steps of computation. Also, find the time complexity
of the algorithm.
c) What is dynamic programming? What is the principle of Optimality? Use the
dynamic programming approach to find the optimal sequence of chain
multiplication of the following matrices:
| Matrix | Dimension |
| A1 | 5 x 10 |
| A2 | 10 x 20 |
| A3 | 20 x 15 |
| A4 | 15 x 8 |
| A5 | 8 x 10 |
3-CNF SAT
State and explain the theorems for computing the bounds O, Ω and Θ. Apply these theorem to find the O-notation, Ω-notation and Θ-notation for the function: