ARRAYS

2.1 Array and Structures : 

2.1 Arrays 2.1.1 The ADT 2.1.2 Arrays in C 2.2 Dynamically Allocated arrays 2.2.1 One Dimensional array 2.2.2 Two Dimensional array 2.3 Structures and Unions 2.3.1 Structures 2.3.2 Unions 2.3.3 Internal Representations of structures 2.3.4 Self referential Structures 2.4 Polynomials 2.4.1 The ADT 2.4.2 Polynomial Representation 2.4.3 Polynomial addition Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.1 Array and Structures

PowerPoint Presentation: 

2.5 Sparse Matrix 2.5.1 The ADT 2.5.2 Sparse Matrix Representation 2.5.3 Transposing a Matrix 2.5.4 Matrix Multiplication 2.6 Representation of Multidimensional Arrays Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Array ……: 

To dress or decorate especially in splendid or impressive attire : To set or place in order To arrange or display Example: She arrayed herself in rich velvets and satins . Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Array ……

PowerPoint Presentation: 

In Computer Science An arrangement of memory elements in one or more planes . Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Why Arrays ?: 

Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Why Arrays ? Think There are 1000 voters

PowerPoint Presentation: 

Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Fruits[4] Why Arrays ? 0 1 2 3 2000 2002 2004 2006 Memory Addressees

PowerPoint Presentation: 

Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore people[5] 10 20 30 40 50 1002 1004 1006 1008 1010 Similar data type

Dissimilar Type : 

struct anna { }; Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Dissimilar Type

All about Array: 

Lets you associate one name with a lot of variables of same type An array in C Programming Language can be defined as number of memory locations, each of which can store the same data type and which can be references through the same variable name. An array is a collective name given to a group of similar quantities. Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore All about Array

What is a subscript in array?: 

The individual elements of an array are referenced by appending a subscript , in square brackets, behind the name. The subscript itself can be any legitimate C expression that yields an integer or any other value Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore What is a subscript in array?

Array Declarations: 

Syntax for creating an array data_type varname [int size]; If the size is not defined a default size of the array is taken by the compiler which is sufficient for most purposes. Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Array Declarations

Default Values : 

void main() { int arr[4] = { 1, 2 }; for ( int i=0; i<4; ++i) printf("The Values of %d=%d\n", i, arr[i]); getch(); } Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Default Values

PowerPoint Presentation: 

Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Declaration of an Array : 

type variable_name[size_of_the_array]; double height[10]; float width[20]; int min[9]; char name[20]; Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Declaration of an Array

2.1.1 The Abstract Data Type: 

Everybody we define array as “ Consecutive set of memory locations” This is unfortunate.. Array is set of pairs <index, value> Each index that is defined has a value associated with it . In mathematics we call as mapping Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.1.1 The Abstract Data Type

2.1 ADT array : 

Array is : Set of <index, values> where for each value of index there is a value from the set item Index is finite ordered set of one or more dimension For Example A[2][2].. A[0,0],A[0,1],A[1,0],A[1,1] for a 2 dimensions Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.1 ADT array

Functions: 

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 i th element is the size of the ith dimension Item Retrieve(A,i)::= If (i∈ index) return the item associated with index value I in array Array Store(A,i,x)::= if (i is in index) return an array that is indicated to array A else return error Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Functions

Concluding remarks about array as ADT : 

The advantage of this ADT definition is that it clearly points out the fact that the array is a more general structure than a consecutive locations Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Concluding remarks about array as ADT

2.1.2 Arrays in C : 

One dimensional array in C Int lalu[5], *balu[5]; Declares two arrays each containing five elements First array defines array of five integer Second array defines array of pointers Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.1.2 Arrays in C

Array Internals: 

Implementations of One Dimensional arrays In the above example lalu[5] creates storage for 5 integers. Each memory location is large enough to hold the single integer The address of the first location is called base address We calculate the address of the location like this.. α +i*sizeof(int) where α is the base address . Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Array Internals

How array treated in C ?: 

