BE Computer Engineering (IOE, TU) Data Structure and Algorithm (IOE, CT 552) Question Paper 2078 Nepal

(a) Stack: definition, operations and array implementation

A stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle: the element inserted last is the one removed first. All insertions and deletions take place at one end called the top.

Basic operations

• PUSH(x) — insert element x at the top of the stack.
• POP() — remove and return the top element.
• PEEK() (or TOP) — return the top element without removing it.

Overflow and underflow (array of size MAX, top initialised to -1)

• Overflow: attempting to PUSH when top == MAX - 1 (stack full).
• Underflow: attempting to POP/PEEK when top == -1 (stack empty).

#define MAX 100
int stack[MAX];
int top = -1;

void push(int x) {
    if (top == MAX - 1)            // overflow check
        printf("Stack Overflow\n");
    else
        stack[++top] = x;
}

int pop() {
    if (top == -1) {              // underflow check
        printf("Stack Underflow\n");
        return -1;
    }
    return stack[top--];
}

int peek() {
    if (top == -1) {
        printf("Stack Empty\n");
        return -1;
    }
    return stack[top];
}

(b) Infix to postfix conversion

Expression: A + ( B * C - ( D / E ^ F ) * G ) * H

Precedence: ^ (highest, right-associative) > * / > + -. We scan left to right; operands go to output, operators are managed on the stack.

Postfix: A B C * D E F ^ / G * - H * +

Evaluation using a stack: Scan the postfix expression left to right. Push every operand onto the stack. On meeting an operator, pop the top two operands (the first popped is the right operand, the second is the left), apply the operator, and push the result back. After the whole string is scanned, the single value remaining on the stack is the final result.

(a) Binary Search Tree and insertion

A Binary Search Tree (BST) is a binary tree in which, for every node, all keys in its left subtree are smaller than the node's key and all keys in its right subtree are greater (no duplicates). This ordering allows search, insertion and deletion in $O(h)$ time, where $h$ is the height.

Inserting 45, 30, 60, 25, 40, 55, 70, 35 (45 is the root; each key goes left if smaller, right if larger):

              45
            /    \
          30      60
         /  \    /  \
        25  40  55  70
            /
           35

(b) Traversals of the BST

• Inorder (Left, Root, Right) — gives sorted order: 25, 30, 35, 40, 45, 55, 60, 70
• Preorder (Root, Left, Right): 45, 30, 25, 40, 35, 60, 55, 70
• Postorder (Left, Right, Root): 25, 35, 40, 30, 55, 70, 60, 45

(c) Deletions

Rule for deleting a node with two children: replace the node's key with its inorder successor (the smallest key in its right subtree) — or equivalently the inorder predecessor — then delete that successor node, which has at most one child.

Delete 30 (it has two children: 25 and 40). Inorder successor of 30 is 35 (smallest in the right subtree rooted at 40). Replace 30 with 35 and remove the original 35:

              45
            /    \
          35      60
         /  \    /  \
        25  40  55  70

Delete 60 (two children: 55 and 70). Inorder successor is 70 (smallest in its right subtree). Replace 60 with 70 and remove the leaf 70:

              45
            /    \
          35      70
         /  \    /
        25  40  55

(a) Adjacency matrix vs adjacency list

For a graph with $V$ vertices and $E$ edges:

A matrix wastes space on sparse graphs because it stores a slot for every possible edge; a list stores only existing edges, so it is far more space-efficient when $E \ll V^2$.

(b) DFS and BFS algorithms

DFS uses a stack (explicitly, or implicitly via recursion):

DFS(G, s):
    mark all vertices unvisited
    push s onto stack
    while stack not empty:
        v = pop()
        if v not visited:
            visit v; mark visited
            push all unvisited neighbours of v

BFS uses a queue:

BFS(G, s):
    mark all vertices unvisited
    visit s; mark visited; enqueue s
    while queue not empty:
        v = dequeue()
        for each unvisited neighbour w of v:
            visit w; mark visited; enqueue w

(c) Traversal starting from A (neighbours in alphabetical order)

Adjacency: A→B,C B→D,E C→F E→F,G

• DFS (A): start A → B → D (dead end, backtrack) → E → F (dead end) → G (dead end), backtrack to A → C (its neighbour F already visited). Visiting order: A, B, D, E, F, G, C.
• BFS (A): level by level — A | B, C | D, E, F | G → A, B, C, D, E, F, G

