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

Sorting

Sorting is the process of arranging the elements of a list/array in a particular order, either ascending or descending, according to some key. Sorting makes searching and other operations more efficient.

Quick Sort

Quick sort is a divide-and-conquer, in-place sorting algorithm. It picks an element as the pivot and partitions the array so that all elements smaller than the pivot lie to its left and all larger lie to its right. The pivot then occupies its final sorted position. The two sub-arrays are sorted recursively.

Algorithm

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

PARTITION(A, low, high)            // last element as pivot
  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 = [7, 2, 1, 6, 8, 5, 3, 4], pivot = last element.

• Pivot = 4. After partition: [2,1,3,4,8,5,7,6], pivot 4 placed at index 3.
• Left [2,1,3] → pivot 3 → [2,1,3], then [2,1] → [1,2].
• Right [8,5,7,6] → pivot 6 → [5,6,8,7], then [8,7] → [7,8].
• Final sorted array: [1, 2, 3, 4, 5, 6, 7, 8].

Time Complexity Analysis

Best case — the pivot splits the array into two nearly equal halves at every level. The recurrence is:

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

Worst case — the pivot is always the smallest or largest element (e.g. an already sorted array with last/first as pivot), giving one empty and one size-$(n-1)$ partition:

Space complexity is $O(\log n)$ on average (recursion stack). Randomised pivot selection avoids the worst case in practice.

Binary Search Tree (BST)

A Binary Search Tree is a binary tree in which, for every node $x$:

• all keys in the left subtree of $x$ are less than $x$'s key, and
• all keys in the right subtree of $x$ are greater than $x$'s key.

This ordering allows search, insertion and deletion in $O(h)$ time, where $h$ is the tree height ($O(\log n)$ if balanced, $O(n)$ in the worst case).

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, 80 into an empty BST:

         50
       /    \
      30     70
     /  \   /  \
    20  40 60   80

Each key is compared from the root and placed as a leaf following the BST property.

Deletion Algorithm

Three cases: leaf, one child, two children.

DELETE(root, key)
  if root == NULL then return NULL
  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 right child
     if root.right == NULL then return root.left    // left child only
     succ = MIN(root.right)              // inorder successor
     root.key = succ.key
     root.right = DELETE(root.right, succ.key)
  return root

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

• Inorder successor of 30 = smallest in its right subtree = 40.
• Copy 40 into the node, then delete the original 40 (a leaf).

         50
       /    \
      40     70
     /      /  \
    20     60   80

Deleting a leaf (e.g. 20) simply removes it; deleting a node with one child links its child to its parent.

Graph

A graph $G = (V, E)$ is a non-linear data structure consisting of a set of vertices $V$ and a set of edges $E$ connecting pairs of vertices. Graphs may be directed/undirected and weighted/unweighted.

Consider the undirected graph:

   A - B
   |   | \
   C - D - E

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

Breadth First Search (BFS)

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

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

Order 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)

Order from A: A, B, D, C, E (depends on neighbour ordering).

Comparison & Applications

Both run in $O(V + E)$ time using adjacency lists.

Applications of BFS: shortest path in unweighted graphs, peer-to-peer networks, web crawlers, finding connected components.

Applications of DFS: cycle detection, topological sorting, finding strongly connected components, solving mazes/puzzles, spanning trees.

Algorithm Complexity

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

Big-O ($O$) — upper bound (worst case). $f(n) = O(g(n))$ if there exist constants $c>0, n_0$ such that $f(n) \le c\,g(n)$ for all $n \ge n_0$. Example: linear search is $O(n)$; inserting in an array is $O(n)$.

Big-Omega ($\Omega$) — lower bound (best case). $f(n) = \Omega(g(n))$ if $f(n) \ge c\,g(n)$ for all $n \ge n_0$. Example: any comparison sort is $\Omega(n \log n)$; linear search best case is $\Omega(1)$.

Big-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. both $O$ and $\Omega$ hold. Example: merge sort is $\Theta(n \log n)$; summing an array is $\Theta(n)$.

For instance, $f(n) = 3n^2 + 2n + 5$ is $O(n^2)$, $\Omega(n^2)$ and therefore $\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 containing data and one or more pointers to other nodes. Unlike arrays, it has dynamic size and allows $O(1)$ insertion/deletion given a node reference.

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).

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

Doubly Linked List (DLL)

Each node has data, a next pointer and a prev pointer, allowing bidirectional traversal.

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

Differences

Queue

A queue is a linear data structure that follows the FIFO (First In, First Out) principle: elements are inserted at the rear and removed from the front.

Circular Queue

