BE Computer Engineering (Pokhara University) Data Structure and Algorithms (PU, CMP 160) Question Paper 2078 Nepal

(a) Stack and Queue as Abstract Data Types

Stack (LIFO — Last In, First Out): A stack is a linear ADT in which insertion and deletion both occur at the same end, called the top. The element inserted most recently is the first to be removed.

Operations:

• push(x) — insert element x at the top
• pop() — remove and return the top element
• peek()/top() — return the top element without removing it
• isEmpty() — test whether the stack is empty

Queue (FIFO — First In, First Out): A queue is a linear ADT in which insertion occurs at one end (rear) and deletion at the other end (front). The element inserted first is the first to be removed.

Operations:

• enqueue(x) — insert element x at the rear
• dequeue() — remove and return the front element
• front() — return the front element without removing it
• isEmpty() — test whether the queue is empty

(b) Infix to Postfix Conversion using a Stack

Algorithm:

Initialize an empty stack and an empty output string.
Scan the infix expression left to right:
  1. If the token is an operand, append it to output.
  2. If the token is '(', push it onto the stack.
  3. If the token is ')', pop and append operators until '(' is
     popped (discard the '(').
  4. If the token is an operator o1:
       while stack top is an operator o2 with
         precedence(o2) > precedence(o1), OR
         precedence(o2) == precedence(o1) and o1 is left-associative:
           pop o2 and append to output
       push o1.
After scanning, pop and append all remaining operators.

Precedence: *, / (high) > +, - (low); all are left-associative.

Trace on A + B * (C - D) / E:

(Note: at /, * has equal precedence and is left-associative, so * is popped first; then / is pushed.)

Postfix result: A B C D - * E / +

(c) Circular Queue vs Linear Queue

In a simple linear array queue, front and rear only move forward. After repeated enqueue/dequeue operations, rear reaches the last index even though free cells exist at the beginning (vacated by dequeue). This false-full / wasted-space problem cannot be reused without shifting elements.

A circular queue treats the array as a ring: after the last index it wraps to index 0 using modulo arithmetic, so freed front cells are reused. Index update: rear = (rear + 1) % SIZE, front = (front + 1) % SIZE.

Conditions (using count, or the one-cell-gap method):

• Empty: front == -1 (or count == 0).
• Full: (rear + 1) % SIZE == front (one-cell-gap method), or count == SIZE.

(a) BST Construction by inserting 45, 15, 79, 90, 10, 55, 12, 20, 50

Insert each key by comparing with nodes from the root, going left if smaller and right if larger.

1. Insert 45 → root 45.
2. Insert 15 (<45) → left of 45.
3. Insert 79 (>45) → right of 45.
4. Insert 90 (>45,>79) → right of 79.
5. Insert 10 (<45,<15) → left of 15.
6. Insert 55 (>45,<79) → left of 79.
7. Insert 12 (<45,<15,>10) → right of 10.
8. Insert 20 (<45,>15) → right of 15.
9. Insert 50 (>45,<79,<55) → left of 55.

Final tree:

            45
          /    \
        15      79
       /  \    /  \
      10   20 55   90
        \     /
        12   50

(b) Traversal Sequences

• Inorder (Left, Root, Right): 10, 12, 15, 20, 45, 50, 55, 79, 90 (sorted order, as expected for a BST)
• Preorder (Root, Left, Right): 45, 15, 10, 12, 20, 79, 55, 50, 90
• Postorder (Left, Right, Root): 12, 10, 20, 15, 50, 55, 90, 79, 45

(c) Deleting a Node with Two Children

Procedure: When the node to delete has two children, replace its key with its inorder successor (the smallest key in its right subtree) — or equivalently its inorder predecessor — then delete that successor node (which has at most one child, so it is easy to remove).

Steps to delete 45 (root, two children):

1. Right subtree of 45 is rooted at 79. Its leftmost (smallest) node is 50 → inorder successor.
2. Replace key 45 with 50.
3. Delete the original 50 node. It was the left child of 55 and has no children, so simply remove it.

Tree after deletion:

            50
          /    \
        15      79
       /  \    /  \
      10   20 55   90
        \
        12

The BST property is preserved: 50 is greater than all keys in the left subtree and smaller than all remaining keys in the right subtree.

(a) Adjacency Matrix vs Adjacency List

For a graph with V vertices and E edges:

(b) BFS and DFS

Breadth First Search (BFS): Explores the graph level by level — visits the source, then all its neighbours, then their unvisited neighbours, and so on. It uses a queue (FIFO) as the auxiliary structure and finds shortest paths in terms of edge count in an unweighted graph. Time: $O(V+E)$ with an adjacency list.

