Explain how arrays are stored in memory.

Compare row major and column major

order with an example of 2D matrix?
Arrays are stored in contiguous memory locations. For a 1D array, elements are placed one
after another. For a 2D matrix, the compiler must map the two-dimensional logical structure
into a one-dimensional physical memory space using one of two methods:

• Row-major order (used by C, C++, Python (NumPy), Java, etc.)

• Column-major order (used by Fortran, MATLAB, R, Julia, etc.)

Row Major Order

Row major ordering assigns successive elements, moving across the rows and then down
the next row, to successive memory locations. In simple language, the elements of an array
are stored in a Row-Wise fashion.

To find the address of the element using row-major order uses the following formula:

Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))

I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in an array(in byte),
LR = Lower Limit of row/start row index of the matrix(If not given assume it as zero),
LC = Lower Limit of column/start column index of the matrix(If not given assume it as
zero),
N = Number of column given in the matrix.
Column Major Order
If elements of an array are stored in a column-major fashion means moving across the
column and then to the next column then it’s in column-major order.

To find the address of the element using column-major order use the following formula:

Address of A[I][J] = B + W * ((J – LC) * M + (I – LR))

I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in any array(in byte),
LR = Lower Limit of row/start row index of matrix(If not given assume it as zero),
LC = Lower Limit of column/start column index of matrix(If not given assume it as zero),
M = Number of rows given in the matrix.

Row Major Order vs Column Major Order

Aspect Row Major Order Column Major Order

Elements are stored row Elements are stored column

by row in contiguous by column in contiguous
Memory Organization locations. locations.
Aspect Row Major Order Column Major Order

For a 2D array A[m][n]: For the same array:

[A[0][0], A[0][1], ..., A[m- [A[0][0], A[1][0], ..., A[m-
Memory Layout Example 1][n-1]] 1][n-1]]

Moves through the entire Moves through the entire

row before progressing to column before progressing
Traversal Direction the next row. to the next column.

Efficient for row-wise Efficient for column-wise

access, less efficient for access, less efficient for
Access Efficiency column-wise access. row-wise access.

Commonly used in Commonly used in

Common Use Cases languages like C and C++. languages like Fortran.

Suitable for row-wise Suitable for column-wise

operations, e.g., image operations, e.g., matrix
Applications processing. multiplication.

Write a Python program to insert and delete an element at a specific position in an

array

Arrays store elements in contiguous memory locations. When you insert or delete at a
specific position, all elements after that position must be shifted.

Insertion Process

Original Array: [10, 20, 30, 40, 50]

Insert 99 at position 2 (0-based index)

Step 1: Shift elements from position 2 onward to the RIGHT

[10, 20, __, 30, 40, 50]

Empty space created

Step 2: Insert 99 at position 2

[10, 20, 99, 30, 40, 50]

Final Array: [10, 20, 99, 30, 40, 50]

Deletion Process

Original Array: [10, 20, 99, 30, 40, 50]

Delete element at position 2

Step 1: Remove element at position 2

[10, 20, __, 30, 40, 50]

Empty space created

Step 2: Shift elements from position 3 onward to the LEFT

[10, 20, 30, 40, 50]

Final Array: [10, 20, 30, 40, 50]

Deleted Element: 99

def insert_element(arr, position, element):

"""

Insert an element at a specific position.

Modifies the original list.

"""

if position < 0:

position = len(arr) + position + 1

if position < 0 or position > len(arr):

raise IndexError(f"Invalid position. Must be between 0 and {len(arr)}")

[Link](position, element)

return arr

def delete_element(arr, position):

"""

Delete an element at a specific position.

Modifies the original list and returns the deleted element.

"""

if position < 0:

position = len(arr) + position

 if position < 0 or position >= len(arr):

raise IndexError(f"Invalid position. Must be between 0 and {len(arr)-1}")

deleted = [Link](position)

return deleted

# Example usage

my_list = [10, 20, 30, 40, 50]

print(f"Original: {my_list}")

# Insert at position 2 (0-based index)

insert_element(my_list, 2, 99)

print(f"After inserting 99 at index 2: {my_list}")

# Delete at position 4

deleted_value = delete_element(my_list, 4)

print(f"Deleted value: {deleted_value}")

print(f"After deletion: {my_list}")

Output:

Original: [10, 20, 30, 40, 50]

After inserting 99 at index 2: [10, 20, 99, 30, 40, 50]

Deleted value: 40

After deletion: [10, 20, 99, 30, 50]

A 2D matrix A of size M × N (M rows, N columns) is stored in row-major order in
memory. Write the formula to find the address of element A[i][j] and explain it with
example

Row major ordering assigns successive elements, moving across the rows and then down
the next row, to successive memory locations. In simple language, the elements of an array
are stored in a Row-Wise fashion.

To find the address of the element using row-major order uses the following formula:

Address of A[I][J] = B + W * ((I – LR) * N + (J – LC))

I = Row Subset of an element whose address to be found,
J = Column Subset of an element whose address to be found,
B = Base address,
W = Storage size of one element store in an array(in byte),
LR = Lower Limit of row/start row index of the matrix(If not given assume it as zero),
LC = Lower Limit of column/start column index of the matrix(If not given assume it as
zero),
N = Number of column given in the matrix.
Define stack. Explain its operations using array and linked list implementation.

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The
last element added to the stack is the first one to be removed. Real-world examples include a
stack of plates, a deck of cards, or the undo feature in text editors.

Basic Operations

Operation Description

push(x) Add element x to the top of stack

pop() Remove and return the top element

peek() Return top element without removing

isEmpty() Check if stack is empty

isFull() Check if stack is full (array only)

1. Array Implementation

