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

(a) Asymptotic Notations

Asymptotic notations describe the limiting behaviour of an algorithm's running time as the input size $n$ grows large. They let us compare algorithms independent of machine and constants.

Big-O (Upper Bound)

$f(n) = O(g(n))$ if there exist constants $c > 0$ and $n_0 > 0$ such that

$$0 \le f(n) \le c\,g(n) \quad \text{for all } n \ge n_0.$$

It gives the worst-case (upper) bound. Example: $3n^2 + 2n + 1 = O(n^2)$.

Graph: $c\,g(n)$ lies above $f(n)$ for all $n \ge n_0$.

Big-Omega ($\Omega$) (Lower Bound)

$f(n) = \Omega(g(n))$ if there exist $c > 0$ and $n_0 > 0$ such that

$$0 \le c\,g(n) \le f(n) \quad \text{for all } n \ge n_0.$$

It gives the best-case (lower) bound. Example: $3n^2 + 2n = \Omega(n^2)$.

Graph: $c\,g(n)$ lies below $f(n)$ for all $n \ge n_0$.

Big-Theta ($\Theta$) (Tight Bound)

$f(n) = \Theta(g(n))$ if there exist $c_1, c_2 > 0$ and $n_0$ such that

$$0 \le c_1 g(n) \le f(n) \le c_2 g(n) \quad \text{for all } n \ge n_0.$$

It squeezes $f(n)$ between two multiples of $g(n)$ (both upper and lower bound). Example: $3n^2 + 2n + 1 = \Theta(n^2)$.

Graph: $f(n)$ is sandwiched between $c_1 g(n)$ and $c_2 g(n)$ for all $n \ge n_0$.

(b) Frequency Count of the Code

for (i = 0; i < n; i++) {        // outer loop
    for (j = i; j < n; j++) {    // inner loop
        sum = sum + a[i][j];     // body
    }
}

The inner loop runs $(n - i)$ times for each value of $i$. Total executions of the body:

$$\sum_{i=0}^{n-1}(n-i) = n + (n-1) + \dots + 1 = \frac{n(n+1)}{2}.$$

Frequency count of the body statement $= \dfrac{n(n+1)}{2} = \dfrac{n^2+n}{2}$.

Since there is no early exit (no conditional break), the number of iterations is the same for every input. Therefore:

• Best case: $O(n^2)$
• Worst case: $O(n^2)$

The code is always $\Theta(n^2)$.

(a) AVL Tree

An AVL tree is a self-balancing binary search tree in which, for every node, the balance factor (height of left subtree $-$ height of right subtree) is $-1$, $0$, or $+1$. When an insertion violates this, a rotation (LL, RR, LR, RL) restores balance.

Insertion of 30, 31, 32, 23, 22, 24, 16, 17, 18

1. Insert 30 → root 30.
2. Insert 31 → right child of 30. Balanced.
3. Insert 32 → unbalanced at 30 (BF $-2$, right-right). RR rotation → 31 becomes root with children 30, 32.
4. Insert 23 → goes left of 30. Balanced.
5. Insert 22 → unbalanced at 30 (left-left). LL rotation at 30 → 23 with children 22,30. Tree: root 31, left 23 (children 22, 30), right 32.
6. Insert 24 → right child of 23... it goes left of 30. Balanced (no violation).
7. Insert 16 → left of 22. Unbalanced at 31 (BF $+2$, left subtree heavy, left-left). LL rotation at 31 → 23 becomes new root. Left child 22 (with child 16), right child 31 (with left 30 containing 24, right 32).
8. Insert 17 → unbalanced at 22 (left-right: 16 then right 17). LR rotation → 17 becomes parent of 16 and 22.
9. Insert 18 → unbalanced at 23 root region (left-right path 17→18). RL/LR rotation restores balance; 18 settles under 17.

Final balanced AVL tree

          23
        /     \
      17        31
     /  \      /   \
   16    22  30      32
          \   /
          18 24

(Heights satisfy |BF| ≤ 1 at every node.)

(b) Binary Tree vs Binary Search Tree

Traversals of the final tree

• In-order (L, Root, R): 16, 17, 18, 22, 23, 24, 30, 31, 32 (sorted)
• Pre-order (Root, L, R): 23, 17, 16, 22, 18, 31, 30, 24, 32
• Post-order (L, R, Root): 16, 18, 22, 17, 24, 30, 32, 31, 23

(a) Adjacency Matrix

Vertices {A, B, C, D, E}, undirected edges: A-B(4), A-C(1), C-B(2), B-D(5), C-D(8), C-E(10), D-E(2). Entry = weight, $\infty$ (or 0) if no edge; matrix is symmetric.

(b) Dijkstra's Algorithm from source A

Initialize $dist[A]=0$, others $=\infty$. At each iteration pick the unvisited vertex with minimum distance and relax its neighbours.