Depth First Search (DFS): Explores as far as possible along one branch before backtracking. It uses a stack (LIFO) — explicitly, or implicitly via recursion. Useful for cycle detection, topological sort, connected components. Time: $O(V+E)$.

(c) Dijkstra's Algorithm

Consider this weighted graph (source A):

A-B = 4    A-C = 1
C-B = 2    C-D = 5
B-E = 3    D-E = 1

Edges: A–B(4), A–C(1), C–B(2), C–D(5), B–E(3), D–E(1). Vertices: A,B,C,D,E.

Maintain a distance set dist[] (initially 0 for A, ∞ for others) and a visited set. Repeatedly pick the unvisited vertex with smallest distance and relax its edges.

At step 2, C relaxes B: 1+2=3 < 4. At step 3, B relaxes E: 3+3=6. At step 5, D relaxes E: 6+1=7 > 6, no change.

Final shortest distances from A: A=0, B=3 (A→C→B), C=1 (A→C), D=6 (A→C→D), E=6 (A→C→B→E).

(a) Quick Sort and the Partition Step

Quick Sort is a divide-and-conquer algorithm. It chooses a pivot, then partitions the array so that all elements smaller than the pivot lie to its left and all larger to its right; the pivot is then in its final sorted position. The two partitions are sorted recursively.

Partitioning (Lomuto scheme, pivot = last element):

partition(A, lo, hi):
    pivot = A[hi]; i = lo - 1
    for j = lo to hi-1:
        if A[j] <= pivot:
            i = i + 1; swap A[i], A[j]
    swap A[i+1], A[hi]
    return i+1   // final pivot index

Example on [7, 2, 9, 3], pivot = 3: elements ≤3 (2) moved left → [2, 3, 9, 7] with 3 in place; recurse on [2] and [9,7] → sorted [2,3,7,9].

(b) Merge Sort of [38, 27, 43, 3, 9, 82, 10]

Division:

[38, 27, 43, 3, 9, 82, 10]
  -> [38, 27, 43, 3]            [9, 82, 10]
  -> [38,27] [43,3]            [9,82] [10]
  -> [38][27] [43][3]          [9][82] [10]

Merging (combine sorted halves):

[38]+[27]   -> [27,38]
[43]+[3]    -> [3,43]
[27,38]+[3,43] -> [3,27,38,43]
[9]+[82]    -> [9,82]
[9,82]+[10] -> [9,10,82]
[3,27,38,43] + [9,10,82] -> [3,9,10,27,38,43,82]

Sorted array: [3, 9, 10, 27, 38, 43, 82].

(c) Time Complexity of Quick Sort

Let $T(n)$ be the running time on $n$ elements; partitioning costs $\Theta(n)$.

• Best case — pivot splits the array into two equal halves:

$$T(n) = 2T(n/2) + \Theta(n) = O(n \log n)$$

• Average case — random/typical input, reasonably balanced splits: $O(n \log n)$.
• Worst case — pivot is always the smallest or largest element, giving splits of size $n-1$ and $0$:

$$T(n) = T(n-1) + \Theta(n) = O(n^2)$$

Worst-case input condition: the array is already sorted (ascending or descending) when the first or last element is chosen as pivot, producing maximally unbalanced partitions. Using a randomized or median-of-three pivot makes the worst case very unlikely. Space: $O(\log n)$ average recursion stack ($O(n)$ worst case).

Recursive Fibonacci

int fib(int n) {
    if (n <= 1)
        return n;          // fib(0)=0, fib(1)=1
    return fib(n-1) + fib(n-2);
}

Recursion Tree for fib(5)

              fib(5)
            /        \
        fib(4)        fib(3)
        /    \        /    \
   fib(3)  fib(2)  fib(2)  fib(1)
   /  \    /  \    /  \
fib(2) f(1) f(1) f(0) f(1) f(0)
 /  \
f(1) f(0)

Many subproblems (e.g. fib(3), fib(2)) are recomputed multiple times.

Why Exponential

Each call spawns two more calls, so the number of calls roughly doubles with n. The recurrence is $T(n) = T(n-1) + T(n-2) + O(1)$, whose solution grows like $\Theta(\phi^n)$ where $\phi \approx 1.618$ — i.e. exponential, $O(2^n)$. The same values are computed over and over (overlapping subproblems).

Improvement

Use memoization (top-down DP) — store each computed fib(i) in an array/cache and reuse it — or bottom-up dynamic programming iterating from fib(0) upward. This reduces the time to $O(n)$ (and space to $O(1)$ for the iterative two-variable version).

Reverse a Singly Linked List In Place

Use three pointers and reverse each next link while traversing once.

