Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Shashank Yadav (KIET-Ghaziabad)

6
...
1 Linear Array:
 The simplest type of data structure is a linear array
...

 The elements of the array are stored respectively in successive memory locations
...

 The elements of A are denoted by any subscript notation as given below
...
A[K] is called subscripted
variable
...

LOC (LA[K]) = Base(LA) + w(K- LB)
LA Linear Array
LOC(LA[K]) Address of the element LA[K] of the array LA in memory
w the number of words per memory cell for array LA

6
...
If we want to print all numbers of array A or to count the
numbers of elements of A, we have to traverse all elements
...

1
...

Apply PROCESS to LA
3
...


6
...

1
...

3
...

5
...


Time Complexity:Best Case- When the ITEM is inserted at last (Nth) position
...

T(n)= O(1)
Worst Case- When the ITEM is inserted at first position
...

T(n)= O(n)
DELETE(LA, N, K)
Where LA is linear array of N elements, K is positive number such that K<=N
...
for J= K to N-1 do
2
...
N=N-1
4
...

Time Complexity:Best Case- When we want to delete last (Nth) position
...

T(n)= O(1)
Worst Case- When we want to delete first element
...

T(n)= O(n)

6
...
Most programming languages
allow two-dimensional and three-dimensional arrays, i
...
where elements are referenced,
respectively, by two and three subscripts
...
4
...
n data elements such that each
element is specified by a pair of integers (such as J, K), called subscripts, with the
following property that,
1 < = J < = m and 1 <= K <= n
 The element of A with first subscripts J and second subscript K will be denoted by
A J,K or A[J, K] or A[J][K]
 Two-dimensional arrays are called matrices in mathematics and tables in business
applications; hence two-dimensional arrays are sometimes called matrix arrays
...
4
...
Although A is pictured as a rectangular array of
elements with m rows and n columns, the array will be represented in memory by a block
of m
...

 Specially, the programming language will store the array A by two orders
1
...
Row major order
A

Subscript
(1,1)
(2,1)
(3,1)
(1,2)
(2,2)
(3,2)
(1,3)
(2,3)
(3,3)
(1,4)
(2,4)
(3,4)
1
...
Row-major order

Shashank Yadav (KIET-Ghaziabad)

 Formula for finding out address of A[J][K] element
(Column-major order) LOC (A[J][K])= Base(A) +w[M(K-1) + (J-1)]
(Row-major order) LOC (A[J][K])= Base(A) +w[N(J-1) + (K-1)]
Where w denotes the numbers of words per memory location for array A
...
Write an algorithm for searching an element in an array
...

1
...

if (A[I]== ITEM) then
3
...

goto step (5)
5
...

Write (ITEM is not found)
Time Complexity:Best Case- If the ITEM is at first position
...

T(n)= O(n)

2
...

DELETE(A, N, ITEM)
Where A is an array of N elements, ITEM is for deleting from array
...
for I=1 to N do
2
...

for J= I to N-1 do
4
...

N=N-1
6
...
if (I== N+1) then
8
...
Write an algorithm for multiplication of two matrices
...

1
...
for I=1 to M do
3
...

total=0
5
...

total=total+ A[I][K]*B[K][J]
7
...
Exit
Time complexity:- The complexity of a matrix multiplication algorithm is measured by counting
the numbers of multiplications
...
The complexity of the
algorithm is
T(n)= O(M
...
P)
4
...

#include ...
”);
}
Output:
How many numbers do you want in array: 5
Enter 5 numbers: 4 6 7 8 9
Enter number do you want to search in array: 8
Number is found
...
Write a C program for Insertion Sort
...
h>
#include ...
Write a Program in C for multiplication of two matrices A and B
...
h>
#include ...
5 Sparse Matrix:
 If a lot of elements from a matrix have a value 0 then matrix is known as a sparse matrix
...

 If the matrix is sparse we must consider an alternate way of representing it rather than the
normal row major or column major arrangement
...
The
first matrix, where non-zero entries can only occur on or below the main diagonal, is
called lower triangular matrix
...


15 | P a g e

Shashank Yadav (KIET-Ghaziabad)

1
2
3
4
5

1
2
3
4
5
6
7

1
2
3
4
3
-5
1
0
6
-7
8
-1
5
-2
0
(a) Triangular matrix

4

5

3
2

-8

1
5
1

4

5

2
-3
4
9

3
3
-3
2

6
4
3

-7
-1
6

6

7

0
-5
3

8
-1

(b) Tri-diagonal Matrix

 A common way of representing non-zero elements of a sparse matrix is 3-tuple forms
...

The 3rd element in this row stores the actual value of the non-zero element
...
Therefore, matrix A can be converted
into following form
...
5
...

16 | P a g e

Shashank Yadav (KIET-Ghaziabad)

CONVERT-SPARSE (ARRAY, SPARSE, M, N)
Where ARRAY is matrix of M*N order, SPARSE is the sparse
representation of M*N matrix
...
SPARSE [1][1]= M
2
...
C=2
4
...

for J=1 to N do
6
...

SPARSE[C][1]= I
8
...

SPARSE[C][3]= ARRAY[I][J]
10
...
SPARSE [1][3]=C-1
12
...

6
...
2 Addition of two sparse Matrices

---

Title: Arrays
Description: Basic guide to Arrays in DSA and practice questions.

Buy These NotesPreview