BSc CSIT (TU) Science Data Structures and Algorithms (BSc CSIT, CSC206) Question Paper 2077 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 sorted halves

MERGE(A, low, mid, high):
    i = low; j = mid+1; k = 0
    create temp array B
    while i <= mid and j <= high:
        if A[i] <= A[j]: B[k++] = A[i++]
        else:            B[k++] = A[j++]
    copy remaining elements of left/right half into B
    copy B back into A[low..high]

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

Divide (top-down split):

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

Merge (bottom-up combine):

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

Complexity Analysis

The recurrence is:

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

• Space complexity: $O(n)$ (needs an auxiliary array for merging).
• It is a stable sort but not in-place.

AVL Tree

An AVL tree (named after Adelson-Velsky and Landis) 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.

Balance factor of a node $= \text{height(left subtree)} - \text{height(right subtree)}$, and must be one of $\{-1, 0, +1\}$. If an insertion/deletion makes it $\pm 2$, a rotation restores balance. This keeps the height $O(\log n)$, so search/insert/delete are all $O(\log n)$.

Rotations

There are four cases:

1. LL (Left-Left) – imbalance in left subtree of left child. Fix with a single right rotation.
2. RR (Right-Right) – imbalance in right subtree of right child. Fix with a single left rotation.
3. LR (Left-Right) – imbalance in right subtree of left child. Fix with left rotation on child, then right rotation on node.
4. RL (Right-Left) – imbalance in left subtree of right child. Fix with right rotation on child, then left rotation on node.

Example (LL): inserting 10, 5, 1 makes 10 unbalanced (BF=+2). A right rotation makes 5 the root with children 1 and 10.

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

• 21, 26 -> 21 root, 26 right.
• 30 -> 21 becomes unbalanced (RR). Left-rotate -> root 26, children 21, 30.
• 9, 4 -> insert 9 (left of 21), then 4 makes 21 unbalanced (LL). Right-rotate at 21 -> 9 with children 4, 21. Tree: 26(9(4,21),30).
• 14 -> goes right of 9's subtree under 21's left; tree stays balanced: 26(9(4,21(14,_)),30).
• 28, 18 -> 28 right of 30; 18 left of 21. Now node 26 becomes unbalanced (LR via 9-21). Perform LR: left-rotate at 9, right-rotate at 26 -> new root 21, left child 9(4,18,14), right child 26(,30(28)). Resulting tree: **21(9(4,14(,18)),26(,30(28,)))**. (Heights rebalanced.)
• 15 -> inserted near 14; triggers a rotation in the left subtree restoring balance.
• 10 -> inserted under 9's right; subtree rebalanced.
• 2, 3 -> 2 left of 4; 3 makes 4 unbalanced (LR), rotate so 3 becomes parent of 2 and 4.
• 7 -> inserted, local rebalancing as needed.

Final AVL tree (one valid balanced result):

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

All balance factors lie in $\{-1,0,+1\}$, height $= O(\log n)$.

(Note: minor structural variation is acceptable as long as BST ordering holds and every balance factor is within $\pm 1$.)

Minimum Spanning Tree (MST)

A spanning tree of a connected, undirected, weighted graph $G$ is a subgraph that is a tree and includes all $n$ vertices using exactly $n-1$ edges. A Minimum Spanning Tree (MST) 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):

Prim's Algorithm (vertex-based, greedy)

Grows the tree from a starting vertex, repeatedly adding the cheapest edge that connects a vertex inside the tree to one outside.

start with any vertex (say A)
repeat n-1 times:
    pick the minimum-weight edge crossing from
    the visited set to an unvisited vertex; add it.

Trace from A: add A-B(1) -> B-D(2) -> B-C(3) -> D-E(6). MST edges: A-B, B-D, B-C, D-E; total weight = 1+2+3+6 = 12.

Time complexity: $O(E \log V)$ with a binary heap, $O(V^2)$ with an adjacency matrix.

Kruskal's Algorithm (edge-based, greedy)

Sorts all edges by weight and adds them one by one, skipping any edge that forms a cycle (detected with a Disjoint-Set/Union-Find structure).

sort edges by increasing weight
for each edge (u,v):
    if u and v are in different sets:
        add edge; union(u,v)
    stop when n-1 edges are chosen

Trace: A-B(1) ✓, B-D(2) ✓, B-C(3) ✓, A-C(4) ✗cycle, C-D(5) ✗cycle, D-E(6) ✓. MST edges: A-B, B-D, B-C, D-E; total weight = 12 (same MST).

Time complexity: $O(E \log E)$ dominated by sorting.

Comparison

Linear Search vs Binary Search

Binary Search Algorithm

BINARY_SEARCH(A, n, key):
    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 half
        else: high = mid - 1                // search left half
    return -1                               // not found

Complexity

Each comparison halves the remaining elements, so after $k$ steps the size is $n/2^k$. The search ends when $n/2^k = 1 \Rightarrow k = \log_2 n$.

• Best case: $O(1)$ (key at middle); Worst/Average: $O(\log n)$; Space: $O(1)$ iterative.

Heap

A heap is a complete binary tree (all levels filled except possibly the last, filled left to right) that satisfies the heap property:

• Max-heap: every parent $\geq$ its children (largest element at root).
• Min-heap: every parent $\leq$ its children (smallest element at root).

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

Heapify Operation

Heapify (sift-down) restores the heap property at a node assuming its subtrees are already heaps. For a max-heap, it compares the node with its children, swaps with the larger child, and repeats downward. It runs in $O(\log n)$ time.

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)

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