In C, array parameters are treated as pointers. Array parameters treated as pointers because of efficiency . It is inefficient to copy the array data in terms of both memory and time; and most of the times, when we pass an array our intention is to just tell the array we interested in, not to create a copy of the array. Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore How array treated in C ?

/* Program to illustrate Array and its addresses */: 

#include< stdio.h > #include< conio.h > void main() { int chintu [5]={4,5,6,7,8}; int i ; clrscr (); for( i =0;i<5;i++) { printf ("Hey I am %d = “, chintu [ i ]); printf (" Stored at the address %u\ n",&chintu [ i ]); } printf ("I think You learned about me how I store the nos..\n"); getch (); } Example Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore /* Program to illustrate Array and its addresses */

2.2Dynamically Stored Arrays..: 

Allocation of memory during runtime for a given array Why these are required ? Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.2Dynamically Stored Arrays..

PowerPoint Presentation: 

2.2.1 One Dimensional Array The dynamic array is an array data structure which can be resized during runtime which means elements can be added and removed The expression (int*)malloc(n*sizeof (int)) stores the number of elements in the memory. The malloc is basically used for memory allocation. Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Declaring one dimensional array for dynamic allocation: 

int *ar; Example Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Declaring one dimensional array for dynamic allocation

Two Dimensional Arrays… Dynamically allocation: 

C uses so-called array of arrays representation to represent a multidimensional array. In this representation, a two dimensional array is represented as one Declaration: int **a; Example Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Two Dimensional Arrays… Dynamically allocation

Reallocation Of Memory Dynamically : 

realloc ; function is used to to reallocate the memory dynamically Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Reallocation Of Memory Dynamically

PowerPoint Presentation: 

void main() { int *a; int i,n; int *b,n2; clrscr(); printf("Enter the size..\n"); scanf("%d",&n); a=(int *)malloc(n*sizeof(int)); printf(" Enter the new size...\n"); scanf("%d",&n2); a = (int *) realloc(a,n2*sizeof(int)); printf("Enter the numbers...\n"); for(i=0;i<n2;i++) scanf("%d",&a[i]); printf(" The Array Elements are....\n"); for(i=0;i<n2;i++) printf("%d\n",a[i]); } Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Structures in C : 

Structures in C defines the group of contiguous (adjacent) fields, such as records or control blocks. A structure is a collection of variables grouped together under a single name. It provides an elegant and powerful way for keeping related data together. A structure contains an ordered group of data objects. Unlike the elements of an array, the data objects within a structure can have varied data types. Each data object in a structure is a member or field. [IBM] Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Structures in C

2.3 Structures and Unions: 

Defining structure General Syntax and Example What is Structure variable Methods of declaring structure variable Initializing members of the structures Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.3 Structures and Unions

General Format of a Structure : 

struct tag_name { datatype1 member1; datatype1 member2; datatype1 member3; }; Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore General Format of a Structure Members of the structures

Example : 

Struct student { char name[20]; int rno; char college[20]; }; Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Example Members of the structures Name of the structure Keyword

What is Structure Variable?: 

A variable which is used to access the members of the structure Variable used to initialize the members of the structure Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore What is Structure Variable?

Declaring Structure Variable: 

struct student { char name[20]; int rno; char collegename[20]; float score; } s1,s2; Here s1 and s2 are called as structure variables Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Declaring Structure Variable

Method 2 : 

struct student { char name[20]; int rno; char collegename[20]; float score; } ; struct student s1,s2; here s1 and s2 are the two structure variables Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Method 2

Method 3: 

struct student { char name[20]; int rno; char collegename[20]; float score; } ; main() { struct student s1,s2; } Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Method 3

Accessing Members of the Structure: 

dot (.) operator is used selection operator -> Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Accessing Members of the Structure

Method 1 : 

struct student { char name[20]; int rno; } s1={“sachin”,34}; Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Method 1

Method 2: 

struct student { char name[20]; int rno; }; struct student s1={“sachin”,34}; Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Method 2

PowerPoint Presentation: 

Method 3 struct student { char name[20]; int rno ; } main() { struct student s1={“sachin”,34}; } Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Rules to be followed while using intializing Structures: 

