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

Minimum Spanning Tree (MST)

Given a connected, undirected, weighted graph $G = (V, E)$, a spanning tree is a subgraph that includes all vertices $V$ and is a tree (connected and acyclic, with exactly $|V|-1$ edges). A Minimum Spanning Tree is a spanning tree whose total edge-weight sum is the minimum among all spanning trees of $G$.

Example Graph

Vertices $\{A,B,C,D,E\}$ with edges:

1. Prim's Algorithm (vertex-growing, greedy)

Start from any vertex and repeatedly add the cheapest edge that connects a vertex inside the tree to a vertex outside it, until all vertices are included.

PRIM(G, start):
  T = { start };  cost = 0
  while T does not contain all vertices:
    pick min-weight edge (u,v) with u in T, v not in T
    add v to T; cost += weight(u,v)
  return T, cost

Trace (start = A):

• Add A. Cheapest crossing edge A-B(1) → add B.
• Crossing edges: A-C(3), B-C(3), B-D(6). Pick A-C(3) → add C.
• Crossing edges: C-E(2), C-D(4), B-D(6). Pick C-E(2) → add E.
• Crossing edges: C-D(4), D-E(5). Pick C-D(4) → add D.

MST edges: A-B, A-C, C-E, C-D, total weight $= 1+3+2+4 = 10$.

Using a binary heap / priority queue, Prim's runs in $O(E \log V)$.

2. Kruskal's Algorithm (edge-sorting, greedy)

Sort all edges by increasing weight; add each edge to the MST if it does not form a cycle (checked with a Disjoint-Set / Union-Find structure), until $|V|-1$ edges are chosen.

KRUSKAL(G):
  sort edges by weight
  MakeSet for each vertex
  T = {}
  for each edge (u,v) in sorted order:
    if Find(u) != Find(v):
      add (u,v) to T; Union(u,v)
  return T

Trace (sorted edges): A-B(1), C-E(2), A-C(3), B-C(3), C-D(4), D-E(5), B-D(6).

• A-B(1): no cycle → add.
• C-E(2): no cycle → add.
• A-C(3): no cycle → add.
• B-C(3): B and C already connected → reject (cycle).
• C-D(4): no cycle → add. Now 4 edges = $|V|-1$, stop.

MST edges: A-B, C-E, A-C, C-D, total weight $= 1+2+3+4 = 10$.

Kruskal's runs in $O(E \log E)$ (dominated by sorting).

Conclusion

Both algorithms are greedy and produce the same minimum total weight (10 here). Prim's grows a single tree from a vertex (better for dense graphs); Kruskal's picks globally cheapest safe edges (better for sparse graphs).

Hashing

Hashing is a technique that maps keys to indices of a fixed-size table (the hash table) using a hash function $h(k)$, allowing average $O(1)$ time for insertion, search and deletion. A good hash function is fast to compute, distributes keys uniformly, and minimizes collisions.

Example: $h(k) = k \bmod 10$ maps key 25 to slot 5.

Collision

A collision occurs when two distinct keys hash to the same slot, i.e. $h(k_1) = h(k_2)$. Since the number of possible keys usually exceeds table size, collisions are unavoidable and must be resolved.

1. Open Addressing

All elements are stored inside the table itself. On a collision, the algorithm probes for the next free slot. Requires load factor $\alpha < 1$.

(a) Linear probing: $h_i(k) = (h(k) + i) \bmod m$. Insert keys 12, 22, 32 with $m=10$: $h=2$ for all. 12→slot 2, 22→slot 3, 32→slot 4. Suffers from primary clustering.

(b) Quadratic probing: $h_i(k) = (h(k) + i^2) \bmod m$. Reduces primary clustering but causes secondary clustering.

(c) Double hashing: $h_i(k) = (h_1(k) + i \cdot h_2(k)) \bmod m$, where $h_2$ is a second hash function. Gives the best distribution.

2. Separate Chaining

Each slot holds a linked list of all keys that hash to it. Collisions simply append to the list; load factor can exceed 1.

Insert 12, 22, 32 (all → slot 2 with $m=10$):

[2] -> 12 -> 22 -> 32

Search/delete scans only the relevant chain.

Comparison

Average time for both is $O(1 + \alpha)$; worst case is $O(n)$ when all keys collide.

Sorting

Sorting is the process of arranging the elements of a list/array into a defined order (ascending or descending) based on a key. It improves searching efficiency and is fundamental to many algorithms.

Quick Sort

Quick sort is a divide-and-conquer, in-place comparison sort. It picks a pivot, partitions the array so all elements smaller than the pivot lie to its left and larger ones to its right, then recursively sorts the two partitions.

QUICKSORT(A, lo, hi):
  if lo < hi:
    p = PARTITION(A, lo, hi)
    QUICKSORT(A, lo, p-1)
    QUICKSORT(A, p+1, hi)

PARTITION(A, lo, hi):   // Lomuto, pivot = A[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

Example: sort [7, 2, 1, 6, 8, 5, 3, 4] (pivot = last element)

