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

Sorting

Sorting is the process of arranging the elements of a list or array into a logical order — either ascending or descending — according to a comparison key. Sorting makes searching, merging and other operations more efficient.

Quick Sort

Quick Sort is a divide-and-conquer algorithm. It picks an element called the pivot, partitions the array so that all elements smaller than the pivot come before it and all larger ones come after it (the pivot is now in its final position), and then recursively sorts the two sub-arrays.

Algorithm

QUICKSORT(A, low, high)
    if low < high then
        p = PARTITION(A, low, high)
        QUICKSORT(A, low, p-1)
        QUICKSORT(A, p+1, high)

PARTITION(A, low, high)
    pivot = A[high]
    i = low - 1
    for j = low to high-1 do
        if A[j] <= pivot then
            i = i + 1
            swap A[i] and A[j]
    swap A[i+1] and A[high]
    return i+1

Example

Sort A = [5, 3, 8, 4, 2], choosing the last element as pivot.

• Pivot = 2: no smaller elements → 2 goes to front. Array: [2 | 3, 8, 4, 5]
• Sort right part [3, 8, 4, 5], pivot = 5: 3 and 4 are smaller → [3, 4 | 5 | 8]
• Sort [3, 4], pivot = 4: → [3 | 4]

Combining: [2, 3, 4, 5, 8] (sorted).

Time Complexity Analysis

Let the partition step take $O(n)$ time for $n$ elements.

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

• Average case: also $O(n\log n)$.

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

Quick sort needs $O(\log n)$ stack space on average and sorts in place. Worst-case behaviour is avoided in practice by choosing a random or median-of-three pivot.

Binary Search Tree (BST)

A Binary Search Tree is a binary tree in which, for every node, all keys in its left subtree are smaller than the node's key and all keys in its right subtree are larger than the node's key (no duplicates). This ordering allows search, insertion and deletion in $O(h)$ time, where $h$ is the height of the tree.

Insertion Algorithm

INSERT(root, key)
    if root == NULL then
        return new Node(key)
    if key < root.key then
        root.left  = INSERT(root.left, key)
    else if key > root.key then
        root.right = INSERT(root.right, key)
    return root

Trace — insert 50, 30, 70, 20, 40, 60 into an empty BST:

        50
       /  \
     30    70
    /  \   /
   20  40 60

Each key is compared from the root: smaller keys go left, larger go right, until an empty spot is found.

Deletion Algorithm

Three cases must be handled.

DELETE(root, key)
    if root == NULL then return root
    if key < root.key then
        root.left  = DELETE(root.left, key)
    else if key > root.key then
        root.right = DELETE(root.right, key)
    else
        // node found
        if root.left == NULL then return root.right    // 0 or 1 child
        if root.right == NULL then return root.left
        // two children: replace with inorder successor
        succ = MIN(root.right)
        root.key = succ.key
        root.right = DELETE(root.right, succ.key)
    return root

• Case 1 – Leaf node: simply remove it.
• Case 2 – One child: replace the node with its child.
• Case 3 – Two children: replace the node's key with its inorder successor (smallest key in the right subtree), then delete that successor.

Trace — delete 30 (two children) from the tree above:

• Inorder successor of 30 = 40 (min of right subtree).
• Copy 40 into the node, delete the old 40 node.

        50
       /  \
     40    70
    /     /
   20    60

Both operations run in $O(h)$ time — $O(\log n)$ for a balanced tree and $O(n)$ in the worst (skewed) case.

Graph

A graph $G = (V, E)$ is a non-linear data structure consisting of a finite set of vertices $V$ and a set of edges $E$ connecting pairs of vertices. Graphs may be directed/undirected and weighted/unweighted, and are used to model networks, maps, dependencies, etc.

Consider the undirected graph:

      A
     / \
    B   C
    |   |
    D---E

Adjacency: A:{B,C}, B:{A,D}, C:{A,E}, D:{B,E}, E:{C,D}.

Breadth First Search (BFS)

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

BFS(G, s)
    mark all vertices unvisited
    enqueue s; mark s visited
    while queue not empty do
        v = dequeue()
        visit v
        for each unvisited neighbour w of v do
            mark w visited; enqueue w

Trace from A: A → B → C → D → E.

Depth First Search (DFS)

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

DFS(G, v)
    mark v visited; visit v
    for each unvisited neighbour w of v do
        DFS(G, w)

Trace from A: A → B → D → E → C.

Comparison

Applications

• BFS: shortest path in unweighted graphs, peer-to-peer/web crawling, finding connected components, social-network levels.
• DFS: topological sorting, cycle detection, finding strongly connected components, maze/path solving, spanning-tree generation.

Algorithm Complexity

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

Big-O ($O$) — Upper Bound

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

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

$f(n) = \Omega(g(n))$ if $f(n) \ge c\,g(n)$ for all $n \ge n_0$. It gives the best-case lower bound. Example: any comparison sort is $\Omega(n\log n)$.

Theta ($\Theta$) — Tight Bound

$f(n) = \Theta(g(n))$ if $c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$, i.e. it is both $O(g(n))$ and $\Omega(g(n))$. Example: $3n^2 + 2n + 1 = \Theta(n^2)$.

In short, $O$ bounds from above, $\Omega$ from below, and $\Theta$ bounds tightly from both sides.

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, its size is dynamic and insertion/deletion need no shifting.

Singly Linked List (SLL)

Each node has data and a single next pointer to the following node. Traversal is one-directional.

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

Doubly Linked List (DLL)

Each node has data, a next pointer and a prev pointer, allowing two-directional traversal.

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