Final shortest distances and paths from A

• A → A: 0
• A → C: 1 (A→C)
• A → B: 3 (A→C→B)
• A → D: 8 (A→C→B→D)
• A → E: 10 (A→C→B→D→E)

(a) Infix → Postfix: A + B * (C - D) / E ^ F

Precedence: ^ (highest, right-assoc) > *,/ > +,-. Scan left to right; operands go to output, operators are pushed respecting precedence.

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

(b) Recursion and the System Stack

When a function calls itself, the system pushes an activation record (stack frame) onto the call stack containing the return address, parameters, and local variables. Each recursive call adds a new frame; when a call returns, its frame is popped and control returns to the caller. The base case stops the recursion and unwinding begins.

int factorial(int n) {
    if (n == 0)            // base case
        return 1;
    return n * factorial(n - 1);   // recursive case
}

Trace for n = 4

factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1 * factorial(0)
factorial(0) = 1            <- base case, stack unwinds
=> factorial(1) = 1*1 = 1
=> factorial(2) = 2*1 = 2
=> factorial(3) = 3*2 = 6
=> factorial(4) = 4*6 = 24

Result: 4! = 24.

Insertion in a Singly Linked List

struct Node { int data; struct Node *next; };

// 1. Insert at the BEGINNING
struct Node* insertBegin(struct Node *head, int x) {
    struct Node *n = malloc(sizeof(struct Node));
    n->data = x;
    n->next = head;   // point to old head
    return n;         // new head
}

// 2. Insert at the END
struct Node* insertEnd(struct Node *head, int x) {
    struct Node *n = malloc(sizeof(struct Node));
    n->data = x; n->next = NULL;
    if (head == NULL) return n;
    struct Node *t = head;
    while (t->next != NULL) t = t->next;  // go to last node
    t->next = n;
    return head;
}

// 3. Insert AFTER a given node p
void insertAfter(struct Node *p, int x) {
    if (p == NULL) return;
    struct Node *n = malloc(sizeof(struct Node));
    n->data = x;
    n->next = p->next;   // link new node to p's successor
    p->next = n;         // link p to new node
}

Advantage of a linked list over an array: A linked list is dynamic — it can grow or shrink at run time without a fixed size, and insertion/deletion at the front (or after a known node) takes $O(1)$ time without shifting elements, whereas an array requires shifting and has fixed capacity.

Hashing with Quadratic Probing

Table size $m = 10$, $h(k) = k \bmod 10$. On collision, probe positions $(h(k) + i^2) \bmod 10$ for $i = 1, 2, 3, \dots$

Insert 72, 27, 36, 24, 63, 81, 92:

• 72 → $72\%10 = 2$. Slot 2 empty → place at 2.
• 27 → 7. Empty → 7.
• 36 → 6. Empty → 6.
• 24 → 4. Empty → 4.
• 63 → 3. Empty → 3.
• 81 → 1. Empty → 1.
• 92 → 2 (occupied by 72). Probe $i=1$: $(2+1)\%10 = 3$ (occupied by 63). Probe $i=2$: $(2+4)\%10 = 6$ (occupied by 36). Probe $i=3$: $(2+9)\%10 = 11\%10 = 1$ (occupied by 81). Probe $i=4$: $(2+16)\%10 = 18\%10 = 8$ (empty) → place at 8.

Final Hash Table

Quick Sort (first element as pivot)

List: 44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88

Pass 1 — pivot = 44. Partition so elements < 44 go left, > 44 go right. 44 settles into its sorted position: [33, 11, 40, 22] 44 [77, 90, 55, 60, 99, 88]

Left sublist [33, 11, 40, 22], pivot = 33: [11, 22] 33 [40] → gives [11, 22, 33, 40]

• sub [11, 22], pivot 11 → 11 [22] → [11, 22].

Right sublist [77, 90, 55, 60, 99, 88], pivot = 77: [55, 60] 77 [90, 99, 88]

• [55, 60], pivot 55 → 55 [60] → [55, 60].
• [90, 99, 88], pivot 90 → [88] 90 [99] → [88, 90, 99].

Combine: 11, 22, 33, 40, 44, 55, 60, 77, 88, 90, 99

Sorted array

11, 22, 33, 40, 44, 55, 60, 77, 88, 90, 99

Worst-case complexity

The worst case of quick sort is $O(n^2)$. It occurs when the pivot is always the smallest or largest element, producing maximally unbalanced partitions (one side empty). With first-element pivot this happens when the input is already sorted (ascending or descending).

Circular Queue

A circular queue is a linear data structure in which the last position is logically connected back to the first position, forming a circle. The array indices wrap around using modulo arithmetic: after the last index, the next index becomes 0.

How it overcomes the linear-queue limitation