We cannot initialize individual members of the structure inside the structure template The order of values enclosed in braces must match the order of members in the structure definition It is permitted to have a partial initialization . The uninitialized members will be assigned default values. Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Rules to be followed while using intializing Structures

What is typedef in C?: 

The C language provides a facility called typedef for creating synonyms[ aliasing] for previously defined data type names. For example, the declaration: A typedef can be used to eliminate the need for the struct key word in C. typedef int mint; mint a,b; // a and b are declared as two integers Int data type is renamed as mind This kind of declaration of data type is user defined data type Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore What is typedef in C?

PowerPoint Presentation: 

Example to illustrate typedef #include< stdio.h > typedef struct { int a; float b; } st ; st k={2,4.5}; void main() { printf ("% d%f",k.a,k.b ); } Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Example to Illustrate initialize the values for the members… assigning one variable to other and we can comapre : 

Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Example to Illustrate initialize the values for the members… assigning one variable to other and we can comapre #include<stdio.h> struct name { char name[20]; int rno; }s1={"anil",12}; void main() { struct name s2; s2=s1; if(s2.rno==s1.rno) { printf(" We are similar \n"); printf("%s3%d",s1.name,s1.rno); printf("%s3%d",s2.name,s2.rno); } }

2.3.2 Why Unions ?: 

This can save memory if you have a group of data where only one of the types is used at a time. Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.3.2 Why Unions ?

Real-time Examples for Union; U r sharing these but only one at a time…. : 

Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Real-time Examples for Union; U r sharing these but only one at a time….

2.3.2 Unions : 

Like a structure, a union is also a user defined data type. Concept borrowed from structures, hence syntax is similar to structures The members of a union share a single storage space. Only ONE member of each union can be referenced at a time. Amount of space allocated for storage is the amount needed for the largest member of the union . Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.3.2 Unions

Some Points on Unions…: 

Sizeof union is size of its biggest member Unions most often contain different types of structures Can only initialize first member of union Can assign (copy) one union variable to another Can pass union or pointer to union as function argument Function can return union type Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Some Points on Unions…

Example : 

union student { char name[10]; int rno; float score; } Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Example 10 Bytes Here Memory allocation is done based on the largest member.. In this case name is the largest member 2 Bytes 4Bytes

Arrays within the structures: 

We can have array as member of the structure Example: struct student { int rno; char name[20]; int sub[3]; }s1; Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Arrays within the structures

Arrays of structures: 

Struct stud { int rno; char name[20]; int sub[3]; }s[3]; Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Arrays of structures

Nesting of structures : 

struct s { int a; struct { float b; }f; }r; A structure can have structure within it, we call this as nesting of structures Example Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Nesting of structures

Structures and Functions : 

The first method is pass each member of the structure as an actual argument of the function call Passing a copy of entire structure to the called function Example: Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Structures and Functions

2.3.3 Internal Representation of structures: 

Memory allocated in structures is contiguous Allocation is done based on the word size(machines bit size) For example some machines are 32 bit, some may be 64 bits To enhance the speed of execution data alignment is done it is done by the help of padding mechanism. Padding is nothing but adding some extra bits in the memory of the member Control moves based on the word size, we call this as offset. For more details move to next slide Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.3.3 Internal Representation of structures

What is alignment and Padding in Structures?: 

Data structure alignment is the way data is arranged and accessed in computer memory. It consists of two separate but related issues: data alignment and data structure padding . When a modern computer reads from or writes to a memory address, it will do this in word sized chunks (e.g. 4 byte chunks on a 32-bit system). Data alignment means putting the data at a memory offset equal to some multiple of the word size, which increases the system's performance due to the way the CPU handles memory. To align the data, it may be necessary to insert some meaningless bytes between the end of the last data structure and the start of the next, which is data structure padding . Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore What is alignment and Padding in Structures?

How the structure Padding is done?: 