Node* reverse(Node* head) {
    Node *prev = NULL, *curr = head, *next = NULL;
    while (curr != NULL) {
        next = curr->next;   // save next node
        curr->next = prev;   // reverse the link
        prev = curr;         // advance prev
        curr = next;         // advance curr
    }
    return prev;             // new head
}

Complexity

• Time: $O(n)$ — each node is visited exactly once.
• Space: $O(1)$ — only a constant number of pointers are used; no extra nodes are allocated (in-place).

Two Advantages of Doubly over Singly Linked List

1. Bidirectional traversal: a doubly linked list can be traversed both forward and backward using its prev and next pointers.
2. Easier deletion / insertion before a node: given a pointer to a node, it can be deleted in $O(1)$ (the previous node is directly accessible via prev), whereas a singly linked list needs the predecessor to be found first.

Hash Collision

A hash collision occurs when two distinct keys map to the same index of the hash table under the hash function, i.e. h(k1) == h(k2) for k1 ≠ k2. A collision-resolution method is then required to store both keys.

Here h(k) = k mod 10, so all keys 12, 22, 32, 42, 52 hash to index 2 — every insertion after the first collides.

(a) Linear Probing

On collision, probe the next slot: (h(k) + i) mod 10, i = 0,1,2,...

• 12 → 2 (empty) → index 2
• 22 → 2 occupied → 3 → index 3
• 32 → 2,3 occupied → 4 → index 4
• 42 → 2,3,4 occupied → 5 → index 5
• 52 → 2,3,4,5 occupied → 6 → index 6

(b) Separate Chaining

Each slot holds a linked list of all keys hashing to it. All five keys hash to index 2:

In chaining, no probing is needed; collisions are simply appended to the list at that index.

Asymptotic Notations

Let $f(n)$ and $g(n)$ be non-negative functions.

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

Increasing Order of Growth

$$\log n \;<\; n \;<\; n \log n \;<\; n^2 \;<\; 2^n \;<\; n!$$

Justification: $n \log n$ vs $n^2$

Divide both by $n$: we compare $\log n$ with $n$. Since $\log n$ grows much more slowly than $n$ (for large $n$, $\log n \ll n$), it follows that $n \log n \ll n^2$. Hence $n \log n$ is placed before $n^2$ in the ordering.

Binary Search Algorithm (sorted array)

int binarySearch(int A[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (A[mid] == key)  return mid;      // found
        else if (A[mid] < key) low = mid + 1; // search right half
        else high = mid - 1;                  // search left half
    }
    return -1;  // not found
}

Trace: search 23 in [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] (indices 0–9)

Key 23 is found at index 5 in 3 comparisons. Time complexity: $O(\log n)$.

Why Not on a Singly Linked List

Binary search needs constant-time random access to the middle element. A singly linked list provides only sequential access — reaching the middle node requires traversing from the head in $O(n)$ time, and the list cannot be indexed directly. This destroys the $O(\log n)$ advantage, so binary search cannot be applied efficiently to a singly linked list.

AVL Tree

An AVL tree is a self-balancing Binary Search Tree in which, for every node, the heights of the left and right subtrees differ by at most 1. This keeps the tree height $O(\log n)$, guaranteeing $O(\log n)$ search, insert and delete.

Balance Factor Condition

For every node: $\text{BF} = height(\text{left subtree}) - height(\text{right subtree})$, and it must satisfy

$$\text{BF} \in \{-1, 0, +1\}.$$

If any node's balance factor becomes $+2$ or $-2$ after an insertion, a rotation restores balance.

Inserting 30, 20, 10

1. Insert 30 → root.
2. Insert 20 (<30) → left child. Tree still balanced (BF of 30 = +1).

   30
   /
  20

3. Insert 10 (<30,<20) → left child of 20.

     30   (BF = +2  -> unbalanced)
     /
    20
    /
   10

Node 30 now has balance factor $+2$ with the imbalance in the left-left subtree.

Rotation required: Single Right Rotation (LL rotation) about node 30.

After rotation (balanced):

    20
   /  \
  10   30

Every node now has balance factor in $\{-1,0,+1\}$, so the AVL property is restored.

Stack vs Queue

Real-world applications:

• Stack: function call/return management (call stack), undo operation in editors, expression evaluation.
• Queue: CPU/printer job scheduling, handling requests on a server (first-come first-served).

Implementing a Queue using Two Stacks

Use two stacks inStack and outStack.

• Enqueue(x): push x onto inStack.
• Dequeue(): if outStack is empty, pop every element from inStack and push it onto outStack (this reverses the order). Then pop and return the top of outStack.

Because the elements are reversed once when transferred, the element that entered first ends up on top of outStack, giving FIFO behaviour. Each element is pushed and popped at most twice, so the amortized cost per operation is $O(1)$.