• Pivot = 4. After partition: [2,1,3,4,8,5,7,6] — 4 is in final position; left {2,1,3}, right {8,5,7,6}.
• Sort left [2,1,3] with pivot 3 → [1,2,3]; then [1,2] → [1,2].
• Sort right [8,5,7,6] with pivot 6 → [5,6,8,7]; left {5}, right {8,7} pivot 7 → [7,8].
• Combined result: [1,2,3,4,5,6,7,8].

Time Complexity Analysis

Let the partition step cost $O(n)$.

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

Average case is also $O(n \log n)$.

Worst case — pivot is always the smallest or largest element (e.g., an already-sorted array with last-element pivot), giving partitions of size 0 and $n-1$:

Space: $O(\log n)$ average recursion stack. Quick sort is not stable but is very fast in practice. Choosing a random or median-of-three pivot avoids the worst case.

Dynamic Programming (DP)

Dynamic programming is an algorithm-design technique for problems with optimal substructure (the optimal solution is built from optimal solutions of subproblems) and overlapping subproblems (the same subproblems recur). DP solves each subproblem once and stores the 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$, select a subset maximizing total value such that total weight $\le W$. Each item is taken 0 or 1 time (no fractions).

DP recurrence — let $K[i][c]$ be the best value using the first $i$ items with capacity $c$:

Example: $W = 5$; items $(w,v)$ = (1,1), (2,6), (3,10), (4,16).

Filling the table, the optimal selection is items with weights 2 and 3 (values 6 + 10 = 16)... checking item (4,16) alone gives 16, and (1,1)+(4,16) needs weight 5 → value 17. Best value = 17 (items of weight 1 and 4).

Time complexity: $O(nW)$, space $O(nW)$ (reducible to $O(W)$).

Applications of Stack

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

1. Function/subroutine call management (the call stack).
2. Expression conversion and evaluation — infix→postfix/prefix, and evaluating postfix expressions.
3. Balancing/matching of parentheses and syntax checking by compilers.
4. Recursion implementation (each recursive call pushes a frame).
5. Backtracking algorithms (maze solving, DFS, undo operations in editors).
6. Reversing a string or list; browser back-button history.

Stack in Function Calls

When a program calls a function, the system pushes an activation record (stack frame) onto the call stack. Each frame stores:

• the return address (where to resume in the caller),
• the actual parameters / arguments,
• local variables of the function,
• saved registers.

When the function returns, its frame is popped, control jumps back to the saved return address, and execution continues in the caller. Because the most recently called function finishes first, the LIFO discipline of the stack naturally models nested and recursive calls.

Example: main() calls f() which calls g().

Call stack (top = most recent):
  | g() frame |  <- top, executes first to finish
  | f() frame |
  | main frame|

When g() returns, its frame is popped and control returns to f(), then to main(). If recursion is too deep, the call stack overflows (stack overflow).

Heap Sort

Heap sort is a comparison-based sort that uses a binary heap. A max-heap is a complete binary tree where every parent $\ge$ its children, so the maximum is at the root. Stored in an array, node $i$ has children $2i+1$ and $2i+2$.

Algorithm:

1. Build a max-heap from the input array (heapify from the last internal node up).
2. Repeatedly swap the root (largest) with the last element, shrink the heap by one, and sift-down (heapify) the new root.

HEAPSORT(A, n):
  for i = n/2 - 1 downto 0:   // build max-heap
    HEAPIFY(A, n, i)
  for i = n-1 downto 1:
    swap A[0], A[i]           // move max to end
    HEAPIFY(A, i, 0)          // restore heap on A[0..i-1]

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

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

• Build max-heap → [10, 5, 3, 4, 1].
• Swap 10↔1, heapify [1,5,3,4] → [5,4,3,1] | 10. Array: [5,4,3,1,10].
• Swap 5↔1, heapify [1,4,3] → [4,1,3] | 5,10. Array: [4,1,3,5,10].
• Swap 4↔3, heapify [3,1] → [3,1]. Array: [3,1,4,5,10].
• Swap 3↔1 → [1,3,4,5,10]. Sorted: [1,3,4,5,10].

Time Complexity

• Building the heap: $O(n)$.
• Each of the $n$ extractions does a heapify costing $O(\log n)$ → $O(n \log n)$.

Total = $O(n \log n)$ in best, average and worst cases. It is in-place ($O(1)$ extra space) but not stable.

Algorithm Complexity

Algorithm complexity measures the resources an algorithm consumes as a function of input size $n$ — time complexity (number of basic operations) and space complexity (memory used). Asymptotic notations describe the growth rate for large $n$, ignoring constants and lower-order terms.

1. Big-O — Upper Bound (worst case)

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

It gives an upper bound on growth. Example: $3n^2 + 5n + 2 = O(n^2)$, since for large $n$ the $n^2$ term dominates and $3n^2+5n+2 \le 4n^2$ for $n \ge 6$. Linear search is $O(n)$.

2. Big-Omega ($\Omega$) — Lower Bound (best case)

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