(a) Quick Sort algorithm and partitioning

Quick Sort is a divide-and-conquer sorting algorithm. It picks a pivot, partitions the array so that all elements smaller than the pivot lie to its left and all larger to its right (the pivot reaches its final sorted position), then recursively sorts the two partitions.

QUICKSORT(A, low, high):
    if low < high:
        p = PARTITION(A, low, high)   // pivot index
        QUICKSORT(A, low, p - 1)
        QUICKSORT(A, p + 1, high)

PARTITION(A, low, high):       // first element as pivot
    pivot = A[low]
    i = low + 1; j = high
    while true:
        while i <= j and A[i] <= pivot: i++
        while i <= j and A[j] >  pivot: j--
        if i < j: swap(A[i], A[j])
        else: break
    swap(A[low], A[j])         // place pivot in correct slot
    return j

Role of the pivot: the pivot is the reference element. The partition step rearranges the array around it so the pivot lands in its correct final position, splitting the problem into two independent smaller sub-arrays.

(b) Sorting 38, 27, 43, 3, 9, 82, 10 (first element as pivot)

Pass 1 — pivot = 38: elements ≤38 to the left, >38 to the right.
Result: [27, 3, 9, 10] 38 [82, 43] → 27 3 9 10 38 82 43

Left sub-array 27, 3, 9, 10 — pivot = 27:
→ [3, 9, 10] 27 → 3 9 10 27

• 3, 9, 10 pivot 3 → 3 [9, 10]; 9,10 pivot 9 → 9 10. Left part sorted: 3 9 10 27.

Right sub-array 82, 43 — pivot = 82:
→ [43] 82 → 43 82

Final sorted array: 3, 9, 10, 27, 38, 43, 82

(c) Time complexity

• Best case — pivot splits the array into two nearly equal halves: $T(n) = 2T(n/2) + O(n) = O(n \log n)$.
• Worst case — pivot is always the smallest or largest element, giving partitions of sizes $0$ and $n-1$: $T(n) = T(n-1) + O(n) = O(n^2)$.
• The worst case occurs when the array is already sorted (or reverse-sorted) and the first/last element is chosen as pivot.

(a) Singly vs doubly linked list

Singly: [data|next] -> [data|next] -> [data|NULL]

Doubly: NULL <- [prev|data|next] <-> [prev|data|next] -> NULL

(b) Algorithms

Insert at beginning

INSERT_FRONT(head, x):
    new = allocate node
    new.data = x
    new.next = head
    head = new          // new node becomes head
    return head

Delete from end

DELETE_END(head):
    if head == NULL: return NULL          // empty
    if head.next == NULL:                 // single node
        free(head); return NULL
    temp = head
    while temp.next.next != NULL:          // stop at 2nd-last
        temp = temp.next
    free(temp.next)
    temp.next = NULL
    return head

(a) Circular queue

A circular queue is a linear queue in which the last position is logically connected back to the first position, forming a circle. Indices wrap around using modulo arithmetic: REAR = (REAR + 1) % SIZE and FRONT = (FRONT + 1) % SIZE.

Limitation of a linear array queue it solves: in a simple linear queue, when REAR reaches the last index the queue is treated as full even if cells at the front were freed by dequeues — this is false overflow and wastes space. A circular queue reuses those vacated front cells by wrapping REAR around, so space is fully utilised without shifting elements.

(b) Trace for circular queue of size 5 (indices 0–4)

Start: FRONT = -1, REAR = -1 (empty).

Final: array = 60, 20, 30, 40, 50, FRONT = 1, REAR = 0 (REAR wrapped around to index 0). The queue is now full.

(a) Recursion

Recursion is a technique in which a function calls itself (directly or indirectly) to solve a problem by reducing it to smaller instances of the same problem, with a base case that stops the recursion.

Memory usage — recursive vs iterative: a recursive solution uses the call stack: each pending call adds a stack frame (storing parameters, local variables, return address), so memory grows with the recursion depth, $O(\text{depth})$ extra space, and deep recursion may cause stack overflow. An iterative solution uses a loop with a fixed set of variables, typically requiring only $O(1)$ extra space, making it more memory-efficient.

(b) Tower of Hanoi

void hanoi(int n, char src, char aux, char dst) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", src, dst);
        return;
    }
    hanoi(n - 1, src, dst, aux);   // move top n-1 to auxiliary
    printf("Move disk %d from %c to %c\n", n, src, dst);
    hanoi(n - 1, aux, src, dst);   // move n-1 from aux to dest
}

