CSC 211 -Data Structures &

Algorithms

Arrays
 Arrays

• Array: a set of pairs (index and value)

• data structure
• For each index, there is a value
associated with that index.

• Representation
• implemented by using consecutive
memory.
 Arrays
 One Dimensional Array:

int A[10];

 Two dimensional Array:

int A[10][25];

3
 The Array as ADT
Objects: A set of pairs <index, value> where for each value of
index there is a value from the set item.

Index is a finite ordered set of one or more dimensions, for

example,

{0, … , n-1} for one dimension,

{(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)} for two

dimensions, etc.
 The Array ADT
 Methods:
 for all A  Array, i  index, x  item, j, size  integer
Array Create(j, list) ::= return an array of j dimensions where list is
a j-tuple (a structure containing multiple parts) whose kth element is the
size of the kth dimension. Items are undefined.

 Item Retrieve(A, i) ::= if (i  index) return the item associated with index
value i in array A
else return error
 Array Store(A, i, x) ::= if (i in index)
return an array that is identical to array A except the
new pair <i, x> has been inserted else return error
 Arrays in C
int list[5], *plist[5];

list[5]: five integers

list[0], list[1], list[2], list[3], list[4]
*plist[5]: five pointers to integers
plist[0], plist[1], plist[2], plist[3], plist[4]

implementation of 1-D array

list[0] base address = α
list[1] α + sizeof(int)
list[2] α + 2*sizeof(int)
list[3] α + 3*sizeof(int)
list[4] α + 4*size(int)
 Arrays in C (cont’d)

Compare int *list1 and int list2[5] in C.

Same: list1 and list2 are pointers.
Difference: list2 reserves five locations.

Notations:
 list2 = a pointer to list2[0]
 (list2 + i) = a pointer to list2[i] i.e (&list2[i])
*(list2 + i) = list2[i]
 Example

Example:
int one[] = {0, 1, 2, 3, 4}; //Goal: print out Address Contents
address and value
1228 0
void print1(int *ptr, int rows)
1230 1
{
printf(“Address Contents\n”);
1232 2
for (i=0; i < rows; i++) 1234 3
printf(“%8u%5d\n”, ptr+i, *(ptr+i)); 1236 4
printf(“\n”);
}
 Other Data Structures
Based on Arrays
•Note
• Arrays:

•Basic data structure

•May store any type of elements

 Other Data Structures Based on Arrays:
Polynomial ADT
Polynomials: defined by a list of coefficients and exponents
-degree of polynomial = the largest exponent in a polynomial

-In a MONOMIAL Term of the form

Axⁿ
A is the Coefficient of the term, x is the base and n is the exponent

For example, given the term 10x³ it is a monomial term of degree 3

with exponent 3 base x and coefficient 10

-Note: a monomial is a product of powers of variables with

nonnegative integer exponents,
Other Data Structures Based on Arrays:
Polynomial ADT

-An example of a single variable polynomial:

Polynomials A(X)=3X20+2X5+4,
B(X)=X4+10X3+3X2+1

Remark: the order/degree of this polynomial is 20

(look for highest exponent)
 Polynomial ADT

• A single variable polynomial can be

generalized as:
• Polynomial ADT (continued)

…This sum can be expanded to:

anxn + a(n-1)x(n-1) + … + a1x1 + a0

If you like, CExE + C(E-1)x(E-1) + … + C1x1 + C0

