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

Graph

A graph $G = (V, E)$ is a non-linear data structure consisting of a finite set of vertices (nodes) $V$ and a set of edges $E$, where each edge connects a pair of vertices. Graphs may be directed or undirected, and weighted or unweighted. They model networks such as road maps, social networks, and the web.

Breadth First Search (BFS)

BFS explores a graph level by level, visiting all neighbours of a vertex before moving to the next level. It uses a queue (FIFO).

BFS(G, s):
    mark all vertices unvisited
    create empty queue Q
    visit s; enqueue s
    while Q is not empty:
        u = dequeue(Q)
        for each neighbour v of u:
            if v is unvisited:
                visit v; enqueue v

Example — graph with edges A-B, A-C, B-D, C-D, D-E starting at A: BFS order = A, B, C, D, E.

Applications: shortest path in unweighted graphs, finding connected components, level-order traversal, web crawling, peer-to-peer networks, GPS navigation.

Depth First Search (DFS)

DFS explores as deep as possible along each branch before backtracking. It uses a stack (or recursion).

DFS(G, u):
    visit u; mark u visited
    for each neighbour v of u:
        if v is unvisited:
            DFS(G, v)

Example — same graph starting at A: DFS order = A, B, D, C, E (one valid order).

Applications: topological sorting, cycle detection, finding connected components and strongly connected components, solving mazes/puzzles, path finding.

Complexity

Both run in $O(V + E)$ time using an adjacency list and $O(V^2)$ using an adjacency matrix.

Stack

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle: the last element inserted is the first removed. Insertion and deletion happen at one end called the top.

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() — check whether the stack is empty.
• isFull() — check whether the stack is full (array implementation).

Infix to Postfix Conversion Algorithm

for each symbol in infix expression:
    if symbol is an operand:
        append it to output
    else if symbol is '(':
        push it onto stack
    else if symbol is ')':
        pop and append until '(' is popped
    else (symbol is an operator):
        while stack not empty and top has >= precedence:
            pop and append to output
        push symbol
after scanning, pop and append all remaining operators

Evaluating the Postfix Expression

The given postfix expression is A B + C * D -. Scan left to right; push operands, and on an operator pop two operands, apply, push result.

Result: $((A+B) \times C) - D$, which is the single value left on the stack.

With numeric values, say $A=2, B=3, C=4, D=5$: $(2+3)=5$, $5 \times 4 = 20$, $20 - 5 = 15$.

Merge Sort

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

MergeSort(A, l, r):
    if l < r:
        m = (l + r) / 2
        MergeSort(A, l, m)
        MergeSort(A, m+1, r)
        Merge(A, l, m, r)

Merge(A, l, m, r):
    copy A[l..m] into L[], A[m+1..r] into R[]
    merge L and R back into A[l..r] in sorted order

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

Divide phase (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]

Merge phase (combine in sorted order):

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

Sorted result: 3, 9, 10, 27, 38, 43, 82.

Complexity Analysis

The recurrence is $T(n) = 2T(n/2) + O(n)$. By the Master Theorem this gives:

• Best, average and worst case: $O(n \log n)$ (it always divides evenly).
• Space: $O(n)$ auxiliary array for merging.
• It is a stable sort but not in-place.

Recursion

Recursion is a programming technique in which a function calls itself (directly or indirectly) to solve a problem by breaking it into smaller sub-problems of the same type. Every recursion must have a base case (stopping condition) and a recursive case that moves toward the base case.

Recursive Factorial

factorial(n):
    if n == 0 or n == 1:      // base case
        return 1
    else:                      // recursive case
        return n * factorial(n - 1)

For example $factorial(4) = 4 \times 3 \times 2 \times 1 = 24$.

Role of the Stack in Recursion

Each recursive call is placed on the program's call stack (activation record / stack frame), storing the parameters, local variables and the return address. The calls stack up until the base case is reached; then the frames are popped in LIFO order as each call returns its value to the caller. Thus the stack manages the suspended state of every pending call—if the base case is missing, the stack grows without bound causing a stack overflow.

Bubble Sort vs Selection Sort

Example — sort 5, 1, 4, 2

Bubble sort (pass 1, adjacent compares): 5,1,4,2 → 1,5,4,2 → 1,4,5,2 → 1,4,2,5; subsequent passes give 1,2,4,5.

Selection sort: find min=1 → swap with first: 1,5,4,2; min of rest=2 → 1,2,4,5; min of rest=4 (in place) → 1,2,4,5. Sorted.

Summary: Bubble sort swaps adjacent pairs; selection sort selects the minimum and does one swap per pass. Both are $O(n^2)$, but selection sort performs fewer swaps.

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.

• Inorder (Left, Root, Right): visit left subtree, then root, then right subtree. For a BST this gives nodes in sorted order.
• Preorder (Root, Left, Right): visit root first, then left subtree, then right subtree. Used to copy a tree / get prefix expression.
• Postorder (Left, Right, Root): visit left subtree, then right subtree, then root last. Used to delete a tree / get postfix expression.