It gives a lower bound. Example: $3n^2 + 5n + 2 = \Omega(n^2)$. Any comparison sort is $\Omega(n \log n)$.

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

$f(n) = \Theta(g(n))$ if it is both $O(g(n))$ and $\Omega(g(n))$, i.e. constants $c_1, c_2, n_0$ exist with

It gives an exact (tight) asymptotic bound. Example: $3n^2 + 5n + 2 = \Theta(n^2)$.

Summary

Linked List

A linked list is a linear dynamic data structure made of nodes, where each node stores data and one or more pointers/links to other nodes. Unlike arrays, memory is allocated dynamically (non-contiguous), allowing efficient insertion/deletion without shifting elements, though random access is $O(n)$.

Singly Linked List (SLL)

Each node has data and a single next pointer to the following node; the last node points to NULL. Traversal is one-directional (forward only).

HEAD -> [10|*] -> [20|*] -> [30|NULL]

Doubly Linked List (DLL)

Each node has data, a next pointer, and a prev pointer to the previous node. Traversal is bidirectional.

NULL <- [|10|] <-> [|20|] <-> [|30|] -> NULL

Differences

Queue

A queue is a linear FIFO (First-In-First-Out) data structure: elements are inserted at the rear (enqueue) and removed from the front (dequeue). Examples: print spooling, CPU scheduling.

Circular Queue

In a simple array queue, once rear reaches the last index, no new element can be added even if front slots are free (false overflow). A circular queue treats the array as a ring: after the last index, indices wrap around to 0 using modulo arithmetic, reusing vacated front slots.

With size $m$:

• Full when (rear + 1) % m == front.
• Empty when front == -1.

Enqueue Algorithm

ENQUEUE(Q, m, x):
  if (rear + 1) % m == front:
    print "Queue Overflow"; return
  if front == -1:          // first element
    front = 0
  rear = (rear + 1) % m
  Q[rear] = x

Dequeue Algorithm

DEQUEUE(Q, m):
  if front == -1:
    print "Queue Underflow"; return
  x = Q[front]
  if front == rear:        // only one element left
    front = rear = -1
  else:
    front = (front + 1) % m
  return x

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

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. Every correct recursion needs:

1. a base case that stops the recursion, and
2. a recursive case that moves toward the base case.

Recursive Factorial

FACTORIAL(n):
  if n <= 1:          // base case
    return 1
  else:
    return n * FACTORIAL(n - 1)   // recursive case

Trace for FACTORIAL(4): $4 \times 3 \times 2 \times 1 = 24$.

Role of the Stack in Recursion

Each recursive call creates a new activation record (stack frame) pushed onto the call stack, holding that call's parameters, local variables and return address. The calls expand until the base case is reached; then the frames are popped in LIFO order as each call returns its value to its caller.

Push:  F(4) -> F(3) -> F(2) -> F(1)=1
Pop:   F(2)=2 -> F(3)=6 -> F(4)=24

The stack thus remembers the pending multiplications. If the base case is missing or recursion is too deep, the stack runs out of memory → stack overflow.

Bubble Sort vs Selection Sort

Both are simple $O(n^2)$ comparison sorts but differ in mechanism.

Bubble Sort

Repeatedly steps through the list, comparing adjacent pairs and swapping them if out of order, so the largest unsorted element "bubbles" to the end each pass.

Example on [5, 1, 4, 2] (ascending):

• Pass 1: (5,1)→swap [1,5,4,2]; (5,4)→swap [1,4,5,2]; (5,2)→swap [1,4,2,5].
• Pass 2: [1,4,2,5] → (4,2)→swap [1,2,4,5].
• Pass 3: no swaps → sorted [1,2,4,5].

Selection Sort

Finds the minimum of the unsorted part and places it at the beginning by one swap per pass.

Example on [5, 1, 4, 2]:

• Pass 1: min = 1, swap with 5 → [1,5,4,2].
• Pass 2: min of {5,4,2} = 2, swap → [1,2,4,5].
• Pass 3: min of {4,5} = 4 → [1,2,4,5]. Sorted.

Comparison

Binary Tree Traversals

Traversal means visiting every node of a tree exactly once in a systematic order. The three depth-first traversals differ in when the root is visited relative to its subtrees.

Example Tree

          A
         / \
        B   C
       / \   \
      D   E   F

1. Inorder (Left, Root, Right)

Traverse left subtree → visit root → traverse right subtree.

INORDER(node): if node: INORDER(left); visit(node); INORDER(right)

Result: D B E A C F. (For a binary search tree, inorder gives sorted order.)

2. Preorder (Root, Left, Right)

Visit root → traverse left → traverse right.

PREORDER(node): if node: visit(node); PREORDER(left); PREORDER(right)

Result: A B D E C F. (Used to copy a tree / get prefix expression.)

3. Postorder (Left, Right, Root)

Traverse left → traverse right → visit root.

POSTORDER(node): if node: POSTORDER(left); POSTORDER(right); visit(node)

Result: D E B F C A. (Used to delete a tree / evaluate postfix expression.)

Each traversal runs in $O(n)$ time for $n$ nodes.