Using Horner's rule, evaluate the polynomial p(x)= 2x5 -5x4 -3x2+15 at x=2. Analyse the computation time required for polynomial evaluation using Horner’s rule against the Brute force method.
Evaluation of Polynomial Using Horner's Rule
To evaluate the polynomial \( p(x) = 2x^5 - 5x^4 - 3x^2 + 15 \) at \( x = 2 \) using Horner's rule, we first rewrite the polynomial in Horner’s form:
\[ p(x) = 2x^5 - 5x^4 - 3x^2 + 15 \]
can be expressed as:
\[ p(x) = (((2x - 5)x - 3)x^2 + 15) \]
Now evaluate \( p(2) \) step-by-step:
1. Compute \( 2 \cdot 2 = 4 \).
2. Compute \( _______ ___ ___ _______ ____ _______ ______ ___ _________ ____ ___.
______ ____ ___ ______ ____ ______ ______ ___ ____ ______ ____.
_____ ______ _____ ______ ___ ___ __________ _____ _____ _____ ________ __________.
_________ __________ ___ ________ __________ ________ ____ ________ _________ ___ ________ __________.
_______ ____ ______ ______ _____ __________ _____.
_________ ______ ___ _______ ______ __________ ____ _____ ________ __________ _________.
_____ _____ ________ ______ ____ ___ ________ ____ ___ _____.
_______ ___ ____ __________ _____ _____ _______.
_________ ______ ___ __________ ______ ______ ______ __________ ________ _______.
_______ ________ _________ ____ ______ ________ ___ _________ ___.
___ _________ ___ ____ _____ __________ _________.
_____ __________ _________ ________ ________ __________ ____.
__________ _______ ______ ______ ______ ________ ___ _____.
_________ _____ ___ ________ __________ _____ __________.
___ ____ ____ ____ ________ _______.
________ ________ ______ __________ ______ _______ __________ __________ ________ _____.
_________ _______ __________ _________ _______ ___ ________ ___ __________ _______ _______ ________.
________ ____ ___ __________ ______ ___.
__________ __________ _______ _______ ______ _____.
______ _____ _______ ___ _______ _________ ______ ____.
______ _________ _____ _________ _____ ____ __________.
____ _________ ___ ____ ____ ______ ____ ______ ____.
____ __________ ________ ______ _________ _________ __________ ____ _________ ___ _______ __________.
_____ ___ ____ ___ __________ ___ _________.
____ ________ ________ _____ _________ ___ __________ ________ _______ ________.
__________ _____ ________ _______ _________ ________ _______.
____ ____ _________ ______ __________ _______ ____ ______ ______.
_______ ___ ___ ____ _________ _______ ____ __________ _______ _____ _________ ___.
_____ ____.
Get Full Answer on WhatsApp
Using Horner's rule, evaluate the polynomialAnalyse the computation time required for polynomial evaluation using Horner’s rule against the Brute force method.
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)
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 × 10 |
| A2 | 10 × 20 |
| A3 | 20 × 15 |
| A4 | 15 × 8 |
| A5 | 8 × 10 |
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.
3-CNF SAT
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
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: