Unit 2: Introduction to Array Concepts - Subjective Questions

Array: An array is a linear data structure that stores a fixed number of elements of the same data type in contiguous memory locations. Each element is accessed using an index.

Declaration:

• General form: dataType arrayName[size];
• Example: int marks[5];

Initialization:

• At declaration: int marks[5] = {70, 75, 80, 85, 90};
• With inferred size: int marks[] = {70, 75, 80, 85, 90};
• Individual assignment: marks[0] = 70;

For an array of size , valid indexes range from to . Thus, marks[0] is the first element and marks[4] is the last element of an array of size .

A one-dimensional array is stored in contiguous memory locations. If every element requires bytes, the addresses of successive elements differ by bytes.

Let:

• be the base address of the array.
• be the lower-bound index.
• be the size of each element in bytes.
• be the required index.

The address is:

For a zero-based array, , so:

For example, if the base address is , each integer occupies bytes, and , then:

This direct calculation enables constant-time indexed access, with complexity .

Array traversal is the process of visiting every element of an array, usually from the first element to the last, to read, display, or process it.

Algorithm:

1. Start with index .
2. Access or process A[i].
3. Increment by .
4. Repeat until .

Pseudocode:

for i = 0 to n - 1

process A[i]

Complexity:

• Time complexity: , because all elements are visited.
• Auxiliary space complexity: , if only a loop variable is used.

Traversal is commonly used for printing, summing, counting, searching, and updating array elements.

To insert an element into an array, sufficient unused capacity must be available. Elements at and after the insertion position must be shifted one place to the right.

Algorithm for inserting item at index pos:

1. Check whether the array has free capacity.
2. Validate that .
3. Starting from index , shift each element right until pos is reached.
4. Store item at A[pos].
5. Increase the logical size by .

Pseudocode:

for i = n - 1 down to pos

A[i + 1] = A[i]

A[pos] = item

n = n + 1

Complexity:

• Insertion at the end: , when capacity is available.
• Insertion at the beginning: .
• Insertion at an arbitrary position: in the worst case.

Array deletion removes an element from a specified index while preserving the order and contiguous logical arrangement of the remaining elements.

Algorithm for deleting the element at index pos:

1. Check that the array is not empty.
2. Validate that .
3. Save A[pos] if the removed value is required.
4. Shift every element after pos one position to the left.
5. Decrease the logical size by .

Pseudocode:

item = A[pos]

for i = pos to n - 2

A[i] = A[i + 1]

n = n - 1

Shifting closes the gap created by deletion.

Complexity:

• Deletion from the end: .
• Deletion from the beginning: .
• Worst-case deletion from an arbitrary position: .

Linear search examines array elements sequentially until the required key is found or the end of the array is reached. It works with both sorted and unsorted arrays.

Algorithm:

1. Begin at index .
2. Compare the current element with the search key.
3. Return the index if they are equal.
4. Otherwise, continue to the next element.
5. Return failure after all elements have been checked.

Pseudocode:

for i = 0 to n - 1

if A[i] == key

return i

return -1

Complexity:

• Best case: , when the first element matches.
• Average case: .
• Worst case: , when the key is last or absent.
• Auxiliary space: .

It is suitable for small or unsorted collections.

Binary search repeatedly divides the search interval into two halves. Its essential prerequisite is that the array must be sorted.

Algorithm:

1. Set low = 0 and high = n - 1.
2. Calculate mid = low + (high - low) / 2 using integer division.
3. If A[mid] equals the key, return mid.
4. If the key is smaller, set high = mid - 1.
5. If the key is larger, set low = mid + 1.
6. Repeat while low <= high; otherwise, report failure.

After iterations, the remaining size is approximately . The process ends when:

Therefore:

Complexity:

• Best case: .
• Average and worst cases: .
• Iterative auxiliary space: .

Linear search and binary search differ as follows:

• Data requirement: Linear search works on sorted or unsorted data, whereas binary search requires sorted data.
• Method: Linear search checks elements sequentially; binary search repeatedly halves the search interval.
• Best-case time: Both can take .
• Worst-case time: Linear search takes , whereas binary search takes .
• Implementation: Linear search is simpler; binary search requires careful management of low, high, and middle indexes.
• Suitable use: Linear search is useful for small or frequently changing unsorted data. Binary search is preferable for large, sorted arrays.

Although binary search is faster for repeated searches, the cost of sorting must be considered if the original data is unsorted.

Bubble sort repeatedly compares adjacent elements and swaps them when they are in the wrong order. After each pass, the largest unsorted element moves to its final position.

For [5, 2, 4, 1], the first pass performs:

• Compare and : [2, 5, 4, 1]
• Compare and : [2, 4, 5, 1]
• Compare and : [2, 4, 1, 5]

The value is now in its correct final position. Further passes produce [1, 2, 4, 5].

Optimized algorithm: Use a Boolean swapped flag and stop if a complete pass performs no swaps.

Complexity:

• Best case with the optimization: .
• Average case: .
• Worst case: .
• Auxiliary space: .

Bubble sort is stable when equal elements are not swapped.

In standard bubble sort, the first pass makes comparisons. The second makes comparisons because the largest element is already in position. This continues until the final pass makes one comparison.

Thus, the total number of comparisons is:

Using the sum of the first positive integers:

Expanding gives:

The term dominates as grows, so the worst-case time complexity is . In a reverse-sorted array, a swap may be required after every comparison, resulting in up to swaps as well.

Complexities of common array operations:

