Scribd
Upload
10 views2 pages

Array

The document outlines methods for calculating addresses in 1D and 2D arrays, including insertion and deletion techniques, as well as strategies for finding minimum and maximum elements. It discusses different search methods, such as linear and binary search, and details the address calculation for elements in row-major and column-major order in 2D arrays. Additionally, it covers properties of lower triangular matrices and linked lists.

Uploaded by

sohomkar42
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views2 pages

Array

The document outlines methods for calculating addresses in 1D and 2D arrays, including insertion and deletion techniques, as well as strategies for finding minimum and maximum elements. It discusses different search methods, such as linear and binary search, and details the address calculation for elements in row-major and column-major order in 2D arrays. Additionally, it covers properties of lower triangular matrices and linked lists.

Uploaded by

sohomkar42
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

ARRAY

find the address of a[i]= base+ size * no of elements stored in array before a[i].
for 1d array address of a[i]=base+ size * (i-Lower Bound)/base+ size * i.
insertion 2 types [Link] at the end[insertion(A[],n,item]
[Link] given index[insertion(A[],n,item,i)]
deletion 2 types [Link] at the end[deletiontion(A[],n,item]
[Link] given index[deletiontion(A[],n,item,i)]
finding minimum element [Link] by one comparison
[Link] tournament
no of comparisons=n-1
method to find min&max
method1 find min= n-1
find max =n-2
total= 2n-3

compare 2 consecutive n/2 element of smaller min= n/2 -1


n/2 element of larger max= n/2 -1
total 3n/2 -2
second minimum
find min n-1
find min of remaining element n-2
total= 2n-3
elimination method
find min n-1
find 2nd min logn-1
total= n+logn-2
linear search-> can be unordered
binary search-> can be sorted
2D ARRAY
finding an element =base+ size* no of elements before A[i][j]
for row major order= base+ size* [no of elements stored in all rows from row
lbi to row i-1+ no of elements stored from column lbj to j-1 in ith row]/
[(i-lbi)n+(j-lbj)]
column major order= base+ size* [no of elements stored from column lbj to j-
1+no of elements stored in all rows from row lbi to row i-1 in jth row ]/
[(j-lbj)m+(i-lbi)]
no of rows m
no of columns n
lower triangular matrix
no of element which can be zero= n(n-1)/2
no of element which can not be zero= n(n+1)/2
address A[i][j]= base + size * [no of elements in rows from row lbi to (i-1)+ no
of elements in ith row before jth column]
=base + size[i(i+1)/2 + (j-0)]
column major order= base + size * [no of elements in column from column 0 to
(j-1)+ no of elements before ith row in column j]
=base + size[nj-j(j-1)/2+(i-j)]
Linked list
address of last node

You might also like