BSc CSIT (TU) Science Data Structures and Algorithms (BSc CSIT, CSC206) Question Paper 2075 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 relationships such as networks, maps, and dependencies.

Breadth First Search (BFS)

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

BFS(G, s):
  mark all vertices unvisited
  visited[s] = true; enqueue(Q, s)
  while Q not empty:
     u = dequeue(Q)
     visit u
     for each neighbour v of u:
        if not visited[v]:
           visited[v] = true
           enqueue(Q, v)

Example: For the graph with edges A-B, A-C, B-D, C-D, D-E starting at A, BFS order is: A, B, C, D, E.

Applications: shortest path in unweighted graphs, finding connected components, peer-to-peer networks, web crawling, 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):
  visited[u] = true
  visit u
  for each neighbour v of u:
     if not visited[v]:
        DFS(G, v)

Example: For the same graph starting at A, one DFS order is: A, B, D, C, E.

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

Comparison

Time complexity of both: $O(V + E)$ using adjacency lists.

Stack and its Operations

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$ on top.
• pop() — remove and return the top element.
• peek() / top() — return top element without removing.
• isEmpty() — check if stack is empty.
• isFull() — check if stack is full (array implementation).

Infix to Postfix Conversion Algorithm

InfixToPostfix(expr):
  create empty stack S, empty output string P
  for each symbol x in expr:
     if x is operand:  append x to P
     else if x == '(': push x onto S
     else if x == ')':
        while top(S) != '(':  pop and append to P
        pop '(' (discard)
     else (x is operator):
        while S not empty and precedence(top(S)) >= precedence(x):
           pop and append to P
        push x onto S
  while S not empty: pop and append to P
  return P

Precedence: ^ > * / > + -.

Postfix Evaluation of A B + C * D -

The expression is already in postfix. Using sample values $A=2,\ B=3,\ C=4,\ D=5$:

Result = 15, i.e. the expression evaluates to $((A+B)\times C) - D$.

Evaluation rule: scan left to right; push operands; on an operator pop the top two operands, apply the operator (second-popped OP first-popped), and push the result. The final stack value is the answer.

Merge Sort

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

Algorithm

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[]
  i = j = 0, k = l
  while i < |L| and j < |R|:
     if L[i] <= R[j]: A[k++] = L[i++]
     else:            A[k++] = R[j++]
  copy remaining elements of L and R into A

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

Divide:

[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 (conquer):

[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 $T(n) = 2T(n/2) + O(n)$, which by the Master Theorem gives:

• Best, average, worst case: $O(n \log n)$ (always divides in half).
• Space: $O(n)$ auxiliary array (not in-place).
• Stability: stable sort.

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. A valid recursive function must have a base case (stopping condition) and a recursive case that moves toward the base case.

Recursive Factorial Algorithm

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

For example, $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 (an activation record / stack frame) holding the parameters, local variables and return address. Frames stack up as calls go deeper:

Factorial(4) -> 4 * Factorial(3)
   Factorial(3) -> 3 * Factorial(2)
      Factorial(2) -> 2 * Factorial(1)
         Factorial(1) -> 1   (base case reached)

When the base case is reached, frames are popped in LIFO order, each returning its value to the caller: $1 \to 2 \to 6 \to 24$. Thus the stack stores the suspended calls and enables correct unwinding; excessive recursion depth causes a stack overflow.

Bubble Sort vs Selection Sort

Examples on list 5, 2, 4, 1

Bubble Sort (compare/swap adjacent):

Pass 1: (5,2)->2,5,4,1  (5,4)->2,4,5,1  (5,1)->2,4,1,5
Pass 2: 2,4,1,5 -> (4,1)-> 2,1,4,5
Pass 3: 2,1,4,5 -> (2,1)-> 1,2,4,5  -> sorted

Selection Sort (pick minimum each pass):

Find min(5,2,4,1)=1 -> swap with pos0: 1,2,4,5
Find min(2,4,5)=2   -> already in place: 1,2,4,5
Find min(4,5)=4     -> in place: 1,2,4,5  -> sorted

Both give 1, 2, 4, 5, but selection sort uses far fewer swaps while bubble sort does more adjacent swaps.

Binary Tree Traversals

Tree traversal means visiting every node exactly once in a systematic order. For a binary tree, the three depth-first traversals differ in when the root is visited relative to its left and right subtrees.

• Inorder (Left, Root, Right): traverse left subtree, visit root, traverse right subtree. For a BST this yields nodes in sorted order.
• Preorder (Root, Left, Right): visit root first, then left, then right. Used to copy a tree or produce prefix expressions.
• Postorder (Left, Right, Root): traverse left, traverse right, visit root last. Used to delete a tree or produce postfix expressions.

Example Binary Tree

          A
        /   \
       B     C
      / \     \
     D   E     F

Inorder (L, Root, R): D, B, E, A, C, F

Preorder (Root, L, R): A, B, D, E, C, F

Postorder (L, R, Root): D, E, B, F, C, A

Each traversal recursively applies the same rule to every subtree.

Linear Search vs Binary Search

Binary Search Algorithm

BinarySearch(A, 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

Example: searching for 23 in [2, 5, 8, 12, 16, 23, 38] — mid=12<23 → right; mid=23 → found at index 5.

Complexity Analysis

Each comparison halves the input, giving the recurrence $T(n) = T(n/2) + O(1)$, so:

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

Heap

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

• Max-heap: every parent $\ge$ its children (root is the maximum).
• Min-heap: every parent $\le$ 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

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

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

Initial array (as complete tree): index 0=4, 1=10, 2=3, 3=5, 4=1.

        4
      /   \
     10    3
    /  \
   5    1

Build heap by heapifying non-leaf nodes from last to first (indices 1 then 0):

• Heapify index 1 (value 10): children 5,1 — 10 is largest, no change.
• Heapify index 0 (value 4): children 10,3 — largest is 10, swap 4↔10 → [10,4,3,5,1]. Now node 4 at index 1 has children 5,1 — largest 5, swap 4↔5 → [10,5,3,4,1].

Resulting max-heap:

        10
      /    \
     5      3
    /  \
   4    1

Array: 10, 5, 3, 4, 1 (root 10 is the maximum).

Graph Representations

Consider an undirected graph with vertices $\{1,2,3,4\}$ and edges: 1-2, 1-3, 2-3, 3-4.

   1 --- 2
   |   /
   | /
   3 --- 4

1. Adjacency Matrix

A $V \times V$ matrix $A$ where $A[i][j] = 1$ if there is an edge between $i$ and $j$, else $0$ (for weighted graphs store the weight).

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

2. Adjacency List

An array of lists; each vertex stores a list of its adjacent vertices.

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

• Space: $O(V + E)$.
• Efficient for sparse graphs; iterating neighbours is fast, but edge lookup is $O(degree)$.

Comparison

Dynamic Programming

Dynamic programming (DP) is an algorithm-design technique that solves problems by breaking them into overlapping sub-problems, solving each sub-problem once, and storing the results (in a table) to avoid recomputation. It applies when a problem has:

1. Optimal substructure — the optimal solution is built from optimal solutions of sub-problems.
2. Overlapping sub-problems — the same sub-problems recur.

It can be implemented top-down (memoization) or bottom-up (tabulation).

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 to maximize total value without exceeding $W$. Each item is taken wholly or not at all (0/1).

DP Recurrence

Let $K[i][w]$ = best value using the first $i$ items with capacity $w$:

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

Example

Items: (w,v) = (1,1),(3,4),(4,5),(5,7), capacity $W=7$. Filling the table, the optimal choice is items (3,4) and (4,5), giving total weight 7 and maximum value 9.

Complexity

Time and space: $O(nW)$ (pseudo-polynomial).

Applications of Stack

A stack (LIFO) is used in many areas:

1. Function/recursion call management — storing activation records.
2. Expression conversion and evaluation — infix↔postfix/prefix, evaluating postfix.
3. Parenthesis / bracket matching — checking balanced symbols.
4. Undo/Redo operations in editors.
5. Backtracking — maze solving, DFS, browser back-button history.
6. Reversing data (e.g., a string or list).
7. Syntax parsing by compilers.

Stack in Function Calls

Programming languages use a call stack to manage function invocations. When a function is called, an activation record (stack frame) is pushed onto the stack containing:

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

Because calls are nested, the most recently called function must finish first — exactly LIFO behaviour. When a function returns, its frame is popped, control returns to the stored return address, and execution continues in the caller. This mechanism naturally supports nested and recursive calls; if calls nest too deeply the stack memory is exhausted, causing a stack overflow.

Heap Sort

Heap sort is a comparison-based, in-place sorting algorithm that uses a binary max-heap. It works in two phases:

1. Build a max-heap from the input array.
2. Repeatedly swap the root (maximum) with the last element, reduce the heap size by one, and heapify the root to restore the heap property.

HeapSort(A, n):
  BuildMaxHeap(A, n)
  for i = n-1 down to 1:
     swap A[0] and A[i]      // move max to its sorted position
     Heapify(A, 0, i)        // restore heap on reduced size i

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

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

Swap 10<->1: [1,5,3,4 | 10]  heapify -> [5,4,3,1 | 10]
Swap 5<->1:  [1,4,3 | 5,10]   heapify -> [4,1,3 | 5,10]
Swap 4<->3:  [3,1 | 4,5,10]   heapify -> [3,1 | 4,5,10]
Swap 3<->1:  [1 | 3,4,5,10]

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

Time Complexity

• BuildMaxHeap: $O(n)$.
• Each of the $n-1$ extractions does a heapify costing $O(\log n)$, so extraction phase is $O(n \log n)$.

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