In a simple linear queue implemented with an array, after several enqueue/dequeue operations the front and rear pointers keep moving forward. Even when the front portion of the array is empty, the rear may reach the end and the queue is wrongly reported as full — this wastes space (false overflow). A circular queue reuses the vacated front slots by wrapping rear (and front) around with $(\text{index} + 1) \bmod size$, so all array cells can be used.

Full and Empty conditions (array of size SIZE)

Using front and rear initialized to $-1$:

• Queue Empty: front == -1
• Queue Full: (rear + 1) % SIZE == front

Enqueue: rear = (rear + 1) % SIZE. Dequeue: if front == rear set both to $-1$, else front = (front + 1) % SIZE.

Radix Sort

Radix sort is a non-comparison, integer sorting algorithm that sorts numbers digit by digit, from the least significant digit (LSD) to the most significant digit. In each pass it distributes elements into 10 buckets (0–9) based on the current digit using a stable sort (counting sort), then collects them back.

Sorting: 170, 45, 75, 90, 802, 24, 2, 66

Pass 1 — units digit:

Collect → 170, 90, 802, 2, 24, 45, 75, 66

Pass 2 — tens digit:

Collect → 802, 2, 24, 45, 66, 170, 75, 90

Pass 3 — hundreds digit:

Collect → 2, 24, 45, 66, 75, 90, 170, 802

Sorted output

2, 24, 45, 66, 75, 90, 170, 802

Complexity comparison

Radix sort runs in $O(d \cdot (n + b))$ where $d$ = number of digits and $b$ = base (10). For fixed-width integers this is effectively $O(n)$ linear time, beating the $O(n \log n)$ lower bound of comparison-based sorts (merge sort, quick sort, heap sort). The trade-off is extra space $O(n + b)$ and that it works only for integers/fixed-length keys.

BFS vs DFS

Traversal from vertex 1

Edges: (1,2),(1,3),(2,4),(3,4),(4,5),(3,5). Adjacency (ascending order):

• 1 → 2, 3
• 2 → 1, 4
• 3 → 1, 4, 5
• 4 → 2, 3, 5
• 5 → 3, 4

BFS (queue, visit neighbours in ascending order): Start 1 → visit 2, 3 → from 2 visit 4 → from 3 visit 5. BFS order: 1, 2, 3, 4, 5

DFS (stack/recursion, ascending order): 1 → 2 → 4 → 3 → 5. (1, go to 2; from 2 go to 4; from 4 go to 3; from 3 go to 5.) DFS order: 1, 2, 4, 3, 5

Building and Deleting in a BST

Insert 50, 30, 70, 20, 40, 60, 80, 10

Applying the BST rule (smaller left, larger right):

          50
        /    \
      30      70
     /  \    /  \
   20    40 60   80
   /
  10

Delete node with key 30

Node 30 has two children (20 and 40). This is the deletion case for a node with two children: replace the node with its in-order successor (smallest key in the right subtree) — here the successor is 40 — then remove that successor node.

Replace 30 with 40; node 40 (a leaf) is deleted from its old place. Resulting tree:

          50
        /    \
      40      70
     /       /  \
   20      60    80
   /
  10

(Alternatively, the in-order predecessor 20 could be used; both are valid. In-order traversal of the result — 10, 20, 40, 50, 60, 70, 80 — remains sorted, confirming correctness.)

Tower of Hanoi

Move $n$ disks from source peg A to destination peg C using auxiliary peg B, never placing a larger disk on a smaller one.

Recursive algorithm

void hanoi(int n, char A, char C, char B) {
    if (n == 1) {                       // base case
        printf("Move disk 1 from %c to %c\n", A, C);
        return;
    }
    hanoi(n - 1, A, B, C);              // 1. move top n-1 from A to B
    printf("Move disk %d from %c to %c\n", n, A, C); // 2. move largest to C
    hanoi(n - 1, B, C, A);              // 3. move n-1 from B to C
}

Recurrence relation

Let $T(n)$ be the number of moves for $n$ disks. Moving $n-1$ disks twice plus one move for the largest disk:

$$T(n) = 2\,T(n-1) + 1, \qquad T(1) = 1.$$

Solving by back-substitution

$$T(n) = 2T(n-1) + 1$$ $$= 2[2T(n-2)+1] + 1 = 2^2 T(n-2) + 2 + 1$$ $$= 2^3 T(n-3) + 2^2 + 2 + 1$$ $$\vdots$$ $$= 2^{n-1} T(1) + (2^{n-2} + \dots + 2 + 1)$$ $$= 2^{n-1} + (2^{n-1} - 1) = 2^n - 1.$$

(Using $T(1)=1$ and the geometric sum $\sum_{k=0}^{n-1} 2^k = 2^n - 1$.)

Result

$$\boxed{T(n) = 2^n - 1}$$

So $n$ disks require $2^n - 1$ moves, giving time complexity $O(2^n)$.