In array implementation, we use an array to store elements and a variable top to track the
index of the top element.

Push Operation

Algorithm push(stack, item, top, capacity)

Begin
if top = capacity - 1 then
print "Stack Overflow"
return false
else
 top = top + 1
stack[top] = item
return true
endif
End

2. Pop Operation

Algorithm pop(stack, top)

Begin
if top = -1 then
print "Stack Underflow"
return null
else
item = stack[top]
top = top - 1
return item
endif
End

3. Peek Operation

Algorithm peek(stack, top)

Begin
if top = -1 then
print "Stack is empty"
return null
else
return stack[top]
endif
End

4. isEmpty Operation
Algorithm isEmpty(top)
Begin
if top = -1 then
return true
else
return false
endif
End

5. isFull Operation

Algorithm isFull(top, capacity)

Begin
if top = capacity - 1 then
return true
else
return false
endif
End

Linked List Implementation

1. Push Operation

Algorithm push(top, item)

Begin
// Create a new node
new_node = createNode()
new_node.data = item

// Link new node to current top

new_node.next = top
 // Update top to new node
top = new_node

return top
End

2. Pop Operation

Algorithm pop(top)
Begin
if top = NULL then
print "Stack Underflow"
return null
else
item = [Link]
temp = top
top = [Link]
delete temp
return item
endif
End

3. Peek Operation

Algorithm peek(top)
Begin
if top = NULL then
print "Stack is empty"
return null
else
return [Link]
endif
End
4. isEmpty Operation

Algorithm isEmpty(top)
Begin
if top = NULL then
return true
else
return false
endif
End

Convert the infix (A+B) *(C+D) into postfix and evaluate the postfix notation using
stack and show step by step
Given Infix Expression: (A + B) * (C + D)

Infix to Postfix Conversion

Rules for Conversion:

• Operands (A, B, C, D) → directly output

• Operators → push to stack based on precedence
• Opening bracket ( → push to stack
• Closing bracket ) → pop until (
• Precedence: * / (higher), + - (lower)

Step-by-Step Conversion

Step Symbol Stack Postfix Expression Action

1 ( ( Push (

2 A ( A Operand → output
Step Symbol Stack Postfix Expression Action

3 + (+ A Push +

4 B (+ AB Operand → output

5 ) AB+ Pop until ( → output +

6 * * AB+ Push *

7 ( *( AB+ Push (

8 C *( AB+C Operand → output

9 + *(+ AB+C Push +

10 D *(+ AB+CD Operand → output

11 ) * AB+CD+ Pop until ( → output +

12 End AB+CD+* Pop remaining *

Final Postfix Expression: AB+CD+*

Evaluate Postfix Expression using Stack

Let's evaluate with values:

Let A = 2, B = 3, C = 4, D = 5

Postfix: A B + C D + * → 2 3 + 4 5 + *

Rules for Evaluation:

 • Read symbols from left to right
• Operand → push to stack
• Operator → pop 2 operands, apply operation, push result

Step-by-Step Evaluation

Stack (top →
Step Symbol Operation Result
bottom)

1 2 2 Push 2

2 3 3, 2 Push 3

Pop 3, Pop 2, Compute 2 + 3 = 5,

3 + 5 5
Push 5

4 4 4, 5 Push 4

5 5 5, 4, 5 Push 5

Pop 5, Pop 4, Compute 4 + 5 = 9,

6 + 9, 5 9
Push 9

Pop 9, Pop 5, Compute 5 × 9 =

7 * 45 45
45, Push 45

Final Result: 45

Conversion Algorithm:

Initialize empty stack

For each symbol in infix:
if operand → output
if '(' → push to stack
if ')' → pop & output until '('
 if operator → pop higher/equal precedence, then push
Pop all remaining operators from stack

Evaluation Algorithm:

Initialize empty stack

For each symbol in postfix:
if operand → push to stack
if operator:
b = pop()
a = pop()
result = a operator b
push result
Final result = pop()

write a recursive function to reverse a string using stack data structure . Explain
recursion vs stack based iteration

Using Stack with Recursion

Algorithm

1. Push all characters of string onto stack

2. Recursively pop characters and build reversed string
def reverse_string_recursive(stack, reversed_str=""):
"""
Recursive function to reverse string using list as stack
"""
# Base case: when stack is empty
if len(stack) == 0:
return reversed_str

# Recursive case: pop last element and add to result

char = [Link]()
 return reverse_string_recursive(stack, reversed_str + char)

def reverse_string(text):
# Create stack as list and push all characters
stack = []
for char in text:
[Link](char)

# Recursively reverse
return reverse_string_recursive(stack)

# Test
text = "HELLO"
print(f"Original: {text}")
print(f"Reversed: {reverse_string(text)}")

Direct Recursion (Without Explicit Stack)

python
def reverse_string_recursive_direct(text):
"""
Direct recursion without explicit stack
(Uses system call stack implicitly)
"""
# Base case
if len(text) <= 1:
return text

# Recursive case: last char + reverse of rest

return text[-1] + reverse_string_recursive_direct(text[:-1])

# Test
text = "WORLD"
print(f"Original: {text}")
print(f"Reversed: {reverse_string_recursive_direct(text)}")

Output:

text
Original: WORLD
Reversed: DLROW

Recursion vs Stack-Based Iteration

Comparison Table

Aspect Recursion Stack-Based Iteration

Memory usage Uses call stack (limited size) Uses heap memory (larger)

Performance Slightly slower (function calls) Faster (no function call overhead)

Code readability Cleaner, more elegant More explicit, longer

Risk Stack overflow for large strings No overflow (heap memory)

Implementation 5-10 lines 10-15 lines

Debugging Harder (multiple stack frames) Easier (linear execution)