Example Binary Tree

          1
         / \
        2   3
       / \
      4   5

• Inorder: 4, 2, 5, 1, 3
• Preorder: 1, 2, 4, 5, 3
• Postorder: 4, 5, 2, 3, 1

Inorder(node):
    if node != null:
        Inorder(node.left)
        visit(node)
        Inorder(node.right)

(Preorder and postorder simply move the visit(node) statement to first or last.)

Linear Search vs Binary Search

Binary Search Algorithm

BinarySearch(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 Analysis

Each comparison halves the search space, giving the recurrence $T(n) = T(n/2) + O(1)$, which solves to:

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

Heap

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

• Max-heap: every parent node is greater than or equal to its children (largest element at the root).
• Min-heap: every parent node is less than or equal to its children (smallest at the root).

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

Heapify restores the heap property at a node by comparing it with its children and swapping it with the larger child (for a max-heap), then recursively heapifying the affected subtree. It runs in $O(\log n)$.

Building a Max-Heap from 4, 10, 3, 5, 1

Insert into a complete tree (array indices 0–4):

        4
       / \
     10   3
     / \
    5   1

Apply heapify to internal nodes from the last (index 1) up to the root (index 0):

• Heapify index 1 (value 10): children 5 and 1; 10 ≥ both → no change.
• Heapify index 0 (value 4): children 10 and 3; largest is 10 → swap 4 and 10.

        10
       /  \
      4    3
     / \
    5   1

• Continue heapifying index 1 (now value 4): children 5 and 1; largest is 5 → swap 4 and 5.

        10
       /  \
      5    3
     / \
    4   1

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

Graph Representations

Consider an 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 an edge exists between $i$ and $j$, else $0$.

• Space: $O(V^2)$.
• Edge lookup: $O(1)$.
• Best for dense graphs; for undirected graphs the matrix is symmetric.

2. Adjacency List

An array (or list) of $V$ lists, where each list stores the neighbours of that vertex.

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

• Space: $O(V + E)$.
• Edge lookup: $O(\text{degree})$.
• Best for sparse graphs; efficiently lists all neighbours.

Conclusion: use an adjacency matrix for dense graphs needing fast edge checks, and an adjacency list for sparse graphs to save memory.

Dynamic Programming

Dynamic programming (DP) is an algorithm-design technique for solving problems that have overlapping subproblems and optimal substructure. Instead of recomputing the same subproblems, DP solves each subproblem once and stores its result in a table (memoization or bottom-up tabulation), then reuses it.

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 whole or not at all) to maximize total value without exceeding $W$.

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

Example: items (w,v) = (1,1), (3,4), (4,5), capacity $W=4$.

• Take items 1 and 2: weight $1+3=4 \le 4$, value $1+4 = 5$.
• Take item 3 alone: weight 4, value 5.
• Best value = 5.

Complexity: $O(nW)$ time and space — pseudo-polynomial, far better than the $O(2^n)$ brute-force approach because subproblem results are reused.

Applications of Stack

A stack (LIFO structure) is used in many areas:

1. Function / subroutine call management — the call stack stores return addresses and local data.
2. Expression conversion and evaluation — infix to postfix/prefix, and evaluating postfix expressions.
3. Parenthesis / bracket matching — checking balanced symbols in compilers.
4. Undo / redo operations in editors.
5. Backtracking — maze solving, recursion, DFS traversal.
6. Reversing data (string, list).
7. Browser back-button history.

Stack in Function Calls

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

• the return address (where to resume after the call),
• the parameters passed,
• the local variables, and
• saved registers.

If that function calls another, a new frame is pushed on top. When a function finishes, its frame is popped, control returns to the stored return address, and execution resumes in the caller. Because returns happen in reverse order of calls, the LIFO discipline of the stack exactly matches nested function-call behaviour, which is also why recursion works naturally.

Heap Sort

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

HeapSort(A, n):
    BuildMaxHeap(A, n)              // O(n)
    for i = n-1 down to 1:
        swap(A[0], A[i])           // move max to its final position
        heapify(A, 0, i)           // restore heap on reduced array

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

Step 1 — Build max-heap: array becomes 10, 5, 3, 4, 1.

        10
       /  \
      5    3
     / \
    4   1

Step 2 — Repeatedly extract max:

• Swap 10↔1, heapify first 4 → 5,4,3,1 | 10
• Swap 5↔1, heapify first 3 → 4,1,3 | 5,10
• Swap 4↔3, heapify first 2 → 3,1 | 4,5,10
• Swap 3↔1 → 1 | 3,4,5,10

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

Time Complexity

• Building the heap: $O(n)$.
• Each of the $n$ extractions costs an $O(\log n)$ heapify.
• Total:

in best, average and worst cases.

• Space: $O(1)$ (in-place); it is not stable.