Notice the two visible data sets namely: (C

and E), where
C is the coefficient object [Real #].
 and E is the exponent object [Integer #].
 Polynomial ADT

By definition of a data types:

Why call it an Abstract Data Type (ADT)?

A set of values and a set of allowable
operations on those values.
We can now operate on this polynomial
the way we like…
 Polynomial ADT

What kinds of operations?

Here are the most common operations on a

polynomial:
• Add & Subtract
• Multiply
• Differentiate
• Integrate
• etc…
 Polynomial ADT

Why implement this?

• Calculating polynomial operations by hand
can be very cumbersome. Take
differentiation as an example:

d(23x9 + 18x7 + 41x6 + 163x4 + 5x + 3)/dx

= (23*9)x(9-1) + (18*7)x(7-1) + (41*6)x(6-1) + …

 Polynomial ADT

 How to implement this?

There are different ways of implementing the

polynomial ADT:

• Array (not recommended)

• Linked List (preferred and recommended)
• Watch out for the reason---
 Polynomial ADT
•Array Implementation:
• p1(x) = 8x3 + 3x2 + 2x + 6
• p2(x) = 23x4 + 18x - 3
p1(x) p2(x)

6 2 3 8 -3 18 0 0 23
0 1 2 3 0 1 2 3 4

Index represents
exponents
 Polynomial ADT
This is why arrays aren’t good to represent
polynomials:

• p3(x) = 16x21 - 3x5 + 2x + 6

6 2 0 0 -3 0 ………… 0 16

WASTE OF SPACE!
 Polynomial ADT
 Advantages of using an Array:

• only good for non-sparse polynomials.

• ease of storage and retrieval.

 Disadvantages of using an Array:

• have to allocate array size ahead of time.

• huge array size required for sparse
polynomials. Waste of space and runtime.
 Polynomial ADT
 Object: Polynomial.
 Operations:
 Boolean IsZero(poly)
::= return FALSE or TRUE.
 Coefficient Coeff(poly, expon)
::= return coefficient of xexpon
 Polynomial Add(poly1, poly2)
::= return poly1 + poly2
 Polynomial Subtract(poly1, poly2)
::= return poly1 - poly2

21
Polynomial ADT Operations
 Additions

#define MAXDEGREE 101

typedef struct {
int degree;
int coef[MAXDEGREE]
} polynomial;
 Polynomial ADT Operations
 Additions

polynomial addp(polynomial a, polynomial b)

{ polynomial c;

c.degree = max(a.degree, b.degree)

for (i=0; i<=MAXDEGREE; i++)
c.coef[i] = a.coef[i] + b.coef[i];

return c; Running time?

}

advantage: easy implementation

disadvantage: waste space when sparse
2nd Representation As Arrays

 Only represent non-zero terms

 Need to represent non-zero exponents and its

corresponding coefficients

24
 Polynomial Addition (2)
• Use one global array to store all
polynomials
A(X)=2X1000+1
B(X)=X4+10X3+3X2+1
Start_a finish_a start_b finishb avail

coef 2 1 1 10 3 1

exp 1000 0 4 3 2 0

0 1 2 3 4 5 6
 2nd Representation As Arrays
 In C:

typedef struct {
int coeff, exp;
} polynomial;

polynomial terms[MAX_TERMS];
int avail = 0;

 Comparisons of two representations:

 If polynomial sparse, 2nd repre. is better.
 If polynomial full, 2nd repre. is double size of 1st.

26
 Polynomial ADT
Methods:
functions:
for all poly, poly1, poly2  Polynomial, coef Coefficients, expon Exponents

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 Attach(poly,coef, expon) ::= if (expon  poly) return error
else return the polynomial poly
with the term <coef, expon>
inserted
 Polyomial ADT (cont’d)

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
 Matrix – Abstract Data Type (ADT)
 Object: Matrix.
col. 0 col. 1 col. 2
 dimension = #rows x #cols
-27 3 4 row 0
6 82 -2 row 1
A= 109 -64 11 row 2
12 8 9
 Operations: 48 27 47 row 3
row 4
 Matrix Transpose(matrixA)
::= return transpose of matrixA
 Matrix Add(matrixA, matrixB)
::= return (matrixA + matrix B)
 Matrix Multiply(matrixA, matrixB)
::= return (matrixA * matrixB)

29
Matrix Representation

 We use arrays to represent matrices.

 Use array a[M][N] to store a matrix A(M, N).

 Use a[i][j] to store A(i, j).

30
 Operations: Transpose & Add
 c transpose(a) // a: m x n matrix
for (i=0; i<rowA; i++) // O(m)
for (j=0; j<colA; j++) // O(n)
c[j][i]=a[i][j];
Running time = O(mn)
 c add(a, b) // a, b: m x n matrices
for (i=0; i<rowA; i++) // O(m)
for (j=0; j<colA; j++) // O(n)
c[i][j]=a[i][j]+b[i][j];

Running time = O(mn)

31
 Operations: Multiply
 c multiply(a, b) //a: m x n mat., b: n x p mat.
x
c: m x p mat. =

for (i=0; i<rowA; i++) { // O(m)

for (j=0; j<colB; j++) { // O(p)
sum=0;
for (k=0; k<colA; k++) // O(n)
sum += a[i][k]*b[k][j];
c[i][j]=sum;
}
}
Running time = O(mnp)
32
 Sparse Matrices
A sparse matrix is a matrix populated primarily with
zeros

E.g.
Sparse Matrices
 An example sparse matrix:

15 0 0 22 0 -15
0 11 3 0 0 0
A= 0 0 0 -6 0 0
0 0 0 0 0 0
91 0 0 0 0 0
0 0 28 0 0 0
 A lot of “zero” entries.
Thus large memory space is wasted.

 Could we use other representation to save

memory space ??
34
Representation for Sparse Matrices
 Use triple <row, col, value> to characterize an
element in the matrix.

 Use array of triples a[] to represent a matrix.

 row by row
 within a row, row col value

column by column a[0] 6 6 8

a[1 ] 0 0 15
a[2] 0 3 22
a[3] 0 5 -15
a[4] 1 1 11
a[5] 1 2 3
a[6] 2 3 -6
a[7] 4 0 91
a[8] 5 2 28
35
Representation for Sparse Matrices
 In C:

typedef struct {
int col, row, value;
} term;

term a[MAX_TERMS];

36
Operations: Transpose
 c transpose(a) // a: m x n matrix
//Algorithm 1:
for each row i {
take element (i, j, value) and
store it as (j, i, value).
} valuae
row col row col

a[0] 6 6 8 c[0] 6 6 value

8
 Eg. a[1 ]0 0 15 c[1 ]0 0 15
a[2] 0 3 22 c[2] 3 0 22
a[3] 0 5 -15 c[3] 5 0 -15
a[4] 1 1 11 c[4] 1 1 11
a[5] 1 2 3 c[5] 2 1 3
a[6] 2 3 -6 c[6] 3 2 -6
a[7] 4 0 91 c[7] 0 4 91
a[8] 5 2 28 c[8] 2 5 28 37
Sparse Matrices

col1 col2 col3 col4 col5 col6

row0
0 − 15

[ ]
15 0 0 22
row1
0 11 3 0 0 0
row2 0 0 0 − 6 0 0
row3 0 0 0 0 0 0
row4 91 0 0 0 0 0
row5
0 0 28 0 0 0
5*3 6*6
15/15 8/36

sparse matrix
data structure?
 Sparse Matrix ADT
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.
 Sparse Matrix ADT

Methods:
for all a, b  Sparse_Matrix, x  item, i, j, max_col,
max_row  index

Sparse_Marix Create(max_row, max_col) ::=

return a Sparse_matrix that can hold
up to max_items = max _row x max_col and whose
maximum row size is max_row and whose maximum
column size is max_col.
 Sparse Matrix ADT (cont’d)
Sparse_Matrix 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
Sparse_Matrix 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.
 Sparse Matrix Representation
(1) Represented by a two-dimensional array.
Sparse matrix wastes space.
(2) Each element is characterized by <row, col, value>.
Sparse_matrix Create(max_row, max_col) ::=

#define MAX_TERMS 101 /* maximum number of terms +1*/

typedef struct {
int col;
int row;
int value; The terms in A should be ordered
} term; based on <row, col>
term A[MAX_TERMS]
 Sparse Matrix Operations
• Transpose of a sparse matrix.
• What is the transpose of a matrix?

row col value row col value

a[0] 6 6 8 b[0] 6 6 8
[1] 0 0 15 [1] 0 0 15
[2] 0 3 22 [2] 0 4 91
[3] 0 5 -15 [3] 1 1 11
[4] 1 1 11 transpose [4] 2 1 3
[5] 1 2 3 [5] 2 5 28
[6] 2 3 -6 [6] 3 0 22
[7] 4 0 91 [7] 3 2 -6
[8] 5 2 28 [8] 5 0 -15
 Transpose a Sparse Matrix
(1) for each row i
take element <i, j, value> and store it
in element <j, i, value> of the transpose.

difficulty: where to put <j, i, value>?

(0, 0, 15) ====> (0, 0, 15)
(0, 3, 22) ====> (3, 0, 22)
(0, 5, -15) ====> (5, 0, -15)
(1, 1, 11) ====> (1, 1, 11)
Move elements down very often.

(2) For all elements in column j,

place element <i, j, value> in element <j, i, value>
Transpose of a Sparse Matrix (cont’d)
void transpose (term a[], term b[])
/* b is set to the transpose of a */
{
int n, i, j, currentb;
n = a[0].value; /* total number of elements */
b[0].row = a[0].col; /* rows in b = columns in a */
b[0].col = a[0].row; /*columns in b = rows in a */
b[0].value = n;
if (n > 0) { /*non zero matrix */
currentb = 1;
for (i = 0; i < a[0].col; i++)
/* transpose by columns in a */
for( j = 1; j <= n; j++)
/* find elements from the current column */
if (a[j].col == i) {
/* element is in current column, add it to b */