In a simple linear array queue, once rear reaches the last index, no new element can be added even if front positions are free (false overflow). A circular queue treats the array as circular: after the last index, the next position wraps to index 0 using modulo arithmetic, reusing freed space efficiently.

For a queue of size $N$: it is full when (rear + 1) % N == front, and empty when front == -1.

Enqueue Algorithm

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

Dequeue Algorithm

DEQUEUE(Q)
  if front == -1 then
     print "Queue Underflow"; return
  x = Q[front]
  if front == rear then           // only one element
     front = rear = -1
  else
     front = (front + 1) % N
  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. A valid recursive function 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

E.g. FACTORIAL(4) = 4*3*2*1*1 = 24.

Role of the Stack

Each recursive call creates a new activation record (stack frame) pushed onto the call stack, storing the parameters, local variables and return address. Frames pile up until the base case is reached:

fact(4) -> fact(3) -> fact(2) -> fact(1) -> fact(0)=1   (pushing)

Then the stack unwinds as each call returns, multiplying results: $1 \to 1 \to 2 \to 6 \to 24$. The maximum stack depth equals the recursion depth ($O(n)$ space); a missing base case causes infinite recursion and stack overflow.

Bubble Sort vs Selection Sort

Bubble Sort repeatedly steps through the list, compares adjacent elements and swaps them if out of order, so the largest unsorted element 'bubbles' to its place 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.

Differences

Both have worst- and average-case time $O(n^2)$ and use $O(1)$ extra space.

Example on [5, 1, 4, 2]

Bubble sort (pass 1): compare/swap adjacent → [1,4,2,5]; pass 2 → [1,2,4,5]; sorted.

Selection sort: min is 1 → [1,5,4,2]; next min 2 → [1,2,4,5]; next min 4 → [1,2,4,5]; sorted.

Tree Traversal

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.

• Inorder (Left, Root, Right): traverse left subtree → visit root → traverse right subtree. For a BST this yields keys in sorted ascending order.
• Preorder (Root, Left, Right): visit root → left subtree → right subtree. Useful to copy a tree or produce prefix expressions.
• Postorder (Left, Right, Root): left subtree → right subtree → visit root. Useful to delete a tree or produce postfix expressions.

Example Binary Tree

        A
       / \
      B   C
     / \   \
    D   E   F

• Inorder: D, B, E, A, C, F
• Preorder: A, B, D, E, C, F
• Postorder: D, E, B, F, C, A

INORDER(node)
  if node != NULL:
     INORDER(node.left); visit(node); INORDER(node.right)

(Preorder and postorder reorder the visit call accordingly.)

Linear Search vs Binary Search

Binary Search Algorithm

Given a sorted array A[0..n-1] and a key:

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

Complexity Analysis

Each iteration halves the search space, so the number of comparisons satisfies:

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

It is usually stored in an array where, for index $i$ (0-based), children are at $2i+1$ and $2i+2$ and the parent at $\lfloor (i-1)/2 \rfloor$. Heaps power the priority queue and heap sort.

Heapify

Heapify (sift-down) restores the heap property at a node assuming its subtrees are already heaps: compare the node with its children, swap with the larger child (for max-heap), and recurse downward until the property holds. It costs $O(\log n)$. Building a heap from $n$ elements by heapifying from the last internal node upward costs $O(n)$.

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

Insert into a complete binary tree (array [4,10,3,5,1]):

        4
       / \
      10   3
     /  \
    5    1

Heapify from the last internal node up (indices 1 then 0):

• Node 10 (index 1): children 5,1 — already largest. No change.
• Node 4 (index 0): children 10 and 3; largest child 10 > 4 → swap.

        10
       /  \
      4    3
     / \
    5   1

• Re-heapify the displaced 4 (now index 1): children 5,1; 5 > 4 → swap.

        10
       /  \
      5    3
     / \
    4   1

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

Graph Representations

A graph $G = (V, E)$ can be stored mainly in two ways. Consider the directed example with vertices $\{1,2,3,4\}$ and edges $1\to2, 1\to3, 2\to4, 3\to4$.

1. Adjacency Matrix

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

      1  2  3  4
   1  0  1  1  0
   2  0  0  0  1
   3  0  0  0  1
   4  0  0  0  0

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

2. Adjacency List

An array/list of $V$ lists, where list $i$ holds all vertices adjacent to $i$.

1 -> 2 -> 3
2 -> 4
3 -> 4
4 -> (empty)

• Space: $O(V + E)$.
• Edge lookup: $O(\deg(v))$.
• Best for sparse graphs; preferred by BFS/DFS.

Comparison