Scribd
Upload
42 views19 pages

CSCE 3110 Data Structures & Algorithm Analysis: Rada Mihalcea

Uploaded by

gopinukala

(1) Initialize the transpose matrix with the same number of rows and columns swapped (2) Iterate through each element in the original matrix and add the transpose element <column, row, value> (3) Order the elements in the transpose matrix based on the <row, column> to maintain sparsity

Copyright:

Attribution Non-Commercial (BY-NC)
Download as PPT, PDF, TXT or read online from Scribd
Download as ppt, pdf, or txt

CSCE 3110 Data Structures & Algorithm Analysis: Rada Mihalcea

Uploaded by

gopinukala
42 views19 pages
(1) Initialize the transpose matrix with the same number of rows and columns swapped (2) Iterate through each element in the original matrix and add the transpose element <column, row, value> (3) Order the elements in the transpose matrix based on the <row, column> to maintain sparsity

Original Title

Arrays

Copyright

© Attribution Non-Commercial (BY-NC)

Available Formats

PPT, PDF, TXT or read online from Scribd

Did you find this document useful?

Is this content inappropriate?

(1) Initialize the transpose matrix with the same number of rows and columns swapped (2) Iterate through each element in the original matrix and add the transpose element <column, row, value> (3) Order the elements in the transpose matrix based on the <row, column> to maintain sparsity

Copyright:

Attribution Non-Commercial (BY-NC)
Download as PPT, PDF, TXT or read online from Scribd
Download as ppt, pdf, or txt
42 views19 pages

CSCE 3110 Data Structures & Algorithm Analysis: Rada Mihalcea

Uploaded by

gopinukala
(1) Initialize the transpose matrix with the same number of rows and columns swapped (2) Iterate through each element in the original matrix and add the transpose element <column, row, value> (3) Order the elements in the transpose matrix based on the <row, column> to maintain sparsity

Copyright:

Attribution Non-Commercial (BY-NC)
Download as PPT, PDF, TXT or read online from Scribd
Download as ppt, pdf, or txt
You are on page 1/ 19

CSCE 3110

Data Structures &


Algorithm Analysis

Rada Mihalcea
http://www.cs.unt.edu/~rada/CSCE3110

Arrays
Arrays

Array: a set of pairs (index and value)

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

representation (possible)
implemented by using consecutive memory.
The Array 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.
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 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)
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] (&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
{
1232 2
printf(“Address Contents\n”);
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
•Arrays:
•Basic data structure
•May store any type of elements

Polynomials: defined by a list of coefficients and


exponents
- degree of polynomial = the largest exponent in a
polynomial

p( x )  a1 x e1  ...  an x en

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


Polynomial ADT
Objects: a set of ordered pairs of <ei,ai>
where ai in Coefficients and
ei in Exponents, ei are integers >= 0
Methods:
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
Polynomial Addition (1)
#define MAX_DEGREE 101
typedef struct {
int degree; Running time?
float coef[MAX_DEGREE];
} polynomial;

Addition(polynomial * a, polynomial * b, polynomial* c)


{
…
}
advantage: easy implementation
disadvantage: waste space when sparse
Polynomial Addition (2)
Use one global array to store all polynomials
A(X)=2X1000+1
B(X)=X4+10X3+3X2+1

starta finisha startb finishb avail

coef
2 1 1 10 3 1

exp
1000 0 4 3 2 0

0 1 2 3 4 5 6
Polynomial Addition (2) (cont’d)
#define MAX_DEGREE 101
typedef struct {
int exp; Running time?
float coef;
} polynomial_term;
polynomial_term terms[3*MAX_DEGREE];

Addition(int starta, int enda, int startb, int endb, int startc, int endc)
{
…
}
advantage: less space
disadvantage: longer code
Sparse Matrices
col1 col2 col3 col4 col5 col6
row0 15 0 0 22 0  15
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.

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  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 transpose [2] 0 4 91
[3] 0 5 -15 [3] 1 1 11
[4] 1 1 11 [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,
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 */

You might also like