2. 2D Array

 

Two Dimensional Array

The two dimensional array can be defined as an array of arrays. The 2D array is organized as matrices which can be represented as the collection of rows and columns.

Declaring and Initializing a 2D Array

• dataType arrayName[rows][columns];
• int disp[2][4] = {{10,11,12,13}, {14,15,16,17}};
• int disp[2][4] = {10,11,12,13,14,15,16,17}};

Row major implementation of 2D array

• In row major method elements of an array are arranged sequentially row by row.
• Thus, elements of first row occupies first set of memory locations reserved for the array, elements of second row occupies the next set of memory and so on.

Address of a[i][j] = B + W * [(U2-L2+1)*(i-L1) + (j-L2)]
where, B is the base address,
W is the size of each element,
L1, U1 are the lower and upper bounds of row,
L2, U2 are the lower and upper bounds of column,
(U2-L2+1) specifies the number of columns.,
(i-L1) specifies the number of rows before us and
(j-L2) specifies the number of elements before us in current row.

Column major implementation of 2D array

• In column major method elements of an array are arranged sequentially column by column.
• Thus, elements of first column occupies first set of memory locations reserved for the array, elements of second column occupies the next set of memory and so on.

Address of a[i][j] = B + W * [(U1-L1+1)*(j-L2) + (i-L1)]
where, B is the base address,
W is the size of each element,
L1, U1 are the lower and upper bounds of row,
L2, U2 are the lower and upper bounds of column,
(U1-L1+1) specifies the number of rows.,
(j-L2) specifies the number of columns before us and
(i-L1) specifies the number of elements before us in current column.

1. If row-major order is used, how is the following matrix stores in memory?

                       a b c
                       d e f
                       g h i

1. i h g f e d c b a
2. a b c d e f g h i
3. c f i b e h a d g
4. a d g b e h c f i

ii. a b c d e f g h i

Dynamic Array

• A dynamic array is a resizable array that can grow or shrink during runtime.
• It is implemented using a fixed-size array, but its size can be increased or decreased as needed by allocating a new array of a larger or smaller size and copying the elements from the old array to the new one. This process is known as resizing or reallocating the array.
• Dynamic arrays are often implemented using pointers and dynamic memory allocation.
• Arrays have a fixed size, which is determined at the time of their declaration, while dynamic arrays can be resized during runtime. This makes dynamic arrays more flexible than arrays, but it also requires more money management and can lead to performance overhead due to the resizing process.

1. In which of the following cases dynamic arrays are not preferred?
1. If the size of the array is unknown.
2. If the size of the array changes after few iterations.
3. If the memory reallocation takes more time i.e. expensive.
4. If the array holds less number of elements.

iv. If the array holds less number of elements.

2. What is meant by physical size in a dynamic array?
1. The size allocated to elements.
2. The size extended to add new elements.
3. The size of underlying array at the backend.
4. The size visible to users.

iii. The size of underlying array at the backend.

3. The growth factor of ArrayList in Java is ____.
1. 1
2. 1.5
3. 2
4. 0

ii. 1.5

4. The size of the dynamic array is deallocated if the array size is less than ____ % of the backend physical size.
1. 30
2. 40
3. 50
4. 10

i. 30

5. What is the following is a disadvantage of dynamic arrays?
1. Memory leak
2. Locality of reference
3. Data cache utilization
4. Random access

i. Memory leak

6. Array is divided into two parts in ____.
1. Hashed Array Tree
2. Geometric Array
3. Bounded-size dynamic Array
4. Sparse Array

iii. Bounded-size dynamic Array

Sparse Array

• A sparse array is a data structure used to represent arrays with a large number of default values (elements that have a default value of zero or null). In sparse array, only non-default values are stored, along with their corresponding indices, to save memory.
• For example, consider an array of length 10^6 that has only 100 non-zero elements. A traditional array would allocate memory for all 10^7 elements, even though most of them have a default value of zero. In sparse array, only the 100 non-zero elements and their indices would be stored, saving a significant amount of memory.
• Sparse arrays can be implemented using a variety of data structures, such as hash tables, linked lists or trees. The specific implementation depends on the access pattern of array and the distribution of non-zero elements.

1. When do you use a sparse array?
1. When elements are stored.
2. When there are unique elements in the array.
3. When the array has more occurrence of zero elements.
4. When the data type of elements differ.

iii. When the array has more occurrence of zero elements.

2. What is a bit array?
1. Data structure for representing arrays of records.
2. Data structure that compactly stores bits.
3. An array in which most of the elements have the same value.
4. Array in which elements are not present in continuous locations.

ii. Data structure that compactly stores bits.

3. What does Hamming weight/population count mean in Bit arrays?
1. Finding the number of 1 bit in a bit array.
2. Finding the number of 0 bit in a bit array.
3. Finding the sum of bits in a bit array.
4. Finding the average number of 1's and 0's in bit arrays.

i. Finding the number of 1 bit in a bit array.