• Access by index: because the element address is calculated directly.
• Traversal: because every element is visited.
• Linear search: Best case ; worst case .
• Binary search: Best case ; worst case , provided the array is sorted.
• Insertion at the end: when unused capacity is available.
• Insertion at the beginning or middle: because elements may need to be shifted.
• Deletion from the end: .
• Deletion from the beginning or middle: because remaining elements must be shifted.
• Bubble sort: Average and worst cases are .

These results show that arrays provide fast random access but can make position-based insertion and deletion expensive.

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. The most recently inserted element is removed first. All insertions and deletions occur at one end called the top.

Basic operations:

• Push: Adds an element to the top.
• Pop: Removes and returns the top element.
• Peek or Top: Reads the top element without removing it.
• isEmpty: Checks whether the stack contains no elements.
• isFull: Checks whether an array-based stack has reached its capacity.
• Traversal: Visits stack elements, generally from top to bottom.

Applications:

• Function-call and recursion management
• Expression evaluation and conversion
• Parenthesis matching
• Undo and redo operations
• Backtracking and depth-first search

Push, pop, and peek normally take time.

Stack traversal visits the stored elements without inserting or deleting them. In an array-based stack, top contains the index of the most recently pushed element.

To traverse in LIFO order, begin at top and move toward index .

Pseudocode:

if top == -1

report "Stack is empty"

else

for i = top down to 0

process stack[i]

The loop uses a separate variable i. It must not decrement top, because top represents the actual state of the stack. Changing it during traversal would logically remove elements or make them inaccessible.

Complexity:

• Time complexity: for stored elements.
• Auxiliary space: for iterative traversal.

The push operation inserts a new element at the top of a stack. For an array stack of capacity MAX, top is initially .

Overflow condition:

top == MAX - 1

If this condition is true, no free position remains and insertion cannot proceed.

Push algorithm:

1. Test whether top == MAX - 1.
2. If true, report stack overflow.
3. Otherwise, increment top.
4. Assign the new value to stack[top].

Pseudocode:

if top == MAX - 1

report "Stack overflow"

else

top = top + 1

stack[top] = item

The operation takes time and auxiliary space because no traversal or shifting is required.

The pop operation removes and returns the element at the top of a stack.

Pop algorithm:

1. Check whether top == -1.
2. If true, report stack underflow.
3. Otherwise, save stack[top].
4. Decrement top.
5. Return the saved element.

Pseudocode:

if top == -1

report "Stack underflow"

else

item = stack[top]

top = top - 1

return item

Underflow versus overflow:

• Underflow occurs when pop or peek is attempted on an empty stack.
• Overflow occurs when push is attempted on a full fixed-size stack.

Pop normally takes time and auxiliary space.

A queue is a linear data structure that follows the First In, First Out (FIFO) principle. The element inserted first is removed first. Insertion occurs at the rear, while deletion occurs at the front.

Basic operations:

• ENQ or enqueue: Inserts an element at the rear.
• DEQ or dequeue: Removes and returns the front element.
• Front or peek: Reads the front element without removing it.
• isEmpty: Checks whether the queue has no elements.
• isFull: Checks whether a fixed-size queue has reached capacity.
• Traversal: Visits elements from front to rear.

Applications:

• CPU and process scheduling
• Printer spooling
• Request handling in servers
• Breadth-first search
• Input and output buffering

Properly implemented ENQ and DEQ operations take time.

Queue traversal visits active queue elements in FIFO order, beginning at front and ending at rear.

Linear queue:

• If front == -1, the queue is empty.
• Otherwise, process elements from index front through rear.

for i = front to rear

process queue[i]

Circular queue: Indexes wrap around the array. Begin at front, process each element, and advance with:

Stop after processing the element at rear.

Important point: Traversal should use a temporary index and must not alter front or rear, because they define the queue's current state.

For active elements, traversal takes time and auxiliary space.

The ENQ operation inserts a new element at the rear of a queue. Assume both front and rear are initially and the array capacity is MAX.

Overflow condition for a linear queue:

rear == MAX - 1

Algorithm:

1. If rear == MAX - 1, report queue overflow.
2. If the queue is initially empty, set front = 0.
3. Increment rear.
4. Store the item at queue[rear].

Pseudocode:

if rear == MAX - 1

report "Queue overflow"

else

if front == -1

front = 0

rear = rear + 1

queue[rear] = item

ENQ takes time. A limitation of a linear array queue is that freed positions before front cannot be reused without shifting or converting the structure into a circular queue.

The DEQ operation removes and returns the element at the front of a queue.

Algorithm:

1. If front == -1 or front > rear, report queue underflow.
2. Save the element at queue[front].
3. If front == rear, the removed element was the last one, so reset both indexes to .
4. Otherwise, increment front.
5. Return the saved element.

Pseudocode:

if front == -1 or front > rear

report "Queue underflow"

else

item = queue[front]

if front == rear

front = rear = -1

else

front = front + 1

return item

DEQ takes time because it changes only the front index and does not shift elements.

Queue underflow occurs when DEQ or front access is attempted on an empty queue. In a typical array implementation, emptiness may be represented by front == -1.

Queue overflow occurs when ENQ is attempted but no usable position is available.

For a linear queue, the overflow test is usually:

rear == MAX - 1

This can cause false overflow: positions before front may be empty but cannot be reused because rear has reached the final array index.

A circular queue treats the array's end as connected to its beginning. Indexes advance using:

Its full condition is:

Its empty condition is commonly represented by:

By wrapping rear to the beginning, a circular queue reuses positions freed by DEQ operations. This improves space utilization while retaining ENQ and DEQ operations.