1.

What are the three different ways of representing a polynomial using arrays? Represent the following polynomials using any three different methods and compare their advantages and disadvantages. (i) 7x5 - 8x4 + 5x3 + x2 + 2x + 15 (ii) 3x100 5x55 - 10

Answer»

A general polynomial A(x) can be written as an Xn + an- n-1 + ...+a1x+a0 where an ≠0 then we can represent A(x)

1. As an ordered list of coefficients using a one dimensional array of length n+2, A=(n, an, an-1,…,a1, a0) , the first element is the degree of A followed by n+1 coefficients in order of decreasing exponent. So the given polynomial can be represented as

i. (5,7, -8,5,1,2,15)

ii. (100,3,0,0,0,0…(45 times), -5, 0,0,0…(55 times),-10) 

Advantage of this method is simple algorithms for addition and multiplication as we have avoided the need to explicitly store the exponent of each term. However there is a major disadvantage of this method and that is wastage of memory for certain polynomial like example (ii) because we are storing more zero values than non-zero values. 

2. As an ordered list where we keep only non-zero coefficient along with their exponent like (m,em-1,bm-1,em-2,bm-2,…,e0,b0) where first entry is the number of nonzero terms, then for each term there are two entries representing an exponentcoefficient pair. So the given polynomial can be represented as 

i. (6,5,7,4,-8,3,5,2,1,1,2,0,15)

ii. (3,100,3,55,-5,0,-10)

This method is solves our problem of wasted memory like what happened in example 2. 



Discussion

No Comment Found

Related InterviewSolutions