Number of moves: the recurrence is $T(n) = 2T(n-1) + 1$, $T(1)=1$, giving $T(n) = 2^n - 1$.

For $n = 4$: $T(4) = 2^4 - 1 = 16 - 1 = \mathbf{15}$ moves.

(a) Hash function and collision

A hash function $h(k)$ maps a key $k$ to an index in a hash table (typically $0$ to $m-1$), ideally distributing keys uniformly so that lookup, insertion and deletion take average $O(1)$ time.

A collision occurs when two distinct keys $k_1 \ne k_2$ hash to the same index, i.e. $h(k_1) = h(k_2)$. Collisions are unavoidable when the number of keys exceeds the table size, and must be handled by a collision-resolution method (e.g. linear probing, chaining).

(b) Insert 23, 43, 13, 27, 33 with h(k)=k mod 10, linear probing

Final hash table:

(a) Binary search algorithm

Precondition: the input array must be sorted (here, in ascending order).

BINARY_SEARCH(A, n, key):
    low = 0; high = n - 1
    while low <= high:
        mid = (low + high) / 2          // integer division
        if A[mid] == key: return mid     // found
        else if A[mid] < key: low = mid + 1
        else: high = mid - 1
    return -1                            // not found

(b) Trace: find 23 in [4, 8, 15, 16, 23, 42, 50] (indices 0–6)

Key 23 found at index 4 in 3 comparisons.

Time complexity: each step halves the search interval, so the number of comparisons is at most $\log_2 n$. Hence binary search runs in $O(\log n)$ in the worst and average case, and $O(1)$ in the best case (key at the first mid).

(a) Asymptotic notations

For functions $f(n)$ and $g(n)$:

• Big-O (upper bound): $f(n) = O(g(n))$ if there exist constants $c>0$ and $n_0$ such that $0 \le f(n) \le c\,g(n)$ for all $n \ge n_0$. Describes the worst-case / maximum growth rate.
• Big-Omega ($\Omega$, lower bound): $f(n) = \Omega(g(n))$ if there exist $c>0, n_0$ such that $0 \le c\,g(n) \le f(n)$ for all $n \ge n_0$. Describes the minimum growth rate.
• Big-Theta ($\Theta$, tight bound): $f(n) = \Theta(g(n))$ if there exist $c_1, c_2 > 0, n_0$ such that $c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$, i.e. $f$ is both $O(g)$ and $\Omega(g)$.

(b) Complexity of the code

for (i = 1; i <= n; i++)            // outer: runs n times
    for (j = 1; j <= n; j = j * 2)  // inner: j doubles each time
        printf("%d", i + j);

• The outer loop runs $n$ times.
• The inner loop multiplies j by 2 each iteration ($1, 2, 4, 8, \ldots$), so it executes about $\lfloor \log_2 n \rfloor + 1 = O(\log n)$ times, independent of i.

Total work $= n \times \log_2 n$.

Time complexity = $O(n \log n)$.

(a) Heap, max-heap and min-heap

A heap is a complete binary tree (all levels full except possibly the last, which fills left to right) that satisfies the heap property at every node. It is usually stored in an array, where for node at index i the children are at 2i+1 and 2i+2.

• Max-heap: every parent is ≥ its children, so the maximum element is at the root.
• Min-heap: every parent is ≤ its children, so the minimum element is at the root.

(b) Build max-heap from 12, 19, 16, 1, 4, 7 by successive insertion

Insert each element at the end and sift up (swap with parent while larger):

• Insert 12: 12
• Insert 19: 19>12 → swap → 19, 12
• Insert 16: 16<19 → 19, 12, 16
• Insert 1: 19, 12, 16, 1
• Insert 4: 19, 12, 16, 1, 4
• Insert 7: 7<16 → 19, 12, 16, 1, 4, 7

Final max-heap array: 19, 12, 16, 1, 4, 7

            19
          /    \
        12      16
       /  \    /
      1    4  7

One delete-max operation: remove the root (19), move the last element (7) to the root, then sift down.

• After moving 7 to root: 7, 12, 16, 1, 4
• Children of 7 are 12 and 16; largest is 16 → swap 7 and 16: 16, 12, 7, 1, 4
• 7 now a leaf → done.

Array after delete-max: 16, 12, 7, 1, 4

           16
         /    \
       12      7
      /  \
     1    4