Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Title: Arrays
Description: Basic guide to Arrays in DSA and practice questions.
Description: Basic guide to Arrays in DSA and practice questions.
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.
Description: Basic guide to Arrays in DSA and practice questions.