Structure Padding is done to do memory alignment. As size of pointer is 4 bytes, if everything is organized by multiple of 4, that it will be easier and faster to calculate the address and processing them. As structures are used to club different size variables, compiler will align to 4 byte boundaries and for that it needs padding. Padding will be done by compiler to structure’s members and to the structure as a whole also. Compiler pads structure as whole because this allows each member of structure aligned in array of structures. Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore How the structure Padding is done?

Example : 

Struct EX { Char a; Short int b; Char c; Long d; }; Due to structure padding this structure size is Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Example

Here Word Size is 32 Bits: 

a b c d Char[1] Padding [3] short int [2] Padding [2] Char [1] Padding [3] Long[4] Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Here Word Size is 32 Bits

Few Points….on Padding…: 

Padding does NOT occur at the beginning of a structure. The value of padding bytes or bits are implementation defined. Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Few Points….on Padding…

2.3.4 Self referential Structures: 

A structure calling a same type of structure is refered to as self referential Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.3.4 Self referential Structures

PowerPoint Presentation: 

Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.3.4 Self Referential Structures Representation of Singly Linked list struct node { int info ; struct node *link }; typedef struct node *NODE; Meaning of this: A node is of the type struct and contains info field and link filed

2.4 Polynomials: 

In mathematics, a polynomial (from Greek poly , means "many“ "binomial“ [ is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents. 2.4 Polynomials Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Few Things about polynomial: 

3x 20 + 2x 5 +4 X is the variables name Exponent: 20,5 are the exponent Coefficient: 3,4 2 are the coefficients Degree: The largest exponent of a polynomial is called degree. Here it is 20 The term with exponent equal to zero doesn’t show the variable Few Things about polynomial Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Adding Polynomial ; Horizonatlly: 

(3 x 3 + 3 x 2 – 4 x + 5) + ( x 3 – 2 x 2 + x – 4) =  3 x 3 + 3 x 2 – 4 x + 5 + x 3 – 2 x 2 + x – 4 =  3 x 3 + x 3 + 3 x 2 – 2 x 2 – 4 x + x + 5 – 4 = 4 x 3 + 1 x 2 – 3 x + 1 Adding Polynomial ; Horizonatlly Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Adding Polynomial ; Vertically : 

Adding Polynomial ; Vertically Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

2.4.1 Abstract Data type: 

The list contain items that are written in the form(item0,item1,…… item n-1 Finding the length, n of the list. Retrieving the items from the list 0≤i<n Replacing the item in the i th position 0 ≤i<n Inserting a new item in the position of a list 0 ≤i ≤ n. The items previously numbered i,i+1,…n-1 become items numbered i+1,i+2…n 2.4.1 Abstract Data type Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

Deleting an item in the ith position of a list 0 ≤ i <n. The items numbered i+1…n-1 become items items numbered i+1….n-2 Classic example of list processing a polynomial Polynomial is a sum of terms, where each term has a form ax e where x is the variable a is the coefficient, and e is the exponent. Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Example: 

A(x )=3x 20 + 2x 5 +4 and B(x)=x 4 +10x 3 + 3x 2 +1 The largest exponent of a polynomial is called degree A(x )+B(x)=3x 20 + 2x 5 +4 =Ʃ(a i + b i )x i Example Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

2.4.2 Polynomial Representation using arrays in structures : 

#define MAX_DEGREE 20 struct poly { int degree; float coef[max]; }a1; a1.degree=n a1.coef[i]=a n-I , 0 ≤i<n Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.4.2 Polynomial Representation using arrays in structures

2.2 Abstract Data type Polynomial: 

Polynomial(zero)::= return the polynomial, p(x)=0 BooleanIisZero (poly)::= if(poly) return FALSE else return zero Coefficient Coef ( poly,expon )::= if( expon∈poly ) return its coefficient else return zero ExponentLeadExp (poly)::=return the largest exponent in poly Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2.2 Abstract Data type Polynomial

PowerPoint Presentation: 

PolynomialAttach(poly,coef,expon)::=if(expon ∈ poly) return error else return the polynomial poly with the term<coef,expon> inserted PolynomialAdd(poly1,poly2)::=return the polynomial, poly1+poly2 PolynomialMult(poly1,poly2)::=return polynomial poly1.poly2 Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

Polynomial ADT (continued) A single variable polynomial can be generalized as: Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

What kinds of operations? Here are the most common operations on a polynomial: Add & Subtract Multiply Differentiate Integrate etc… Polynomial ADT (continued) Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

Polynomial ADT (continued) How to implement this? There are different ways of implementing the polynomial ADT: Array (not recommended) Double Array (inefficient) Linked List (preferred and recommended) Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

Polynomial ADT (continued) Array Implementation:[ two separate arrays] p1(x) = 8x 3 + 3x 2 + 2x + 6 p2(x) = 23x 4 + 18x - 3 6 2 3 8 0 2 Index represents exponents -3 18 0 0 23 0 4 2 p1(x) p2(x) 1 3 1 3 Implementation Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

This is why arrays aren’t good to represent polynomials: p3(x) = 16x 21 - 3x 5 + 2x + 6 Polynomial ADT (continued) 6 2 0 0 -3 0 0 16 ………… WASTE OF SPACE! Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

Polynomial ADT (continued) Double Array Implementation: Say you want to represent the following two polynomials: p1(x) = 23x 9 + 18x 7 - 41x 6 + 163x 4 - 5x + 3 p2(x) = 4x 6 + 10x 4 + 12x + 8 Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

2.3 Representation of Polynomial using arrays of structures: 

Max 100 typedef struct { float coeff; int expon; } polynomial; Polynomial terms[Max]// Single array 2.3 Representation of Polynomial using arrays of structures Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

This is why arrays aren’t good to represent polynomials: p3(x) = 16x 21 - 3x 5 + 2x + 6 Polynomial ADT (continued) 6 2 0 0 -3 0 0 16 ………… WASTE OF SPACE! Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

2.3 Example [Page No 68-69]: 

A(x)=2x 1000 + 1 B(x)=x 4 +10 x 3 +3 x 2 2.3 Example [Page No 68-69] Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore 2 1 1 10 3 1 1000 0 4 3 2 0 START A Finish A START B Finish B Avail Coeff Exp

Here We are using the concept Global array [Single array]: 

Both polynomials can be represented by only one array.[Single array] We use few things like… start A, finish A, start B, finish B, and avail. In the beginning avail=0 Finish A=startA + n-1 Here We are using the concept Global array [Single array] Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

Polynomial ADT (continued) 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. Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

Polynomial ADT (continued) Linked list Implementation: p1(x) = 23x 9 + 18x 7 + 41x 6 + 163x 4 + 3 p2(x) = 4x 6 + 10x 4 + 12x + 8 23 9 18 7 41 6 18 7 3 0 4 6 10 4 12 1 8 0 P1 P2 NODE (contains coefficient & exponent) TAIL (contains pointer) Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

What is Sparse Matrix…: 

A sparse matrix is a matrix populated primarily with zeros. The term itself was coined by Harry M. Markowitz. In many applications it is common to deal with very large matrices where only a few coefficients are different than zero. Both in term of memory consumption and performance, it is fundamental to use an adequate representation storing only nonzero coefficients. Such a matrix is called a sparse matrix. What is Sparse Matrix … Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

When storing and manipulating sparse matrices on a computer, it is beneficial and often necessary to use specialized algorithms and data structures that take advantage of the sparse structure of the matrix. Sparse data is by nature easily compressed, and this compression almost always results in significantly less computer data storage Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Example of Sparse Matrix: 

Example of Sparse Matrix Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

In this example of the 100 elements, only 17 are nonzero. The rest of the elements are zero. We call this a sparse matrix . While it is not costly to store all 100 numbers of the above matrix on a computer, consider what happens as the matrix gets bigger. If the number of rows grows to thousands or millions, the number of elements becomes too large to store. If, however, the number of the elements that are nonzero is small, we can still store the matrix if we only store those numbers and assume the rest are zero! This is a sparse storage scheme . Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

2.5.1 Sparse Matrix ADT [ Page No 73-74]: 

2.5.1 Sparse Matrix ADT [ Page No 73-74] 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. Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Sparse Matrix ADT (cont’d): 

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. Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

(1) Represented by a two-dimensional array. Sparse matrix wastes space. (2) Each element is characterized by TRIPLET <row, col, value>. Sparse Matrix Representation Sparse_matrix Create(max_row, max_col) ::= #define MAX_TERMS 101 /* maximum number of terms +1 */ typedef struct { int col; int row; int value; } term; term A[MAX_TERMS] CODE The terms in A should be ordered based on <row, col> Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore Row/COL COL0 COL1 COL2 COL3 COL4 COL5 Row0 15 0 0 22 0 -15 Row 1 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 O 28 0 0 0 Given Matrix

Sparse Matrix Operations: 

Sparse Matrix Operations Transpose of a sparse 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 [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 Sparse Matrix Transpose of Sparse Matrix Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

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 a Sparse Matrix Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

2.8 Transpose of a Sparse Matrix ; page no 77: 

2.8 Transpose of a Sparse Matrix ; page no 77 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 */ Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

PowerPoint Presentation: 

/* element is in the currenet column add it to b */ b[currentb].row=a[j].col; b[currentb].col=a[j].row; b[currentb].value=a[j].value; currentb++; } } Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

Fast Transpose of Sparse Matrix: 

A fast-transpose is a computer algorithm that quickly transposes a sparse matrix using a relatively small amount of memory. Using arrays normally to record a sparse matrix uses up a lot of memory since many of the matrix's values are zero. In addition, using the normal transpose algorithm to transpose this matrix will take O(cols*elements) amount of time. The fast-transpose algorithm only uses a little memory to record the matrix and takes only O(cols+elements) amount of time, which is efficient considering the number of elements equals cols*rows. Fast Transpose of Sparse Matrix Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore

void fast_transpose(term a[ ], term b[ ]) { /* the transpose of a is placed in b */ int row_terms[MAX_COL], starting_pos[MAX_COL]; int i, j, num_cols = a[0].col, num_terms = a[0].value; b[0].row = num_cols; b[0].col = a[0].row; b[0].value = num_terms; if (num_terms > 0){ /*nonzero matrix*/ for (i = 0; i < num_cols; i++) row_terms[i] = 0; for (i = 1; i <= num_terms; i++) row_term [a[i].col]++ starting_pos[0] = 1; for (i =1; i < num_cols; i++) starting_pos[i]=starting_pos[i-1] +row_terms [i-1]; : 

Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore void fast_transpose (term a[ ], term b[ ]) { /* the transpose of a is placed in b */ int row_terms [MAX_COL], starting_pos [MAX_COL]; int i , j, num_cols = a[0]. col , num_terms = a[0].value; b[0].row = num_cols ; b[0]. col = a[0].row; b[0].value = num_terms ; if ( num_terms > 0){ /*nonzero matrix*/ for ( i = 0; i < num_cols ; i ++) row_terms [ i ] = 0; for ( i = 1; i <= num_terms ; i ++) row_term [a[ i ]. col ]++ starting_pos [0] = 1; for ( i =1; i < num_cols ; i ++) starting_pos [ i ]= starting_pos [i-1] + row_terms [i-1];

for (i=1; i <= num_terms, i++) { j = starting_pos[a[i].col]++; b[j].row = a[i].col; b[j].col = a[i].row; b[j].value = a[i].value; } } } *Program 2.9:Fast transpose of a sparse matrix(p.78): 

Mr. J V Gorabal Assoc Prof CSE SCEM,Mangalore for (i=1; i <= num_terms, i++) { j = starting_pos[a[i].col]++; b[j].row = a[i].col; b[j].col = a[i].row; b[j].value = a[i].value; } } } *Program 2.9:Fast transpose of a sparse matrix(p.78) Compared with 2-D array representation O(columns+elements) vs. O(columns*rows) elements --> columns * rows O(columns+elements) --> O(columns*rows) Cost: Additional row_terms and starting_pos arrays are required. Let the two arrays row_terms and starting_pos be shared.