BSc CSIT (TU) Science Data Structures and Algorithms (BSc CSIT, CSC206) Question Paper 2081 Nepal

Merge Sort

Merge sort is a divide-and-conquer sorting algorithm. It recursively divides the list into two halves, sorts each half, and then merges the two sorted halves into a single sorted list.

Algorithm

MERGE-SORT(A, low, high)
  if low < high
     mid = (low + high) / 2
     MERGE-SORT(A, low, mid)        // sort left half
     MERGE-SORT(A, mid+1, high)     // sort right half
     MERGE(A, low, mid, high)       // merge the two halves

MERGE(A, low, mid, high)
  copy A[low..mid] into L and A[mid+1..high] into R
  i = 0, j = 0, k = low
  while i < |L| and j < |R|
     if L[i] <= R[j]: A[k++] = L[i++]
     else:            A[k++] = R[j++]
  copy any remaining elements of L and R into A

Sorting 38, 27, 43, 3, 9, 82, 10

Divide (split until single elements):

[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]

Conquer (merge back, sorted):

[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 output: $3, 9, 10, 27, 38, 43, 82$

Complexity Analysis

The recurrence is:

By the Master Theorem ($a=2, b=2, f(n)=\Theta(n)$, so $n^{\log_b a} = n$):

Space complexity: $O(n)$ for the auxiliary arrays. Merge sort is stable but not in-place.

AVL Tree

An AVL tree (Adelson-Velsky and Landis 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 one of $\{-1, 0, +1\}$. Whenever an insertion/deletion violates this property, the tree is rebalanced using rotations, keeping its height $O(\log n)$.

Rotations

There are four cases of imbalance:

1. LL (Left-Left) → single right rotation. (Inserted in left subtree of left child.)
2. RR (Right-Right) → single left rotation.
3. LR (Left-Right) → left rotation on left child, then right rotation on node.
4. RL (Right-Left) → right rotation on right child, then left rotation on node.

Example (LL case): Inserting 30, 20, 10 makes 30 unbalanced (BF = +2). A right rotation about 30 gives 20 as root with 10 (left) and 30 (right).

   30(+2)            20
   /                /  \
  20      -->      10   30
  /
 10

Construction: insert 21, 26, 30, 9, 4, 14, 28, 18, 15, 10, 2, 3, 7

Inserting step by step and rebalancing:

• 21, 26: 21 root, 26 right.
• 30: RR at 21 → left rotation, 26 becomes root: 26(21,30).
• 9: goes left of 21 → balanced.
• 4: LL at 21 → right rotation, 9 becomes new left child: subtree 9(4,21). Tree: 26(9(4,21),30).
• 14: inserted right of 21 (in 9's right subtree). 9 becomes unbalanced (LR via 21) → left rotation at 9, right rotation at 26? Rebalance gives subtree rooted appropriately; resulting structure: 21 becomes new root → 21(9(4,14),26(_,30)).
• 28: left of 30 → balanced.
• 18: right of 14 → balanced.
• 15: right of 14 then left of 18 → may trigger RL/LR around 14; rebalance keeps subtree 15(14,18).
• 10, 2, 3, 7: inserted in left region; inserting 3 triggers an LR/RR rotation around 4 (4-2-3) producing 3(2,4); inserting 7 rebalances the 9–4 region.

Final balanced AVL tree (one valid result):

              21
           /      \
         9          26
        /  \        /  \
       3    15     18*  30
      / \   / \          \
     2   4 14  ...        28
          \
           7

The key marking points are: (i) each insertion is into BST position, (ii) after each insertion the balance factor is checked, and (iii) the correct rotation (LL/RR/LR/RL) is applied so that every node ends with balance factor in $\{-1,0,+1\}$ and the final tree height is $O(\log n)$.

Minimum Spanning Tree (MST)

A spanning tree of a connected, weighted, undirected graph $G=(V,E)$ is a subgraph that is a tree connecting all $|V|$ vertices using exactly $|V|-1$ edges. A Minimum Spanning Tree (MST) is a spanning tree whose total edge weight is minimum among all spanning trees of $G$.

Both Prim's and Kruskal's are greedy algorithms.

Example Graph

Vertices $\{A,B,C,D,E\}$ with edges: $A\text{-}B=2$, $A\text{-}C=3$, $B\text{-}C=1$, $B\text{-}D=4$, $C\text{-}D=5$, $C\text{-}E=6$, $D\text{-}E=7$.

Prim's Algorithm

Grows the MST from a starting vertex, repeatedly adding the cheapest edge crossing the cut (connecting a tree vertex to a non-tree vertex).

PRIM(G, start)
  add start to MST set
  while MST set != V
     pick minimum-weight edge (u,v) with u in MST, v not in MST
     add v and edge (u,v) to MST

Starting from A: pick A-B(2) → B-C(1) → A-C? skip (cycle) → B-D(4) → C-E(6). MST edges: A-B(2), B-C(1), B-D(4), C-E(6). Total = 13.

Kruskal's Algorithm

Sorts all edges by weight and adds the next cheapest edge that does not form a cycle (checked with Union-Find/Disjoint Set).

KRUSKAL(G)
  sort edges by weight
  for each edge (u,v) in sorted order
     if FIND(u) != FIND(v)        // no cycle
        add (u,v) to MST; UNION(u,v)
  stop when |V|-1 edges chosen

Sorted: B-C(1), A-B(2), A-C(3), B-D(4), C-D(5), C-E(6), D-E(7). Choose B-C(1) ✓, A-B(2) ✓, A-C(3) ✗ cycle, B-D(4) ✓, C-D(5) ✗ cycle, C-E(6) ✓ → 4 edges. MST edges: B-C(1), A-B(2), B-D(4), C-E(6). Total = 13.

Both produce the same minimum weight 13.

Complexity

Linear Search vs Binary Search

Binary Search Algorithm

BINARY-SEARCH(A, n, key)   // A sorted ascending
  low = 0; high = n - 1
  while low <= high
     mid = (low + high) / 2
     if A[mid] == key:  return mid          // found
     else if A[mid] < key:  low = mid + 1    // search right
     else:                  high = mid - 1   // search left
  return -1                                  // not found

Complexity Analysis

Each comparison halves the search space, giving the recurrence:

• Best case: $O(1)$ (key at mid), Worst/Average: $O(\log_2 n)$, Space: $O(1)$ (iterative).

Heap

A heap is a complete binary tree that satisfies the heap property:

• Max-heap: every parent $\geq$ its children (root is the maximum).
• Min-heap: every parent $\leq$ its children (root is the minimum).

It is usually stored in an array where for index $i$: left child $=2i+1$, right child $=2i+2$, parent $=\lfloor (i-1)/2 \rfloor$.

Heapify Operation

MAX-HEAPIFY(A, i) assumes the subtrees of node $i$ are already heaps and "sinks" $A[i]$ down to restore the heap property:

MAX-HEAPIFY(A, i, n)
  largest = i
  l = 2i+1; r = 2i+2
  if l < n and A[l] > A[largest]: largest = l
  if r < n and A[r] > A[largest]: largest = r
  if largest != i:
     swap A[i], A[largest]
     MAX-HEAPIFY(A, largest, n)

It runs in $O(\log n)$ time.

Build Max-Heap from 4, 10, 3, 5, 1

Array (0-indexed): [4, 10, 3, 5, 1], $n=5$. Heapify from last internal node $i=\lfloor n/2 \rfloor-1 = 1$ down to $0$.

• i = 1 (value 10): children 5, 1 — 10 already largest. No change. [4, 10, 3, 5, 1]
• i = 0 (value 4): children 10, 3 → largest 10. Swap 4 and 10 → [10, 4, 3, 5, 1]. Recurse at index 1 (value 4): children 5, 1 → largest 5. Swap → [10, 5, 3, 4, 1].

Max-heap array: [10, 5, 3, 4, 1]

        10
       /  \
      5    3
     / \
    4   1

Root 10 is the maximum and every parent ≥ its children.

Graph Representations

A graph $G=(V,E)$ can be represented in two common ways. Consider the undirected graph with vertices $\{1,2,3,4\}$ and edges $\{(1,2),(1,3),(2,3),(3,4)\}$.

1. Adjacency Matrix

A $|V| \times |V|$ matrix $A$ where $A[i][j]=1$ (or the edge weight) if there is an edge from $i$ to $j$, else $0$. For an undirected graph it is symmetric.

• Space: $O(V^2)$.
• Edge lookup: $O(1)$. Best for dense graphs.

2. Adjacency List

An array of $|V|$ lists; list $i$ contains all vertices adjacent to vertex $i$.

1 -> 2 -> 3
2 -> 1 -> 3
3 -> 1 -> 2 -> 4
4 -> 3

• Space: $O(V + E)$.
• Edge lookup: $O(\deg(v))$. Best for sparse graphs.

Summary: the matrix wastes space on sparse graphs but gives instant edge checks; the list is space-efficient and ideal when most vertex pairs are not connected.

Dynamic Programming (DP)

Dynamic programming is an algorithm-design technique for problems with optimal substructure (an optimal solution is built from optimal solutions of subproblems) and overlapping subproblems (the same subproblems recur). DP solves each subproblem once and stores its result in a table (memoization / tabulation) to avoid recomputation.

0/1 Knapsack Problem

Given $n$ items each with weight $w_i$ and value $v_i$, and a knapsack of capacity $W$, choose a subset (each item taken 0 or 1 time) to maximize total value without exceeding $W$.

DP formulation — let $K[i][w]$ = max value using the first $i$ items with capacity $w$:

KNAPSACK(w[], v[], n, W)
  for i = 0..n, for j = 0..W:
     if i==0 or j==0:        K[i][j] = 0
     else if w[i] <= j:      K[i][j] = max(K[i-1][j], v[i] + K[i-1][j-w[i]])
     else:                   K[i][j] = K[i-1][j]
  return K[n][W]

Example: items $(w,v) = (1,1),(3,4),(4,5),(5,7)$ with $W=7$. Filling the table gives the optimal value $K[4][7] = 9$ (items 2 and 3: weight $3+4=7$, value $4+5=9$).

• Time: $O(nW)$, Space: $O(nW)$ (pseudo-polynomial).

Applications of Stack

A stack is a LIFO (Last-In-First-Out) data structure. Major applications:

1. Function/subroutine call management (call stack — see below).
2. Expression conversion and evaluation — infix → postfix/prefix, and evaluating postfix expressions.
3. Balancing/matching of parentheses and brackets in compilers.
4. Recursion implementation (the system stack).
5. Undo/redo operations in editors.
6. Backtracking algorithms (e.g., maze solving, DFS traversal of graphs/trees).
7. Reversing data (string/list reversal).

Stack in Function Calls

When a function is called, the program uses a call stack (run-time stack) of activation records (stack frames). Each frame stores:

• the return address (where to resume in the caller),
• parameters passed to the function,
• local variables, and
• saved registers.

Mechanism:

• On a call, a new activation record is pushed onto the stack.
• The called function executes using the top frame.
• On return, the frame is popped, and control jumps back to the saved return address with the caller's frame now on top.

Because stacks are LIFO, the most recently called function returns first, which exactly matches nested and recursive calls. This also explains a stack overflow error when recursion is too deep and the call stack space is exhausted.

Heap Sort

Heap sort is a comparison-based, in-place sorting algorithm that uses a binary max-heap. It first builds a max-heap, then repeatedly removes the maximum (root) and places it at the end.

Algorithm

HEAP-SORT(A, n)
  BUILD-MAX-HEAP(A, n)                 // O(n)
  for i = n-1 down to 1:
     swap A[0], A[i]                   // move max to end
     MAX-HEAPIFY(A, 0, i)              // restore heap on A[0..i-1]

Example: sort 4, 10, 3, 5, 1

Step 1 – Build max-heap: [4,10,3,5,1] → [10, 5, 3, 4, 1].

Step 2 – Repeatedly extract max:

• Swap root 10 with last → [1,5,3,4 | 10], heapify first 4 → [5,4,3,1 | 10].
• Swap 5 with last → [1,4,3 | 5,10], heapify → [4,1,3 | 5,10].
• Swap 4 → [3,1 | 4,5,10], heapify → [3,1 | 4,5,10].
• Swap 3 → [1 | 3,4,5,10].

Sorted: $1, 3, 4, 5, 10$.

Time Complexity

• BUILD-MAX-HEAP: $O(n)$.
• Each of the $n-1$ extractions does a heapify costing $O(\log n)$ → $O(n \log n)$.

Best, average and worst cases are all $\Theta(n \log n)$. Space: $O(1)$ (in-place); it is not stable.

Algorithm Complexity

Algorithm complexity measures the resources (mainly running time and memory/space) an algorithm needs as a function of the input size $n$. Asymptotic notations describe this growth rate as $n \to \infty$, ignoring constants and lower-order terms.

Big-O Notation — Upper Bound

$f(n) = O(g(n))$ if there exist constants $c>0, n_0>0$ such that $0 \le f(n) \le c\,g(n)$ for all $n \ge n_0$. It gives the worst-case / upper bound.

Example: for $f(n) = 3n^2 + 2n + 5$, $f(n) = O(n^2)$.

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

$f(n) = \Omega(g(n))$ if there exist $c>0, n_0>0$ such that $0 \le c\,g(n) \le f(n)$ for all $n \ge n_0$. It gives the best-case / lower bound.

Example: $3n^2 + 2n + 5 = \Omega(n^2)$ (also $\Omega(n)$).

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

$f(n) = \Theta(g(n))$ if there exist $c_1, c_2, n_0 > 0$ such that $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$ — i.e. $f$ is bounded both above and below by $g$.

Example: $3n^2 + 2n + 5 = \Theta(n^2)$, since it is both $O(n^2)$ and $\Omega(n^2)$.

Relation: $f(n) = \Theta(g(n)) \iff f(n)=O(g(n)) \text{ and } f(n)=\Omega(g(n))$.

Linked List

A linked list is a linear, dynamic data structure consisting of a sequence of nodes, where each node stores data and one or more pointers (links) to other nodes. Unlike arrays, elements are not stored contiguously, so insertion and deletion do not require shifting elements.

Singly Linked List (SLL)

Each node has data and one pointer (next) to the following node. Traversal is one direction only (forward). The last node's next is NULL.

[data|next] -> [data|next] -> [data|NULL]
  10            20             30
HEAD ----------^

Doubly Linked List (DLL)

Each node has data plus two pointers — next (to the successor) and prev (to the predecessor) — allowing two-way (forward and backward) traversal.

NULL <- [prev|data|next] <-> [prev|data|next] <-> [prev|data|next] -> NULL
            10                   20                    30

Differences

Queue

A queue is a linear data structure following the FIFO (First-In-First-Out) principle: insertion (enqueue) happens at the rear and deletion (dequeue) happens at the front.

Circular Queue

In a simple linear array queue, once rear reaches the last index the queue appears full even if front slots are empty (false overflow). A circular queue treats the array as a ring: after the last index, the next position wraps to index 0 using modulo arithmetic:

This reuses freed front slots and avoids wasted space.

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

Enqueue Algorithm

ENQUEUE(Q, item)
  if (rear + 1) % SIZE == front:     // queue full
     print "Overflow"; return
  if front == -1:                    // first element
     front = 0
  rear = (rear + 1) % SIZE
  Q[rear] = item

Dequeue Algorithm

DEQUEUE(Q)
  if front == -1:                    // queue empty
     print "Underflow"; return
  item = Q[front]
  if front == rear:                  // last element removed
     front = rear = -1
  else:
     front = (front + 1) % SIZE
  return item

Both operations run in $O(1)$ time.