Array (as complete tree): [4, 10, 3, 5, 1]. Heapify from the last internal node ($i = \lfloor n/2 \rfloor - 1 = 1$) up to the root.

• i = 1 (value 10): children 5, 1; 10 already largest -> no change.
• i = 0 (value 4): children 10, 3; largest is 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].

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

        10
       /  \
      5    3
     / \
    4   1

Root = 10 (maximum), heap property satisfied.

Graph Representations

A graph $G=(V,E)$ can be stored mainly in two ways. Consider this undirected graph:

   1 --- 2
   |   / |
   |  /  |
   3 --- 4
Edges: (1,2), (1,3), (2,3), (2,4), (3,4)

1. Adjacency Matrix

A $V \times V$ matrix $A$ where $A[i][j] = 1$ (or the edge weight) if an edge exists from $i$ to $j$, else $0$.

• Space: $O(V^2)$.
• Edge lookup: $O(1)$.
• Symmetric for undirected graphs. Wasteful for sparse graphs.

2. Adjacency List

An array of $V$ lists; list $i$ stores the neighbours of vertex $i$.

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

• Space: $O(V + E)$ — efficient for sparse graphs.
• Edge lookup: $O(\text{degree})$.
• Easy to iterate over a vertex's neighbours.

Comparison

Dynamic Programming (DP)

Dynamic programming is an algorithm-design technique for solving problems by breaking them into overlapping subproblems and solving each subproblem only once, storing its result (in a table) to avoid recomputation. It applies when a problem has:

1. Optimal substructure – an optimal solution is built from optimal solutions of subproblems.
2. Overlapping subproblems – the same subproblems recur many times.

Results are stored via memoization (top-down) or tabulation (bottom-up).

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 (each item taken 0 or 1 times — cannot be split) maximizing total value without exceeding $W$.

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

with $K[0][w] = 0$.

Example: $W = 5$; items $(w,v) = (1,1),(2,6),(3,10),(5,16)$. Candidate subsets within capacity 5: items {2,3} -> weight $2+3=5$, value $6+10=16$; item {4} alone -> weight 5, value 16; items {1,3} -> weight 4, value 11. The maximum is therefore $K[4][5] = \textbf{16}$ (achieved by taking the items of weight 2 and 3).

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

Time complexity: $O(nW)$ (pseudo-polynomial).

Applications of Stack

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

1. Function call management (call/runtime stack).
2. Expression conversion and evaluation — infix to postfix/prefix, and evaluating postfix expressions.
3. Parenthesis / bracket matching in compilers.
4. Recursion implementation.
5. Undo/redo operations in editors.
6. Backtracking (maze solving, DFS, browser back button).

Stack in Function Calls

When a function is called, the system pushes an activation record (stack frame) onto the call stack. Each frame contains:

• the return address (where to resume after the call),
• actual parameters / arguments,
• local variables,
• saved registers.

How it works:

1. On a call, a new frame is pushed with the arguments and return address.
2. The called function executes using its own frame on top of the stack.
3. For nested/recursive calls, each call pushes a new frame, so frames stack up.
4. When a function returns, its frame is popped, the return value is passed back, and control jumps to the saved return address.

Because the most recently called function is the first to finish, the LIFO behaviour of the stack exactly matches function-call/return order. (Excessive recursion exhausts the stack -> stack overflow.)

Heap Sort

Heap sort sorts an array by first building a max-heap, then repeatedly removing the maximum (the root) and placing it at the end of the array.

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 the end
        MAX_HEAPIFY(A, 0, i)        // restore heap on reduced size

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

Build max-heap -> [10, 5, 3, 4, 1].

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

Time Complexity

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

• Space: $O(1)$ (in-place). Not stable.

Algorithm Complexity

Algorithm complexity measures the amount of resources an algorithm needs as a function of input size $n$:

• Time complexity – number of basic operations executed.
• Space complexity – amount of memory used.

Asymptotic notations describe the growth rate of these functions for large $n$, ignoring constants and lower-order terms.

Big-O (Upper Bound)

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

Describes the worst-case (maximum) growth. Example: $3n^2 + 5n + 2 = O(n^2)$.

Big-Omega $\Omega$ (Lower Bound)

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

Describes the best-case (minimum) growth. Example: $3n^2 + 5n = \Omega(n^2)$.

Big-Theta $\Theta$ (Tight Bound)

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

It means $f$ is both $O(g)$ and $\Omega(g)$ — an exact growth rate. Example: $3n^2 + 5n + 2 = \Theta(n^2)$.

Linked List

A linked list is a linear data structure where elements (nodes) are stored at non-contiguous memory locations; each node holds data and one or more pointers to other nodes. Unlike arrays, it allows dynamic size and $O(1)$ insertion/deletion given a node reference, but only sequential access.

Singly Linked List (SLL)

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

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

Doubly Linked List (DLL)

Each node has data, a next pointer, and a prev pointer to the previous node. Traversal is possible in both directions.

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

Difference

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). The element inserted first is removed first.

Circular Queue

In a simple array queue, once rear reaches the end the space freed at the front cannot be reused (false overflow). A circular queue treats the array as circular: after the last index, indices wrap around to 0 using modulo arithmetic ($\%\, size$). This reuses vacated front slots.

• Empty condition: front == -1.
• Full condition: (rear + 1) % size == front.

Enqueue

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

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

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