DS 4

Data Structures & Algorithms
Ahmad
Lecture 4
Abstract data type: Polynomial
• Polynomials A(X)=3X20+2X5+4, B(X)=X4+10X3+3X2+1
• Structure Polynomial is
• objects:
– a set of ordered pairs of <ei,ai> where ai in Coefficients and ei in Exponents, ei are
integers >= 0
• functions:
– for all poly, poly1, poly2 
• Polynomial, coef Coefficients, expon Exponents
– Polynomial Remove(poly, expon) ::= if (expon  poly) return the

polynomial poly with the term
whose exponent is expon deleted
else return error
– Polynomial SingleMult(poly, coef, expon) ::= return the polynomial

poly • coef • xexpon
– Polynomial Add(poly1, poly2) ::= return the polynomial

poly1 +poly2
– Polynomial Mult(poly1, poly2) ::= return the polynomial

poly1 • poly2
Abstract data type: Polynomial
• Polynomial Zero( ) ::= return the polynomial, p(x) = 0
• Boolean IsZero(poly) ::= if (poly) return FALSE

else return TRUE
• Coefficient Coef(poly, expon) ::= if (expon poly) return its coefficient else
return Zero
• Exponent Lead_Exp(poly) ::= return the largest exponent in poly

Polynomial Addition
• The first input array represents

– 7x^3 + 2x^2 + 5x^1 + 8
• The second array represents
– "2x^3 + 2x^2 + 4x^1"
• The output will be
– "9x^3 + 4x^2 + 9x^1 + 8"
Polynomial Addition
• Create a sum array sum[ ] of size equal to maximum of

'array 1' or 'array 2'
• Copy array1[ ] to sum[ ].
• Travers array2[ ] and do following for every element

array2[i]
– sum[i] = sum[i] + array2[i]
• Return sum[ ]
Polynomial Multiplication
• The first input array represents

– 5x^3 + 0x^2 + 10x^1 + 6
• The second array represents
– 7x^2 + 2x^1 + 4
• The output will be
Polynomial Multiplication
• Create a product array prod[ ] of size m+n-1.

• Initialize all entries in prod[ ] as 0
• Travers array1[ ] and do following for every element
array[i]
– Traverse array2[ ] and do following for every element array2[j]
• prod[i+j] = prod[i+j] + array1[i] * array2[j]
• Return prod[ ]
for (int i=0; i<m; i++)
{
for (int j=0; j<n; j++)
prod[i+j] += A[i]*B[j];
}
Multidimensional Array
• C++ allows an array to have more than one dimension.
• For example, a two-dimensional array consists of a certain number of
rows and columns:
– int NRow = 3;
– int NCol = 7;
– int Array[NRow][NCol];
0 1 2 3 4 5 6
0 4 18 9 3 -4 6 0
1 12 45 74 15 0 98 0
2 84 87 75 67 81 85 79
• Array[2][5] 3rd value in 6th column

Array[0][4] 1st value in 5th column
• The declaration must specify the number of rows and the number of columns.
Declaration & Initialization
• int Array1[2][3] = { {1, 2, 3} , {4, 5, 6} };

• int Array2[2][3] = { 1, 2, 3, 4, 5 };
• int Array3[2][3] = { {1, 2} , {4 } };
• If we printed these arrays by rows, we would find the following initializations

had taken place:
• Rows of Array1: for (int row = 0; row < 2; row++) {

• 123
• 456 for (int col = 0; col < 3; col++)
cout<<Array1[row][col]<<" ";
• Rows of Array2:
• 123 cout<<endl;
• 450 }
• Rows of Array3:
• 120
• 400
Sparse Matrix
• A matrix is implementation of a 2D array.
• If a lot of elements from a matrix have a value 0

then the matrix is known as SPARSE MATRIX.
Sparse Matrix
• If the matrix is sparse we must consider an

alternate way of representing it rather the normal
row major or column major arrangement.
– This is because if majority of elements of the matrix
are 0 then an alternative through which we can store
only the non-zero elements and keep intact the
functionality of the matrix can save a lot of memory
space.
Sparse Matrix
• A common way of representing non-zero elements of a sparse

matrix is 3-tuple form.
• In this form each non-zero element is stored in a row with the 1st
and 2nd element of this row containing the row and column in which
the element is present in the original matrix.
• the 3rd element in this row stores the actual value of the non-zero
elemt.
int k = 1,t = 0;
7 7 9
for( int i = 0 ; i < m ; i + +)
for( int j = 0 ; j < n ; j + + ) 0 3 -5
if(ASMatrix [ i ] [ j ] ! = 0 ) { 1 1 4
CSMatrix[ k ] [ 0 ] = i; 1 6 7
CSMatrix[ k ] [ 1 ] = j; 2 4 9
CSMatrix[ k ] [ 2 ] = ASMatrix[ i ] [ j ];
k++; 3 1 3
t++; 3 3 2
} 4 0 11
CSMatrix[ 0 ][ 0 ] = m; //number of rows 4 2 2
CSMatrix[ 0 ][ 1 ] = n; //number of columns
CSMatrix[ 0 ][ 2 ] = t; //total number of non-zero values 6 2 8
Sparse Matrix
• Objects
– a set of triples, <row, column, value>, where row and column are
integers and form a unique combination, and value comes from the
set item.
• Functions
– Create(max_row, max_col) ::= return a Sparse_matrix that
can hold up to
max_items = max _row max_col
and whose maximum row size is
max_row and whose maximum
column size is max_col.
– Transpose(a) ::= return the matrix produced by
interchanging the row and column
value of every triple.
Sparse Matrix
– Add(a, b) ::= if the dimensions of a and b are the
same return the matrix produced by
adding corresponding items, namely
those with identical row and column
values else return error
– Multiply(a, b) ::= if number of columns in a equals
number of rows in b return the matrix
d produced by multiplying a by b
according to the formula:
d [i] [j] = (a[i][k]•b[k][j]) where d (i, j)
is the (i,j)th element else return error.

DS 4

Uploaded by

Copyright:

Available Formats

DS 4

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DS 4

Uploaded by

Copyright:

Available Formats

Data Structures & Algorithms

– Polynomial Remove(poly, expon) ::= if (expon  poly) return the

– Polynomial SingleMult(poly, coef, expon) ::= return the polynomial

– Polynomial Add(poly1, poly2) ::= return the polynomial

– Polynomial Mult(poly1, poly2) ::= return the polynomial

• Polynomial Zero( ) ::= return the polynomial, p(x) = 0

• Boolean IsZero(poly) ::= if (poly) return FALSE

• Exponent Lead_Exp(poly) ::= return the largest exponent in poly

• The first input array represents

• Create a sum array sum[ ] of size equal to maximum of

• Copy array1[ ] to sum[ ].

• Travers array2[ ] and do following for every element

– sum[i] = sum[i] + array2[i]

• The first input array represents

• Create a product array prod[ ] of size m+n-1.

• Array[2][5] 3rd value in 6th column

• int Array1[2][3] = { {1, 2, 3} , {4, 5, 6} };

• If we printed these arrays by rows, we would find the following initializations

• Rows of Array1: for (int row = 0; row < 2; row++) {

• A matrix is implementation of a 2D array.

• If a lot of elements from a matrix have a value 0

• If the matrix is sparse we must consider an

• A common way of representing non-zero elements of a sparse

You might also like