Differences

Queue

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

Circular Queue

In a simple array queue, once rear reaches the last index the queue appears full even though front cells are free. A circular queue treats the array as a ring: the position after the last index wraps around to index 0 using modulo arithmetic ($\%\ SIZE$), reusing freed space. The queue is full when (rear+1)%SIZE == front and empty when front == -1.

Enqueue

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

Dequeue

DEQUEUE(Q)
    if front == -1 then
        print "Queue Underflow"; return
    x = Q[front]
    if front == rear then              // last element removed
        front = rear = -1
    else
        front = (front + 1) % SIZE
    return x

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

Recursion

Recursion is a programming 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 recursion must have:

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 == 0 then          // base case
        return 1
    else
        return n * FACTORIAL(n - 1)   // recursive case

For FACTORIAL(4): $4\times3\times2\times1\times1 = 24$.

Role of the Stack

Each recursive call creates a new activation record (stack frame) on the call stack, storing the parameters, local variables and the return address. The frames are pushed as the calls go deeper until the base case is reached; then results are computed and the frames are popped in reverse (LIFO) order as the calls return.

push FACT(4) -> FACT(3) -> FACT(2) -> FACT(1) -> FACT(0)=1
pop  : 1 -> 1*1=1 -> 2*1=2 -> 3*2=6 -> 4*6=24

Because of this, deep or infinite recursion (missing base case) causes stack overflow. Space complexity is therefore $O(n)$ due to $n$ stacked frames.

Bubble Sort vs Selection Sort

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.

Selection Sort repeatedly selects the minimum element from the unsorted part and places it at the beginning, performing at most one swap per pass.

Example — sort [5, 1, 4, 2] (ascending)

Bubble Sort (pass 1): (5,1)→swap [1,5,4,2]; (5,4)→swap [1,4,5,2]; (5,2)→swap [1,4,2,5]. Continue passes → [1,2,4,5].

Selection Sort: min of whole list = 1 → already first [1,5,4,2]; min of rest = 2 → swap with 5 [1,2,4,5]; min of rest = 4 → in place. Result [1,2,4,5].

Differences

Both are in-place with $O(1)$ extra space.

Tree Traversal

Traversal means visiting every node of a tree exactly once in a systematic order. For binary trees there are three depth-first traversals, defined by when the root is visited relative to its subtrees:

• Inorder (LNR): Left subtree → Node → Right subtree. For a BST this yields keys in sorted order.
• Preorder (NLR): Node → Left subtree → Right subtree. Useful for copying a tree / prefix expressions.
• Postorder (LRN): Left subtree → Right subtree → Node. Useful for deleting a tree / postfix expressions.

Example

        A
       / \
      B   C
     / \   \
    D   E   F

• Inorder (LNR): D, B, E, A, C, F
• Preorder (NLR): A, B, D, E, C, F
• Postorder (LRN): D, E, B, F, C, A

Each traversal visits all $n$ nodes once, so the time complexity is $O(n)$.

Linear Search vs Binary Search

Binary Search Algorithm

Binary search compares the target with the middle element of a sorted array; if unequal it discards the half in which the target cannot lie and repeats.

BINARY_SEARCH(A, n, key)
    low = 0; high = n - 1
    while low <= high do
        mid = (low + high) / 2
        if A[mid] == key then
            return mid          // found
        else if key < A[mid] then
            high = mid - 1      // search left half
        else
            low = mid + 1       // search right half
    return -1                   // not found

Complexity Analysis

Each comparison halves the remaining elements: $n \to n/2 \to n/4 \to \dots \to 1$. The number of steps $k$ satisfies $n/2^k = 1$, so $k = \log_2 n$. Therefore:

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

Heap

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

• Max-heap: every parent's key $\ge$ its children's keys (largest at root).
• Min-heap: every parent's key $\le$ its children's keys (smallest at 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 (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 larger child if the child is bigger, and continues down recursively. It runs in $O(\log n)$.

MAX_HEAPIFY(A, i, n)
    largest = i
    l = 2i+1; r = 2i+2
    if l < n and A[l] > A[largest] then largest = l
    if r < n and A[r] > A[largest] then largest = r
    if largest != i then
        swap A[i], A[largest]
        MAX_HEAPIFY(A, largest, n)

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

Initial array as a complete tree:

        4(0)
       /    \
    10(1)   3(2)
    /  \
   5(3) 1(4)

Build bottom-up, heapifying from the last internal node $i=\lfloor n/2\rfloor-1 = 1$ down to 0.

• Heapify i=1 (node 10): children 5,1; 10 already largest → no change.
• Heapify i=0 (node 4): children 10,3; largest = 10 → swap(4,10):

        10
       /  \
      4    3
     / \
    5   1

Continue heapify at index 1 (node 4): children 5,1; largest = 5 → swap(4,5):

        10
       /  \
      5    3
     / \
    4   1

Final max-heap array: [10, 5, 3, 4, 1] — the heap property holds at every node.

Graph Representations

Consider the undirected graph with vertices {1, 2, 3, 4} and edges {(1,2), (1,3), (2,4), (3,4)}:

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

1. Adjacency Matrix

A $V \times V$ matrix $A$ where $A[i][j] = 1$ if an edge exists from $i$ to $j$, else $0$ (for weighted graphs, store the weight). For undirected graphs the matrix is symmetric.

• Space: $O(V^2)$ — wasteful for sparse graphs.
• Edge lookup: $O(1)$.

2. Adjacency List

An array (or list) of $V$ entries; entry $i$ holds a linked list of all vertices adjacent to $i$.

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

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

Comparison