Data Structure and Algorithms

B-tree

A B-tree of order $m$ is a balanced multiway search tree designed for data stored on disks, where each node is read in one block access. Properties:

1. Every node has at most $m$ children and $m-1$ keys.
2. Every non-root internal node has at least $\lceil m/2 \rceil$ children; the root has at least 2 children (unless it is a leaf).
3. A node with $k$ children holds $k-1$ keys, stored in sorted order, and the keys separate the ranges of its subtrees.
4. All leaves are at the same level, so the tree is perfectly balanced.

Operations

• Search: like a BST but with a multiway choice at each node; $O(\log n)$.
• Insertion: insert the key in the proper leaf; if the leaf overflows (more than $m-1$ keys) split it around the median and push the median key up to the parent. Splits may propagate up and the tree grows at the root, so height increases only when the root splits.
• Deletion: remove the key; if a node has too few keys, borrow from a sibling or merge with it.

Because of the large branching factor the height is small, $h = O(\log_{\lceil m/2\rceil} n)$, so very few disk accesses are needed.

Uses: database indexes and file systems. A variant, the B+ tree, keeps all data in the linked leaves.

Divide and conquer is an algorithm design technique that solves a problem by breaking it into smaller subproblems of the same type, solving them (usually recursively), and combining their solutions.

Steps

1. Divide: split the problem into two or more smaller independent subproblems.
2. Conquer: solve each subproblem recursively; if it is small enough, solve it directly (base case).
3. Combine: merge the sub-solutions to get the solution of the original problem.

Example: Merge sort

MergeSort(A, low, high)
  if low < high
      mid = (low + high) / 2
      MergeSort(A, low, mid)
      MergeSort(A, mid+1, high)
      Merge(A, low, mid, high)

Recurrence: $T(n) = 2T(n/2) + O(n)$, which solves to $O(n\log n)$.

Other examples: binary search, quicksort, Strassen's matrix multiplication, Tower of Hanoi.

Advantages: simple, natural recursive solutions, efficient algorithms, suited to parallel execution. Disadvantages: recursion overhead and stack space.

Minimum spanning tree. A minimum spanning tree (MST) of a connected, weighted, undirected graph is a subset of edges that connects all vertices without any cycle and has the minimum possible total weight. For $n$ vertices it has exactly $n-1$ edges.

Kruskal's algorithm. Sort all edges by weight; take edges in increasing order and add an edge if it does not form a cycle with the edges already chosen (checked with union-find), until $n-1$ edges are chosen.

Sorted edges: 0-3 (5), 2-4 (5), 3-5 (6), 0-1 (7), 1-4 (7), 1-2 (8), 4-5 (8), 1-3 (9), 4-6 (9), 5-6 (11), 3-4 (15).

Six edges have been chosen for 7 vertices, so we stop.

MST edges: 0-3, 2-4, 3-5, 0-1, 1-4, 4-6.

Total weight = $5 + 5 + 6 + 7 + 7 + 9 = 39$.

Complexity: $O(E\log E)$, dominated by sorting the edges.

Rules used

Operands go straight to the output. Operator precedence: ^ (highest, right-associative), then $*$, then $+,-$. Before pushing an operator, pop from the stack every operator of higher precedence (or equal precedence for left-associative ones). ( is pushed; on ) pop until (.

Expression: $A + B * (C ^ D - E) ^ (F + G * H) - I$

Postfix expression:

$A\,B\,C\,D\,\wedge\,E\,-\,F\,G\,H\,*\,+\,\wedge\,*\,+\,I\,-$

that is ABCD^E-FGH*+^*+I-.

Time complexity is the amount of time an algorithm takes to run, expressed as a function of the input size $n$ (in practice, the number of basic operations). Space complexity is the amount of memory the algorithm needs as a function of $n$, including the input, auxiliary variables and the recursion stack. For example, a single loop summing $n$ numbers has time $O(n)$ and space $O(1)$.

Asymptotic notations describe the growth of a running time $f(n)$ for large $n$.

1. Big-O (upper bound). $f(n) = O(g(n))$ if there are constants $c > 0$, $n_0$ such that $f(n) \le c\,g(n)$ for all $n \ge n_0$. It is used for the worst case.

 cost
  |        c*g(n)
  |      /  .
  |    /  .  f(n)
  |  /  .
  | / .
  |/.______________ n
       n0
  (f(n) stays below c*g(n) after n0)

2. Big-Omega (lower bound). $f(n) = \Omega(g(n))$ if $f(n) \ge c\,g(n)$ for all $n \ge n_0$. It is used for the best case.

 cost
  |  f(n)
  |   .   .
  |  .  .
  | . c*g(n)
  |.______________ n
       n0
  (f(n) stays above c*g(n) after n0)

3. Big-Theta (tight bound). $f(n) = \Theta(g(n))$ if there are constants $c_1, c_2 > 0$ and $n_0$ such that $c_1 g(n) \le f(n) \le c_2 g(n)$ for all $n \ge n_0$. It means $f$ is both $O(g)$ and $\Omega(g)$.

 cost
  |      c2*g(n)
  |    /  
  |   /  f(n)  (between the two curves)
  |  /
  | /   c1*g(n)
  |/______________ n
       n0

4. Little-o and little-omega are strict bounds: $f(n)=o(g(n))$ means $f$ grows strictly slower than $g$, and $f(n)=\omega(g(n))$ means strictly faster.

Example: $f(n) = 3n + 2$. Then $3n + 2 \le 4n$ for $n \ge 2$, so $f = O(n)$; $3n + 2 \ge 3n$, so $f = \Omega(n)$; hence $f = \Theta(n)$.

Time complexity of an algorithm is the amount of time it takes as a function of the input size $n$ (the number of basic operations executed). Space complexity is the total memory it needs as a function of $n$: the space for the input plus auxiliary space (variables, recursion stack, temporary arrays). For example, linear search has time $O(n)$ and space $O(1)$; merge sort has time $O(n\log n)$ and space $O(n)$.

Asymptotic notations describe the growth rate of a function $f(n)$ for large $n$, ignoring constants and lower-order terms.

1. Big-O, $O(g(n))$ (upper bound, worst case). $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$. Example: $f(n) = 3n+2$. Since $3n+2 \le 4n$ for $n \ge 2$, $f(n) = O(n)$.

2. Big-Omega, $\Omega(g(n))$ (lower bound, best case). $f(n) = \Omega(g(n))$ if $f(n) \ge c\,g(n)$ for all $n \ge n_0$. Example: $3n+2 \ge 3n$ for all $n \ge 1$, so $3n+2 = \Omega(n)$.

3. Big-Theta, $\Theta(g(n))$ (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(g)$ and $\Omega(g)$. Example: $3n \le 3n+2 \le 4n$ for $n \ge 2$, so $3n+2 = \Theta(n)$.

4. Little-o, $o(g(n))$ (strict upper bound): $f(n) < c\,g(n)$ for every $c>0$. Example: $n = o(n^2)$.

5. Little-omega, $\omega(g(n))$ (strict lower bound). Example: $n^2 = \omega(n)$.

Common order of growth: $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n)$.

Stack. A stack is a linear data structure in which insertion and deletion take place only at one end, the top, following the LIFO (Last In, First Out) rule.

Basic operations

• push(x): add element $x$ on the top; if the stack is full, overflow occurs.
• pop(): remove and return the top element; if the stack is empty, underflow occurs.
• peek() (top): read the top element without removing it.
• isEmpty(): true if the stack has no element.
• isFull(): true if no more elements can be pushed (array implementation).

All of them take $O(1)$ time.

Infix to postfix: $(a + b) * (c - d) / (e + f)$

Scan left to right: operands go to the output; operators go on the stack after popping operators of higher or equal precedence (* and / have higher precedence than + and -, and are left associative); ( is pushed and ) pops until (.

Postfix expression: $ab+cd-*ef+/$

Why study Data Structures and Algorithms

• Every program stores data and processes it. The way data is organised decides how fast and how economically operations (search, insert, delete, sort) can be done.
• A good choice of data structure and algorithm reduces running time and memory; for large inputs the difference between $O(n^2)$ and $O(n\log n)$ is the difference between a program that finishes and one that does not.
• It gives reusable building blocks (stack, queue, list, tree, graph, hash table) used in compilers, operating systems, databases, networks and AI.
• It develops problem-solving and analytical skills, and lets us compare solutions by measurable cost instead of guesswork.
• It is the foundation of later subjects and of technical interviews.

Algorithm

An algorithm is a finite, well-defined sequence of unambiguous steps that takes zero or more inputs and produces at least one output to solve a problem.

Key characteristics:

1. Input: zero or more well-defined inputs.
2. Output: at least one result.
3. Definiteness: each step is clear and unambiguous.
4. Finiteness: it terminates after a finite number of steps.
5. Effectiveness: each step is basic enough to be carried out exactly in finite time.
6. Correctness / generality: it gives the right result for every valid input.

Time complexity of the code

The outer loop runs for $i = 0, 1, \dots, N-1$. For a given $i$ the inner loop runs for $j = N, N-1, \dots, i+1$, which is $N - i$ times. Total executions of the statement:

$\sum_{i=0}^{N-1}(N-i) = N + (N-1) + \dots + 1 = \frac{N(N+1)}{2}$

$T(N) = \frac{N^2}{2} + \frac{N}{2} = O(N^2)$

The count does not depend on data values, so the worst case time complexity is $O(N^2)$ (quadratic).

Divide and Conquer

A problem is solved in three steps:

1. Divide the problem into smaller sub-problems of the same type.
2. Conquer each sub-problem recursively (solve directly when small enough).
3. Combine the sub-solutions into the solution of the original problem.

The sub-problems are independent (they do not overlap). Its running time is usually described by a recurrence $T(n) = aT(n/b) + f(n)$.

Example: Merge sort

MergeSort(A, low, high)
  if low < high
      mid = (low + high) / 2
      MergeSort(A, low, mid)          // conquer left
      MergeSort(A, mid + 1, high)     // conquer right
      Merge(A, low, mid, high)        // combine in O(n)

$T(n) = 2T(n/2) + cn$, so $T(n) = O(n\log n)$. Other examples: quick sort, binary search ($T(n)=T(n/2)+1 = O(\log n)$).

Dynamic Programming

Dynamic programming solves problems whose sub-problems overlap and which have optimal substructure (an optimal solution contains optimal solutions of its sub-problems). Each sub-problem is solved only once and its result is stored in a table (memoization, top-down, or tabulation, bottom-up) and reused.

Example: Fibonacci numbers

Plain recursion fib(n) = fib(n-1) + fib(n-2) recomputes the same values and takes $O(2^n)$. With a table:

Fib(n)
  F[0] = 0; F[1] = 1
  for i = 2 to n
      F[i] = F[i-1] + F[i-2]
  return F[n]

Time $O(n)$, space $O(n)$. Other examples: 0/1 knapsack, longest common subsequence, matrix-chain multiplication, Floyd-Warshall.

Comparison

Tower of Hanoi

There are $n$ disks of different sizes on peg A (source). Move all to peg C (destination) using peg B (auxiliary), moving one disk at a time and never placing a larger disk on a smaller one.

Recursive algorithm

Hanoi(n, source, aux, dest)
  if n == 1
      print "Move disk 1 from source to dest"
      return
  Hanoi(n-1, source, dest, aux)          // move n-1 disks out of the way
  print "Move disk n from source to dest"
  Hanoi(n-1, aux, source, dest)          // bring them onto disk n

C version:

#include <stdio.h>
void hanoi(int n, char s, char a, char d) {
    if (n == 1) { printf("Move disk 1 from %c to %c\n", s, d); return; }
    hanoi(n - 1, s, d, a);
    printf("Move disk %d from %c to %c\n", n, s, d);
    hanoi(n - 1, a, s, d);
}
int main() { hanoi(3, 'A', 'B', 'C'); return 0; }

For $n = 3$ the moves are: A to C, A to B, C to B, A to C, B to A, B to C, A to C. The number of moves satisfies $T(n) = 2T(n-1) + 1$, so

$T(n) = 2^n - 1.$

Recursion and stack

Each recursive call pushes an activation record (stack frame) onto the system call stack holding the parameters $(n, s, a, d)$, local variables and the return address. When a call finishes, its frame is popped and execution resumes in the caller, at the instruction after the call. Calls are therefore completed in last-in first-out order.

In Hanoi, Hanoi(3,A,B,C) pushes a frame, which calls Hanoi(2,A,C,B), which calls Hanoi(1,A,B,C); the deepest call returns first and its frame is popped, then the print of the caller executes, then the second recursive call is pushed. The maximum stack depth is $n$, so the space used is $O(n)$. Recursion is thus a hidden use of the stack; the same algorithm can be written without recursion by managing an explicit stack.

Circular queue

A circular queue is a queue in which the last position of the array is logically connected to the first position, so the array is treated as a ring. In a linear array queue, after rear reaches the last index no insertion is possible even if cells at the front were freed by deletions. In a circular queue the freed cells are reused, so memory is used efficiently.

Indices move with modulo arithmetic: $\text{next} = (\text{index} + 1) \bmod N$, where $N$ is the array size.

Initially front = rear = -1.

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

Insertion (enqueue)

Enqueue(Q, N, x)
  if (rear + 1) % N == front
      print "Queue overflow"; return
  if front == -1
      front = 0; rear = 0
  else
      rear = (rear + 1) % N
  Q[rear] = x

Deletion (dequeue)

Dequeue(Q, N)
  if front == -1
      print "Queue underflow"; return
  x = Q[front]
  if front == rear            // only one element
      front = -1; rear = -1
  else
      front = (front + 1) % N
  return x

Example with $N = 5$: insert 10, 20, 30, 40, 50 gives front = 0, rear = 4, the queue is full. Delete twice (10, 20 removed): front = 2. Insert 60: rear = $(4+1) \bmod 5 = 0$, so 60 is stored at index 0 and the queue holds 30, 40, 50, 60.

Both operations take $O(1)$ time.

Difference between stack and queue

Stack using a linked list

Each node holds data and a next pointer. top points to the first node; push and pop both act on the head, so each takes $O(1)$ time.

struct Node { int data; struct Node *next; };
Node *top = NULL;

Push(x)
  new = allocate Node
  if new == NULL: print "Overflow"; return
  new->data = x
  new->next = top
  top = new

Pop()
  if top == NULL: print "Underflow"; return
  temp = top
  x = temp->data
  top = top->next
  free(temp)
  return x

C implementation of the two operations:

void push(int x) {
    struct Node *n = (struct Node *)malloc(sizeof(struct Node));
    if (n == NULL) { printf("Overflow\n"); return; }
    n->data = x; n->next = top; top = n;
}
int pop() {
    if (top == NULL) { printf("Underflow\n"); return -1; }
    struct Node *t = top; int x = t->data;
    top = top->next; free(t);
    return x;
}

Singly linked list

A singly linked list is a linear collection of nodes where each node contains a data field and a pointer to the next node; the last node's pointer is NULL. A pointer head holds the address of the first node. Nodes are allocated dynamically, so the list grows and shrinks at run time, and insertion/deletion needs no shifting of elements.

struct Node { int data; struct Node *next; };

Delete at the beginning

struct Node* deleteBegin(struct Node *head) {
    if (head == NULL) {                 // empty list
        printf("List is empty\n");
        return NULL;
    }
    struct Node *temp = head;
    head = head->next;                  // second node becomes first
    free(temp);
    return head;
}

Time: $O(1)$.

Delete at the end

struct Node* deleteEnd(struct Node *head) {
    if (head == NULL) {
        printf("List is empty\n");
        return NULL;
    }
    if (head->next == NULL) {           // only one node
        free(head);
        return NULL;
    }
    struct Node *prev = head, *cur = head->next;
    while (cur->next != NULL) {         // go to the last node
        prev = cur;
        cur = cur->next;
    }
    prev->next = NULL;                  // second last becomes last
    free(cur);
    return head;
}

Time: $O(n)$, because the list must be traversed to reach the second last node.

The tree: root P; P has children Q (left) and R (right); Q has children S (left) and T (right); T has a right child V; R has a right child U.

Inorder traversal (Left, Root, Right)

• Left subtree of P (rooted at Q): inorder(S) = S, then Q, then inorder(T) = T, V (T has no left child), giving S Q T V.
• Root: P.
• Right subtree of P (rooted at R): R has no left child, so R, then U, giving R U.

$\text{Inorder: } S\ Q\ T\ V\ P\ R\ U$

Postorder traversal (Left, Right, Root)

• Left subtree (rooted at Q): S, then postorder(T) = V, T, then Q, giving S V T Q.
• Right subtree (rooted at R): U, then R, giving U R.
• Root: P.

$\text{Postorder: } S\ V\ T\ Q\ U\ R\ P$

Height and depth

• Depth of a node is the number of edges on the path from the root to that node. The root has depth 0.
• Height of a node is the number of edges on the longest path from that node down to a leaf. A leaf has height 0. The height of a tree is the height of its root.

AVL tree

An AVL tree is a binary search tree in which, for every node, the heights of the left and right subtrees differ by at most 1 (balance factor $\in \{-1,0,1\}$). Imbalance is repaired by rotations (LL, RR, LR, RL).

Construction for 35, 33, 42, 10, 14, 19, 27, 44, 26

1. Insert 35, 33, 42: 35 is root with children 33 and 42. Balanced.
2. Insert 10: left child of 33. Balanced.
3. Insert 14: right child of 10. Node 33 has balance factor 2 and the new node is in the right subtree of its left child (LR case). Rotate left at 10, then right at 33. Subtree becomes 14 with children 10 and 33. Tree: 35 (14 (10, 33), 42).
4. Insert 19: path 35, 14, 33, left of 33. Node 35 is unbalanced (left height 3, right height 1) with the insertion in the right subtree of its left child (LR). Rotate left at 14, then right at 35. Tree: 33 (14 (10, 19), 35 (-, 42)).
5. Insert 27: path 33, 14, 19, right of 19. All balance factors are within $\pm1$. Tree: 33 (14 (10, 19 (-, 27)), 35 (-, 42)).
6. Insert 44: right child of 42. Node 35 has balance factor $-2$ (RR case). Rotate left at 35. Subtree becomes 42 with children 35 and 44.
7. Insert 26: path 33, 14, 19, 27, left of 27. Node 19 is unbalanced (right height 2, left 0), and the insertion is in the left subtree of its right child (RL). Rotate right at 27, then left at 19. Subtree becomes 26 with children 19 and 27.

Final AVL tree

              33
            /    \
          14      42
         /  \    /  \
       10   26  35  44
           /  \
         19    27

Check: inorder is 10, 14, 19, 26, 27, 33, 35, 42, 44 (sorted), and every node's balance factor is $-1$, 0 or 1. Height of the tree is 3.

Frequencies of the message B C A A D D D C C A C A C A C (15 characters):

Building the Huffman tree (repeatedly merge the two smallest weights)

1. Smallest are B(1) and D(3): merge into node N1 = 4.
2. Remaining weights: N1(4), A(5), C(6). Merge N1(4) and A(5) into N2 = 9.
3. Remaining: C(6), N2(9). Merge into root = 15.

            (15)
           0/   \1
          C(6)   (9)
                0/  \1
              (4)    A(5)
             0/ \1
           B(1) D(3)

Labelling left edges 0 and right edges 1 (smaller weight on the left):

Total bits

$6\times1 + 5\times2 + 1\times3 + 3\times3 = 6 + 10 + 3 + 9 = 28 \text{ bits}$

Encoded message: C=0, A=11, B=100, D=101 gives the 28-bit string for B C A A D D D C C A C A C A C. A fixed-length code would need $15 \times 2 = 30$ bits, so Huffman coding saves 2 bits here.

Method: choose the first element as pivot. Move i right to the first element greater than the pivot and j left to the first element less than or equal to the pivot; swap them if $i < j$. When the pointers cross, swap the pivot with the element at j. Then sort the left and right parts recursively.

Array: 68, 34, 21, 43, 7, 18, 8, 56, 28, 17

Pass 1 (pivot 68): no element is greater than 68, and j stops at once at 17. Swap pivot with 17:

17, 34, 21, 43, 7, 18, 8, 56, 28 | 68

Pass 2 on [17, 34, 21, 43, 7, 18, 8, 56, 28] (pivot 17): i stops at 34, j stops at 8; swap: 17, 8, 21, 43, 7, 18, 34, 56, 28. i stops at 21, j stops at 7; swap: 17, 8, 7, 43, 21, 18, 34, 56, 28. i stops at 43, j stops at 7 (index before i), so they have crossed. Swap pivot with 7:

[7, 8] | 17 | [43, 21, 18, 34, 56, 28]

Pass 3 on [7, 8]: pivot 7, nothing smaller on the right, so 7 stays and [8] is single. Sorted: 7, 8.

Pass 4 on [43, 21, 18, 34, 56, 28] (pivot 43): i stops at 56, j stops at 28; swap: 43, 21, 18, 34, 28, 56. Pointers cross; swap pivot with 28:

[28, 21, 18, 34] | 43 | [56]

Pass 5 on [28, 21, 18, 34] (pivot 28): i stops at 34, j stops at 18, crossed. Swap pivot with 18:

[18, 21] | 28 | [34]

Pass 6 on [18, 21]: pivot 18 is already in place; [21] is single.

Sorted array:

$7,\ 8,\ 17,\ 18,\ 21,\ 28,\ 34,\ 43,\ 56,\ 68$

Average time $O(n\log n)$, worst case $O(n^2)$.

Insertion sort

The array is divided into a sorted part (initially the first element) and an unsorted part. Each element (the key) of the unsorted part is taken in turn and inserted into its correct position in the sorted part by shifting larger elements one place right.

Algorithm

InsertionSort(A, n)
  for i = 1 to n-1
      key = A[i]
      j = i - 1
      while j >= 0 and A[j] > key
          A[j+1] = A[j]
          j = j - 1
      A[j+1] = key

Program in C

#include <stdio.h>
void insertionSort(int a[], int n) {
    for (int i = 1; i < n; i++) {
        int key = a[i], j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}
int main() {
    int a[] = {5, 2, 4, 6, 1, 3}, n = 6;
    insertionSort(a, n);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

Example: 5, 2, 4, 6, 1, 3

Time complexity

• Best case (already sorted): one comparison per element, $O(n)$.
• Worst case (reverse sorted): the key is compared with and shifted past all earlier elements, $1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2}$, so $O(n^2)$.
• Average case: about half of the worst case, $O(n^2)$.
• Space: $O(1)$ extra (in place). The sort is stable.

Hashing

Hashing stores a record with key $k$ at index $h(k)$ of a table, e.g. $h(k) = k \bmod m$, giving average $O(1)$ search. When two keys map to the same index a collision occurs and must be resolved.

Perfect hashing

A perfect hash function maps a given static set of keys to distinct slots with no collisions, so a search takes worst case $O(1)$. If the table has exactly as many slots as keys it is a minimal perfect hash function. A common construction (FKS, two-level hashing) hashes keys into $n$ buckets with a first hash function; each bucket with $b_i$ keys gets its own secondary table of size $b_i^2$ and a secondary hash function chosen so that it has no collisions. Total space is $O(n)$. It suits fixed key sets such as reserved words of a compiler.

Linear probing (open addressing)

On collision, probe the next slots one by one: $h_i(k) = (h(k) + i) \bmod m$, $i = 0,1,2,\dots$ until an empty slot is found.

Example: $m = 10$, $h(k) = k \bmod 10$, keys 23, 43, 13, 27, 33.

• 23 goes to slot 3.
• 43: slot 3 full, slot 4 is free, so 43 goes to 4.
• 13: slots 3, 4 full, so 13 goes to 5.
• 27 goes to 7.
• 33: slots 3, 4, 5 full, so 33 goes to 6.

Drawback: primary clustering (long runs of filled slots lengthen searches).

Separate chaining

Each slot holds a linked list of all keys hashing to it. A colliding key is simply added to the list; the table never overflows.

Same keys, $m = 10$:

• Slot 3: 23 -> 43 -> 13 -> 33
• Slot 7: 27

Search cost is $O(1 + \alpha)$ where $\alpha = n/m$ is the load factor. It needs extra memory for pointers, but deletion is easy and performance degrades gracefully.

Shortest path

The shortest path between two vertices of a weighted graph is the path whose total edge weight is minimum among all paths joining them.

Dijkstra's algorithm (single source, non-negative weights)

Dijkstra(G, s)
  for each vertex v: dist[v] = infinity; parent[v] = none; visited[v] = false
  dist[s] = 0
  repeat n times
      u = unvisited vertex with smallest dist[u]
      visited[u] = true
      for each neighbour v of u
          if dist[u] + w(u,v) < dist[v]
              dist[v] = dist[u] + w(u,v)
              parent[v] = u

Worked example

Take the graph with edges A-B = 4, A-C = 2, B-C = 1, B-D = 5, C-D = 8, C-E = 10, D-E = 2, D-F = 6, E-F = 3. Source A, destination F.

Details: in step 2, B becomes $2+1 = 3 < 4$, D becomes $2+8 = 10$, E becomes $2+10 = 12$. In step 3, D becomes $3+5 = 8 < 10$. In step 4, E becomes $8+2 = 10 < 12$ and F becomes $8+6 = 14$. In step 5, F becomes $10+3 = 13 < 14$.

Following parents back from F: F <- E <- D <- B <- C <- A.

Shortest path: A -> C -> B -> D -> E -> F with total cost $2+1+5+2+3 = 13$.

Time complexity $O(V^2)$ with an array, $O((V+E)\log V)$ with a binary heap.

Priority queue

A priority queue is an abstract data type in which every element has a priority, and the element with the highest priority (or lowest, in a min-priority queue) is removed first, regardless of the order of arrival. Elements of equal priority are served in FIFO order.

Operations

• insert(x, p): add element $x$ with priority $p$.
• deleteMax() / deleteMin(): remove and return the highest (lowest) priority element.
• peek(): look at the top element without removing it.

Implementations

The heap is the usual efficient implementation.

Types: ascending priority queue (smallest first) and descending priority queue (largest first).

Applications: CPU and job scheduling, Dijkstra's and Prim's algorithms, Huffman coding, event simulation, interrupt handling.

Abstract Data Type (ADT)

An abstract data type is a mathematical model of a data structure that specifies the data it stores and the operations on that data, together with their behaviour, but hides how they are implemented. The user sees only the interface; the representation and algorithms are hidden (information hiding and encapsulation).

Example: Stack ADT

• Data: an ordered collection of elements accessed at one end (top).
• Operations: push(x), pop(), peek(), isEmpty(), isFull().
• Behaviour: last in, first out.

The same stack ADT may be implemented with an array or a linked list; programs using it need not change.

Advantages

• Separates specification from implementation, so the implementation can change without affecting users.
• Improves modularity, reusability and maintainability.
• Reduces complexity by letting programmers think at the level of operations.

Other common ADTs: queue, list, priority queue, dictionary (map), set, tree and graph.

Data structure

A data structure is a particular way of organising, storing and managing data in a computer so that it can be accessed and modified efficiently. Examples are arrays, stacks, queues, linked lists, trees and graphs.

Types of data structure

1. Primitive data structures: basic types supported directly by the machine/language, such as int, float, char, boolean, pointers.

2. Non-primitive data structures: built from primitive types. They are divided into:

(a) Linear data structures: elements are arranged sequentially, each element has a unique predecessor and successor (except the ends).

• Array: fixed-size collection of same-type elements in contiguous memory, accessed by index. Example: int a[5].
• Linked list: nodes connected by pointers; singly, doubly or circular. Example: a playlist.
• Stack: LIFO. Example: undo operation, function calls.
• Queue: FIFO. Example: print queue, ticket counter.

(b) Non-linear data structures: elements are not in a sequence; one element can be linked to many.

• Tree: hierarchical, with a root and subtrees. Example: file system, binary search tree.
• Graph: set of vertices connected by edges. Example: road map, social network.

Other classification

• Static (fixed size, e.g. array) versus dynamic (size changes at run time, e.g. linked list).
• Homogeneous (same type, e.g. array) versus heterogeneous (different types, e.g. structure/record).

Algorithm analysis

Algorithm analysis is the process of determining the resources an algorithm needs, mainly running time (time complexity) and memory (space complexity), as a function of the input size $n$. It lets us compare algorithms independently of hardware and programming language, and choose the most efficient one.

Computing $T(n)$

• Outer loop for i = 1 to n: the loop test is executed $n+1$ times, cost $C_1(n+1)$.
• Inner loop for j = 1 to n-1: for each of the $n$ values of $i$, the test is executed $n$ times, total $C_2 \cdot n \cdot n = C_2 n^2$.
• printf: executed $n-1$ times for each $i$, total $C_3\, n(n-1)$.

$T(n) = C_1(n+1) + C_2 n^2 + C_3 n(n-1) = (C_2 + C_3)n^2 + (C_1 - C_3)n + C_1$

Worst case and average case

The number of operations depends only on $n$ and not on the values of the input, so the best, average and worst cases are identical:

$T_{worst}(n) = T_{avg}(n) = (C_2 + C_3)n^2 + (C_1 - C_3)n + C_1 = \Theta(n^2)$

Complexity of algorithms

Complexity measures the resources an algorithm uses as a function of input size $n$.

• Time complexity: the number of basic operations (steps) executed.
• Space complexity: the amount of memory needed (input plus auxiliary space).

It is studied for the best, average and worst cases; the worst case is most often quoted because it guarantees an upper limit.

Need for asymptotic notation

• Exact running time depends on the machine, compiler and language, so it is not a fair basis for comparison.
• Exact step counts are messy; for large $n$ only the fastest-growing term matters (for $3n^2 + 5n + 2$ the $n^2$ term dominates).
• Asymptotic notations ($O$, $\Omega$, $\Theta$) describe the growth rate of the running time for large $n$, ignoring constants and lower-order terms, giving a simple machine-independent way to compare algorithms.

Big-Oh notation

$f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that

$f(n) \le c\, g(n) \quad \text{for all } n \ge n_0 .$

It gives an asymptotic upper bound on growth (worst-case bound).

Example: show $f(n) = 3n + 2 = O(n)$.

For $n \ge 2$: $3n + 2 \le 3n + n = 4n$. So with $c = 4$ and $n_0 = 2$, $f(n) \le 4n$, hence $3n+2 = O(n)$.

Similarly $5n^2 + 3n + 1 \le 9n^2$ for $n \ge 1$, so it is $O(n^2)$. Common orders: $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(2^n)$.

Stack

A stack is a linear data structure in which insertion (push) and deletion (pop) take place only at one end, called the top. It follows the Last In First Out (LIFO) rule. Other operations are peek, isEmpty and isFull.

Use of stack in recursion

When a function calls itself, the system keeps a call stack. Each call pushes an activation record (stack frame) containing the parameters, local variables and return address. When a call finishes, its frame is popped and control returns to the caller, which continues with the value returned. Calls are therefore completed in reverse order of their start, which is exactly LIFO.

Factorial example

$n! = \begin{cases} 1 & n = 0 \\ n \times (n-1)! & n > 0 \end{cases}$

int fact(int n) {
    if (n == 0) return 1;          // base case
    return n * fact(n - 1);        // recursive case
}

Trace of fact(4):

Winding (calls pushed): fact(4) -> fact(3) -> fact(2) -> fact(1) -> fact(0). The stack holds five frames, with fact(0) on top.

Unwinding (frames popped):

• fact(0) returns 1
• fact(1) returns $1 \times 1 = 1$
• fact(2) returns $2 \times 1 = 2$
• fact(3) returns $3 \times 2 = 6$
• fact(4) returns $4 \times 6 = 24$

So $4! = 24$. The stack depth is $n+1$, so the space is $O(n)$ and the time is $O(n)$. Without the base case the stack would grow without limit and cause stack overflow.

Priority queue

A priority queue is a queue in which each element has a priority and the element with the highest priority is served (removed) first, irrespective of arrival order; elements with equal priority are served in the order of arrival. It is commonly implemented with a heap, giving $O(\log n)$ insertion and deletion. It is used in CPU scheduling, Dijkstra's algorithm and Huffman coding.

Circular queue

A circular queue treats the array of size $N$ as a ring: after the last index the next position is index 0. This reuses the space freed by deletions, which a simple linear queue cannot. Indices advance as $(\text{index}+1) \bmod N$. Initially front = rear = -1; the queue is empty when front == -1 and full when (rear+1) % N == front.

Implementation

#define N 5
int q[N], front = -1, rear = -1;

void enqueue(int x) {
    if ((rear + 1) % N == front) { printf("Overflow\n"); return; }
    if (front == -1) front = rear = 0;
    else rear = (rear + 1) % N;
    q[rear] = x;
}
int dequeue() {
    if (front == -1) { printf("Underflow\n"); return -1; }
    int x = q[front];
    if (front == rear) front = rear = -1;
    else front = (front + 1) % N;
    return x;
}

Example ($N = 5$)

1. Enqueue 10, 20, 30, 40, 50: front = 0, rear = 4, queue full.
2. Dequeue twice (10 and 20 leave): front = 2.
3. Enqueue 60: rear = $(4+1) \bmod 5 = 0$, so 60 is placed at index 0.
4. Contents from front to rear: 30, 40, 50, 60.

Both operations take $O(1)$ time.

Doubly linked list

A doubly linked list is a linked list in which each node has three fields: a pointer to the previous node (prev), the data, and a pointer to the next node (next). The prev of the first node and the next of the last node are NULL. It can be traversed in both directions and a node can be deleted given only its own address, at the cost of an extra pointer per node.

struct Node {
    int data;
    struct Node *prev, *next;
};

Insert a node at the beginning

struct Node* insertBegin(struct Node *head, int x) {
    struct Node *n = (struct Node *)malloc(sizeof(struct Node));
    if (n == NULL) { printf("Memory not available\n"); return head; }
    n->data = x;
    n->prev = NULL;
    n->next = head;
    if (head != NULL)
        head->prev = n;        // old first node points back to the new node
    head = n;                  // new node becomes the first node
    return head;
}

Time complexity $O(1)$.

For a singly linked list (nodes with only data and next), insertion at the beginning is:

struct SNode* insertBeginS(struct SNode *head, int x) {
    struct SNode *n = (struct SNode *)malloc(sizeof(struct SNode));
    n->data = x;
    n->next = head;
    return n;                  // new node is the new head
}

Advantages of a linked stack

• Dynamic size: it grows and shrinks at run time; no maximum size has to be fixed, so there is no stack overflow until memory itself is exhausted.
• Efficient memory use: memory is allocated only for elements actually stored, with no wasted unused array cells.
• Constant time operations: push and pop work at the head, $O(1)$, and no shifting is needed.
• No costly resizing/copying as with a full array.

The cost is an extra pointer per node and slower allocation.

Algorithm: stack using a linked list

Each node has data and next. top points to the first node and is NULL when the stack is empty.

Push(x)
  new = allocate Node
  if new == NULL: print "Overflow"; return
  new->data = x
  new->next = top
  top = new

Pop()
  if top == NULL: print "Underflow"; return
  temp = top
  x = temp->data
  top = top->next
  free(temp)
  return x

Peek()
  if top == NULL: print "Stack empty"
  else return top->data

C code:

struct Node { int data; struct Node *next; } *top = NULL;

void push(int x) {
    struct Node *n = (struct Node *)malloc(sizeof(struct Node));
    if (n == NULL) { printf("Overflow\n"); return; }
    n->data = x; n->next = top; top = n;
}
int pop() {
    if (top == NULL) { printf("Underflow\n"); return -1; }
    struct Node *t = top; int x = t->data;
    top = top->next; free(t);
    return x;
}

Binary search tree (BST)

A BST is a binary tree in which, for every node, all keys in the left subtree are smaller than the node's key and all keys in the right subtree are larger. An inorder traversal gives the keys in sorted order.

struct Node { int key; struct Node *left, *right; };

struct Node* newNode(int k) {
    struct Node *n = (struct Node *)malloc(sizeof(struct Node));
    n->key = k; n->left = n->right = NULL;
    return n;
}

Insertion

struct Node* insert(struct Node *root, int k) {
    if (root == NULL) return newNode(k);
    if (k < root->key)       root->left  = insert(root->left, k);
    else if (k > root->key)  root->right = insert(root->right, k);
    return root;                       // duplicates ignored
}

Search

struct Node* search(struct Node *root, int k) {
    if (root == NULL || root->key == k) return root;
    if (k < root->key) return search(root->left, k);
    return search(root->right, k);
}

Inorder traversal

void inorder(struct Node *r) {
    if (r != NULL) { inorder(r->left); printf("%d ", r->key); inorder(r->right); }
}

Algorithm for search

1. Start at the root.
2. If the tree is empty, the key is not found.
3. If key equals the node's key, return the node.
4. If key is smaller, continue in the left subtree; otherwise in the right subtree.

Time complexity of search

Each comparison moves down one level, so the time is $O(h)$ where $h$ is the height of the tree.

• Best/average case (balanced tree, $h \approx \log_2 n$): $O(\log n)$.
• Worst case (skewed tree, e.g. keys inserted in sorted order, $h = n$): $O(n)$.

Self-balancing trees such as AVL trees guarantee $O(\log n)$.

Huffman tree

Huffman coding is a lossless compression method that gives shorter binary codes to more frequent characters and longer codes to rarer ones, producing a prefix code (no code is a prefix of another). The code is derived from a Huffman tree.

Construction steps

1. Count the frequency of each character and create a leaf node for each.
2. Put all nodes in a priority queue (min-heap) ordered by frequency.
3. Remove the two nodes with the smallest frequencies and create a new internal node whose frequency is their sum, with these two as children.
4. Insert the new node back into the queue.
5. Repeat steps 3 and 4 until one node (the root) remains.
6. Label left edges 0 and right edges 1; the path from the root to a leaf gives the code of that character.

Example: A = 5, B = 9, C = 12, D = 13, E = 16, F = 45 (total 100).

1. Merge A(5) + B(9) = 14.
2. Merge C(12) + D(13) = 25.
3. Merge 14 + E(16) = 30.
4. Merge 25 + 30 = 55.
5. Merge F(45) + 55 = 100 (root).

              (100)
             0/    \1
          F(45)    (55)
                  0/   \1
               (25)     (30)
              0/  \1   0/   \1
           C(12) D(13) (14)  E(16)
                      0/ \1
                    A(5) B(9)

Total bits $= 45\cdot1 + 12\cdot3 + 13\cdot3 + 5\cdot4 + 9\cdot4 + 16\cdot3 = 45+36+39+20+36+48 = 224$ bits, against $100 \times 3 = 300$ bits for fixed 3-bit codes.

Why balance a binary tree

In an ordinary BST the shape depends on insertion order. Sorted input gives a skewed tree (like a linked list) of height $n$, so search, insertion and deletion degrade to $O(n)$. Balancing keeps the height $O(\log n)$, so all these operations stay $O(\log n)$ in the worst case. An AVL tree does this by keeping the balance factor (height of left - height of right) of every node in $\{-1, 0, 1\}$, using rotations after insertions and deletions.

Constructing the AVL tree

Data: 25, 46, 54, 58, 55, 34, 21, 39, 35, 10, 15

1. Insert 25, 46, 54: 25 becomes unbalanced (right-right). Left rotation gives 46 (25, 54).
2. Insert 58: right of 54.
3. Insert 55: left of 58. Node 54 is unbalanced (right-left). Double rotation gives 55 (54, 58). Tree: 46 (25, 55 (54, 58)).
4. Insert 34: right of 25. Insert 21: left of 25. Balanced.
5. Insert 39: right of 34. Balanced.
6. Insert 35: left of 39. Node 34 is unbalanced (right-left). Double rotation gives 35 (34, 39). Now 25 (21, 35 (34, 39)).
7. Insert 10: left of 21. Balanced.
8. Insert 15: right of 10. Node 21 is unbalanced (left-right). Double rotation gives 15 (10, 21).

Final AVL tree

                 46
              /      \
           25          55
          /   \       /  \
        15     35   54    58
       /  \   /  \
     10   21 34   39

Idea: in each pass find the smallest element of the unsorted part and swap it with the first element of that part.

Algorithm

SelectionSort(A, n)
  for i = 0 to n-2
      min = i
      for j = i+1 to n-1
          if A[j] < A[min]
              min = j
      swap A[i], A[min]

C function

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[min])
                min = j;
        int t = a[i]; a[i] = a[min]; a[min] = t;
    }
}

Trace for 12, 8, 9, 3, 11, 5, 4:

Sorted array: 3, 4, 5, 8, 9, 11, 12. Time complexity is $O(n^2)$ in all cases, with $O(1)$ extra space.

Internal sorting sorts data that fits entirely in main memory (RAM), for example quicksort, heap sort, insertion sort.

External sorting sorts data too large for main memory, so it is kept on external storage (disk/tape) and processed in chunks; typically the data is split into sorted runs that fit in memory, which are then merged (external merge sort). The cost is dominated by disk I/O.

Quicksort of 68, 34, 21, 43, 7, 18, 8, 56, 28, 17

The first element is the pivot; $i$ moves right to find an element greater than the pivot, $j$ moves left to find an element not greater than it. If $i<j$ swap them; otherwise swap the pivot with $a[j]$.

Pass 1 (pivot 68): no element exceeds 68; $j$ stops at 17. Swap 68 and 17:

17, 34, 21, 43, 7, 18, 8, 56, 28, 68

Pass 2 (pivot 17):

• $i$ at 34, $j$ at 8: swap gives 17, 8, 21, 43, 7, 18, 34, 56, 28
• $i$ at 21, $j$ at 7: swap gives 17, 8, 7, 43, 21, 18, 34, 56, 28
• $i$ at 43, $j$ at 7 ($i>j$): swap pivot with 7 gives 7, 8, 17, 43, 21, 18, 34, 56, 28

Left part (7, 8) is already sorted.

Right part (43, 21, 18, 34, 56, 28), pivot 43:

• $i$ at 56, $j$ at 28: swap gives 43, 21, 18, 34, 28, 56
• $i>j$: swap pivot with 28 gives 28, 21, 18, 34, 43, 56

(28, 21, 18, 34) with pivot 28 becomes 18, 21, 28, 34; (18, 21) is already in order.

Sorted array: 7, 8, 17, 18, 21, 28, 34, 43, 56, 68

Average time $O(n\log n)$, worst case $O(n^2)$.

Keys: 1, 16, 49, 36, 25, 64, 0, 81, 4, 9 with $h(x) = x \bmod 10$, table size 10.

i. Linear probing (try the next slot, wrapping around, until empty)

• 1 goes to 1; 16 to 6; 49 to 9.
• 36: slot 6 full, goes to 7.
• 25 to 5; 64 to 4; 0 to 0.
• 81: slot 1 full, goes to 2.
• 4: slots 4, 5, 6, 7 full, goes to 8.
• 9: slot 9 full, then 0, 1, 2 full, goes to 3.

ii. Separate chaining (each slot holds a list, new keys appended)

Spanning tree

A spanning tree of a connected undirected graph with $V$ vertices is a subgraph that contains all the vertices, is connected, and has no cycles; it therefore has exactly $V - 1$ edges. In a weighted graph, the minimum spanning tree (MST) is the spanning tree with the smallest total edge weight. It is found by Kruskal's or Prim's algorithm.

Kruskal's algorithm

1. Sort all edges by increasing weight.
2. Take edges in that order and add an edge if it does not form a cycle with the edges already chosen.
3. Stop when $V-1$ edges have been chosen.

Worked example

Take the graph with edges a-b = 3, a-c = 5, b-c = 1, b-d = 6, c-d = 4, c-e = 7, d-e = 2, d-f = 8, e-f = 5. Here $V = 6$, so the MST has 5 edges.

Sorted: b-c 1, d-e 2, a-b 3, c-d 4, a-c 5, e-f 5, b-d 6, c-e 7, d-f 8.

Five edges are chosen, so we stop.

MST edges: b-c, d-e, a-b, c-d, e-f

Total weight $= 1 + 2 + 3 + 4 + 5 = 15$.

Binary search finds a key in a sorted array by repeatedly halving the search range. It compares the key with the middle element: if equal, it is found; if the key is smaller, search the left half; otherwise search the right half.

Algorithm

BinarySearch(A, n, key)
  low = 0; high = n - 1
  while low <= high
      mid = (low + high) / 2
      if A[mid] == key
          return mid
      else if key < A[mid]
          high = mid - 1
      else
          low = mid + 1
  return -1

Example: A = 10, 20, 30, 40, 50, 60, 70; key = 60.

• low = 0, high = 6, mid = 3, A[3] = 40 < 60, so low = 4.
• low = 4, high = 6, mid = 5, A[5] = 60, found at index 5.

Complexity: each step halves the range, so the time is $O(\log n)$ (best case $O(1)$) and the space is $O(1)$ for the iterative version. It requires sorted data and random access, so it is not suitable for ordinary linked lists. Linear search takes $O(n)$.

ADT (Abstract Data Type)

An ADT is a mathematical model that defines a set of data values and the operations on them, without specifying how they are implemented. For example, the Stack ADT defines push, pop, peek and isEmpty, but not whether an array or a linked list stores the elements.

Why it is needed

• Separates the interface (what) from the implementation (how), giving abstraction and information hiding.
• The implementation can be changed without changing the programs that use it.
• Improves modularity, reusability, and ease of maintenance and testing.
• Lets programmers think at the problem level rather than the memory level.

Types of data structures

Data Structures
 |-- Primitive: int, float, char, boolean
 |-- Non-primitive
      |-- Linear: array, linked list, stack, queue
      |-- Non-linear: tree, graph

• Primitive: basic types provided by the language, such as int, float, char.
• Linear: elements are arranged in sequence.
  • Array: fixed-size contiguous collection with index access, e.g. marks of 50 students.
  • Linked list: nodes joined by pointers, with dynamic size, e.g. a playlist.
  • Stack: LIFO, e.g. undo operation, function calls.
  • Queue: FIFO, e.g. a printer queue.
• Non-linear: elements form a hierarchy or network.
  • Tree: e.g. a folder structure, binary search tree.
  • Graph: vertices and edges, e.g. a road network, social network.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

struct Node *top = NULL;

void push(int x) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Stack Overflow (memory full)\n");
        return;
    }
    newNode->data = x;
    newNode->next = top;
    top = newNode;
    printf("%d pushed\n", x);
}

void pop() {
    if (top == NULL) {
        printf("Stack Underflow\n");
        return;
    }
    struct Node *temp = top;
    printf("%d popped\n", temp->data);
    top = top->next;
    free(temp);
}

void display() {
    struct Node *p = top;
    if (p == NULL) {
        printf("Stack is empty\n");
        return;
    }
    printf("Stack (top to bottom): ");
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

int main() {
    int choice, x;
    while (1) {
        printf("\n1. Push  2. Pop  3. Display  4. Exit\nEnter choice: ");
        if (scanf("%d", &choice) != 1) break;
        switch (choice) {
            case 1:
                printf("Enter value: ");
                scanf("%d", &x);
                push(x);
                break;
            case 2:
                pop();
                break;
            case 3:
                display();
                break;
            case 4:
                exit(0);
            default:
                printf("Invalid choice\n");
        }
    }
    return 0;
}

Both push and pop work at the head of the list (top), so each takes $O(1)$ time.

Need for postfix expressions

In infix form (A + B * C) the order of evaluation depends on operator precedence, associativity and parentheses, so a computer needs several scans to evaluate it. In postfix (Reverse Polish) form the operator comes after its operands, so:

• no parentheses and no precedence rules are needed,
• the expression is evaluated in a single left-to-right scan using one stack (push operands; on an operator, pop two operands, apply it, push the result),
• it is easy for compilers to generate code from.

Conversion of $((A + B) - C * (D / E)) + F$

Scan left to right using a stack for operators; ( is pushed and ) pops until (.

Postfix: $A B + C D E / * - F +$

How AVL solves the problems of a BST

A plain BST can become skewed (for example when keys arrive in sorted order), giving height $n$ and $O(n)$ search, insert and delete. An AVL tree is a self-balancing BST: for each node, the heights of the left and right subtrees differ by at most 1 (balance factor $-1$, $0$, $+1$). After an insertion or deletion that breaks this, single or double rotations (LL, RR, LR, RL) restore balance. The height always stays $O(\log n)$, so all operations are guaranteed $O(\log n)$ in the worst case.

Construction: 22, 27, 31, 10, 5, 16, 29, 19, 11, 3, 4, 8

1. Insert 22, 27, 31: 22 is unbalanced (RR). Left rotation gives 27 (22, 31).
2. Insert 10: left of 22.
3. Insert 5: left of 10. Node 22 is unbalanced (LL). Right rotation gives 10 (5, 22). Tree: 27 (10 (5, 22), 31).
4. Insert 16: left of 22. Node 27 is unbalanced (LR). Double rotation gives 22 (10 (5, 16), 27 (-, 31)).
5. Insert 29: left of 31. Node 27 is unbalanced (RL). Double rotation gives 29 (27, 31). Tree: 22 (10 (5, 16), 29 (27, 31)).
6. Insert 19: right of 16. Insert 11: left of 16. Balanced.
7. Insert 3: left of 5. Balanced.
8. Insert 4: right of 3. Node 5 is unbalanced (LR). Double rotation gives 4 (3, 5).
9. Insert 8: right of 5. Node 22 becomes unbalanced (LL): its left subtree (rooted at 10) has height 4 and its right subtree (rooted at 29) has height 2. Right rotation at 22 makes 10 the root, and 16 (11, 19) becomes the left subtree of 22.

Final AVL tree

                      10
                /            \
              4                22
            /   \            /      \
          3      5         16        29
                   \      /  \      /  \
                    8    11   19   27    31

The tree has 4 levels and all balance factors are within $\pm 1$.

Traversal of a binary tree

Traversal means visiting every node exactly once. The three depth-first recursive methods are:

• Inorder (LNR): traverse the left subtree, visit the root, traverse the right subtree.
• Preorder (NLR): visit the root, traverse the left subtree, traverse the right subtree.
• Postorder (LRN): traverse the left subtree, traverse the right subtree, visit the root.

(Level-order traversal uses a queue and visits level by level.)

The tree: root F; F has children B and G; B has children A and D; D has children C and E; G has right child I; I has left child H.

Inorder (L, N, R)

• Left of F (rooted at B): A, B, then D's subtree (C, D, E): A B C D E
• Root F
• Right of F: G, then I's subtree (H, I): G H I

$\text{Inorder: } A\ B\ C\ D\ E\ F\ G\ H\ I$

Preorder (N, L, R)

• F, then B's subtree: B, A, then D, C, E
• then G's subtree: G, I, H

$\text{Preorder: } F\ B\ A\ D\ C\ E\ G\ I\ H$

Postorder (L, R, N)

• Left subtree of F: A, then D's subtree (C, E, D), then B: A C E D B
• Right subtree of F: H, I, G
• Root: F

$\text{Postorder: } A\ C\ E\ D\ B\ H\ I\ G\ F$

Collision

In hashing, a key is mapped to a table index by a hash function $h(k)$. A collision occurs when two different keys hash to the same index, $h(k_1) = h(k_2)$. Since the key space is larger than the table, collisions cannot be avoided entirely and must be resolved.

Techniques to resolve collisions

1. Separate chaining. Each slot holds a linked list of all keys that hash to it; a colliding key is added to the list. With $m = 10$, $h(k) = k \bmod 10$ and keys 12, 22, 32, index 2 holds 12 -> 22 -> 32. It is simple, never fills up and deletion is easy, but needs extra memory for pointers. Average search time is $O(1+\alpha)$, with load factor $\alpha = n/m$.

2. Linear probing (open addressing). If slot $h(k)$ is taken, try $(h(k)+i) \bmod m$ for $i = 1, 2, \dots$ until a free slot is found. With the same keys, 12 goes to 2, 22 to 3 and 32 to 4. It is simple and cache friendly, but suffers from primary clustering (long runs of filled slots).

3. Quadratic probing. The probe sequence is $(h(k) + i^2) \bmod m$, so the probes jump 1, 4, 9, ... slots. For 12, 22, 32: 12 goes to 2, 22 to 3 ($2+1$), 32 to 6 ($2+4$). This reduces primary clustering, though keys with the same hash follow the same probe path (secondary clustering).

4. Double hashing. The step comes from a second hash: $(h_1(k) + i\cdot h_2(k)) \bmod m$, e.g. $h_2(k) = 7 - (k \bmod 7)$. Different keys follow different probe sequences, which avoids both kinds of clustering, at the cost of computing two hashes.

Priority queue. A priority queue is an abstract data type in which every element carries a priority and the element with the highest priority (for a min priority queue, the smallest key) is removed first, regardless of the order of arrival. Its main operations are insert(x), findMin() and deleteMin(). It is usually implemented with a binary heap, which gives $O(\log n)$ insertion and deletion.

Min heap. A min heap is a complete binary tree in which every parent is smaller than or equal to its children. It is stored in an array: the children of index $i$ are at $2i+1$ and $2i+2$.

Building the heap by inserting 4, 6, 52, 17, 28, 39, 43, 11 one at a time (insert at the next free leaf, then percolate up):

Final min heap:

            4
         /     \
        6       39
       / \     /  \
     11   28  52   43
    /
  17

Deleting the root (4).

1. Remove 4 and move the last element 17 to the root: [17, 6, 39, 11, 28, 52, 43].
2. Percolate down: the smaller child of 17 is 6, so swap: [6, 17, 39, 11, 28, 52, 43].
3. The children of 17 are now 11 and 28; the smaller is 11 < 17, so swap: [6, 11, 39, 17, 28, 52, 43].
4. 17 is now a leaf, so stop.

Heap after deletion:

            6
         /     \
       11       39
      /  \     /  \
    17   28  52   43

Leftist heap. A leftist heap is a binary tree that is heap-ordered (each parent is not larger than its children in a min leftist heap) and satisfies the leftist property: for every node, the null path length (npl) of its left child is at least the npl of its right child. The npl of a node is the length of the shortest path from the node to a node with no two children; npl(null) = -1 and npl(leaf) = 0. Consequently the right path is always short (at most $\log(n+1)$ nodes), and merging, insertion and deleteMin all take $O(\log n)$ time.

Steps of merging two leftist heaps H1 and H2.

1. If one heap is empty, return the other.
2. Compare the roots. Let the heap with the smaller root be H1 (swap names if needed).
3. Recursively merge the right subtree of H1 with H2, and make the result the new right child of H1.
4. If the npl of the left child is smaller than the npl of the right child, swap the two children (restore the leftist property).
5. Update npl(root) = npl(right child) + 1 and return the root.

Example. H1: root 3 with left child 10 and right child 8 (npl = 1). H2: root 6 with left child 12 and no right child (npl = 0).

• $3 < 6$, so 3 stays the root and we merge right(3) = 8 with H2.
• Merge(8, H2): $6 < 8$, so 6 is the root and we merge right(6) = null with 8, which gives 8. So 6 gets left child 12 and right child 8; both have npl 0, so npl(6) = 1.
• Back at 3: its right child is now the subtree rooted at 6 (npl 1) while its left child 10 has npl 0. Since npl(left) < npl(right), swap the children: left = 6, right = 10.

Result:

        3
      /   \
     6     10
    / \
  12   8

External sorting. External sorting is used when the data to be sorted is too large to fit in main memory and resides on disk or tape. The usual method is external merge sort: (1) read as much data as fits in memory, sort it with an internal sort and write it out as a sorted run; (2) repeatedly merge the runs (two-way or k-way merge) using input buffers and one output buffer until a single sorted file remains. The aim is to minimise the number of disk passes, because disk I/O dominates the cost.

Quick sort. Quick sort is a divide-and-conquer algorithm.

1. Choose a pivot (here the first element).
2. Partition: move elements smaller than the pivot to its left and larger ones to its right, so the pivot reaches its final position.
3. Recursively sort the left and right parts.

Example: sort 45, 30, 80, 10, 60, 25, 70.

• Pivot = 45. Scan from the left for an element > 45 (80) and from the right for an element ≤ 45 (25). Swap them: 45, 30, 25, 10, 60, 80, 70. Continue: the left scan stops at 60, the right scan stops at 10; the pointers have crossed, so swap the pivot with 10: 10, 30, 25, 45, 60, 80, 70. 45 is in its final place.
• Left part (10, 30, 25): pivot 10 is already in place; the right part (30, 25) with pivot 30 becomes 25, 30. Left part sorted: 10, 25, 30.
• Right part (60, 80, 70): pivot 60 is in place; (80, 70) with pivot 80 becomes 70, 80. Right part sorted: 60, 70, 80.

Sorted array: 10, 25, 30, 45, 60, 70, 80.

Complexity: best and average case $O(n\log n)$; worst case $O(n^2)$ (already sorted input with a bad pivot choice); space $O(\log n)$ for recursion.

Minimum spanning tree (MST). For a connected, undirected, weighted graph with $n$ vertices, a spanning tree is a subgraph that connects all vertices using exactly $n-1$ edges and has no cycle. The minimum spanning tree is the spanning tree whose total edge weight is the smallest.

Prim's algorithm. Start from any vertex and repeatedly add the cheapest edge that joins a vertex in the tree to a vertex outside it, until all vertices are included.

Since the figure is not reproduced here, take the weighted graph on vertices A to F with edges: A-B = 4, A-C = 3, B-C = 1, B-D = 2, C-D = 4, D-E = 2, D-F = 7, E-F = 6.

Start at A.

MST edges: A-C, C-B, B-D, D-E, E-F (5 edges for 6 vertices).

Total weight = $3 + 1 + 2 + 2 + 6 = 14$.

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

Dynamic programming (DP). Dynamic programming is a technique for solving problems that have overlapping subproblems and optimal substructure. Each subproblem is solved only once and its result is stored in a table (memoization, top-down, or tabulation, bottom-up) and reused, instead of being recomputed. Examples are Fibonacci numbers, the 0/1 knapsack problem, longest common subsequence and matrix-chain multiplication.

Divide and Conquer. This strategy solves a problem in three steps.

1. Divide the problem into smaller independent subproblems of the same type.
2. Conquer each subproblem recursively; a small enough subproblem is solved directly (base case).
3. Combine the sub-solutions to get the solution of the original problem.

Its running time is described by a recurrence such as $T(n) = aT(n/b) + f(n)$.

Example: merge sort of 38, 27, 43, 3.

• Divide: [38, 27, 43, 3] into [38, 27] and [43, 3], then into single elements [38], [27], [43], [3].
• Conquer: single elements are already sorted.
• Combine: merge [38] and [27] into [27, 38]; merge [43] and [3] into [3, 43]; merge [27, 38] and [3, 43] into [3, 27, 38, 43].

Here $T(n) = 2T(n/2) + O(n)$, so $T(n) = O(n\log n)$. Other examples: binary search, quick sort, Strassen's matrix multiplication.

Difference from DP: in divide and conquer the subproblems are independent, whereas in dynamic programming they overlap and their results are stored for reuse.

Extendable hashing is a dynamic hashing technique for large files kept on disk. It allows the hash table to grow and shrink as records are inserted and deleted, without rehashing all the data.

• The hash function maps a key to a binary string, and only the first $d$ bits (the global depth) are used to index a directory of $2^d$ pointers.
• Each directory entry points to a bucket (a disk block) holding a limited number of records. Each bucket has a local depth $d' \le d$, the number of bits that all its keys share; several directory entries may point to the same bucket.
• Insertion: go to the bucket given by the first $d$ bits. If it has room, store the key. If it is full and $d' < d$, split the bucket, increase its local depth and redistribute the keys using one more bit. If it is full and $d' = d$, double the directory ($d$ increases by 1) and then split the bucket.
• Search needs at most one directory access and one bucket access.

Advantages: no overflow chains, only the full bucket is split, and lookups are fast. Disadvantage: the directory can become large if the keys are unevenly distributed.

Breadth First Search (BFS) is a graph traversal method that visits a start vertex, then all its neighbours, then all neighbours of those neighbours, level by level. It uses a queue (FIFO) and a visited array.

Algorithm

1. Mark the start vertex $s$ visited and enqueue it.
2. While the queue is not empty: dequeue a vertex $v$ and process it; for each unvisited neighbour $w$ of $v$, mark it visited and enqueue it.

Example. Graph edges: A-B, A-C, B-D, C-D, D-E. Starting from A: queue [A]; visit A, enqueue B, C; visit B, enqueue D; visit C (D is already visited); visit D, enqueue E; visit E. BFS order: A, B, C, D, E.

Complexity: $O(V+E)$ with an adjacency list, $O(V^2)$ with an adjacency matrix.

Applications: shortest path in an unweighted graph, finding connected components, testing whether a graph is bipartite, and web crawling or social-network "friends at distance k".

Need for data structures. A data structure is a way of organising and storing data in memory so that it can be accessed and modified efficiently. We need data structures because:

• they let us organise large amounts of data logically (e.g. a stack for undo, a queue for printing jobs);
• the right structure makes searching, insertion, deletion and sorting fast, reducing time and memory use;
• they support abstraction and reuse, since the same structure can be used in many programs;
• they are the basis of efficient algorithms (compilers, databases, operating systems, networks).

Linear data structures. The elements form a sequence, each element having one predecessor and one successor, and are traversed in a single run.

• Array: fixed-size collection of same-type elements in contiguous memory with direct index access.
• Linked list: nodes holding data and a pointer to the next node (singly, doubly, circular); dynamic size, easy insertion and deletion.
• Stack: insertion and deletion at one end only (LIFO), with push and pop.
• Queue: insertion at the rear and deletion at the front (FIFO); variants are circular queue, deque and priority queue.

Non-linear data structures. The elements are not in a sequence; one element may be connected to several others.

• Tree: hierarchical structure with a root and child nodes (binary tree, BST, AVL, B-tree, heap). Used for file systems and expression parsing.
• Graph: a set of vertices connected by edges (directed or undirected, weighted or not). Used for road maps, networks and social networks.
• Hash table (often also listed here) maps keys to positions using a hash function for near constant-time lookup.

Linear structures are simple and easy to implement but memory is used sequentially; non-linear structures use memory more flexibly and model complex relationships.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

/* i. Insert a new node at the start of the list */
struct Node* insertAtStart(struct Node *head, int value) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return head;
    }
    newNode->data = value;
    newNode->next = head;   /* new node points to the old first node */
    head = newNode;         /* head now points to the new node */
    return head;
}

/* ii. Remove the end (last) node from the list */
struct Node* removeEnd(struct Node *head) {
    if (head == NULL) {                 /* empty list */
        printf("List is empty\n");
        return NULL;
    }
    if (head->next == NULL) {           /* only one node */
        free(head);
        return NULL;
    }
    struct Node *prev = head;
    struct Node *curr = head->next;
    while (curr->next != NULL) {        /* move to the last node */
        prev = curr;
        curr = curr->next;
    }
    prev->next = NULL;                  /* second last becomes last */
    free(curr);
    return head;
}

void display(struct Node *head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node *head = NULL;
    head = insertAtStart(head, 30);
    head = insertAtStart(head, 20);
    head = insertAtStart(head, 10);
    display(head);          /* 10 -> 20 -> 30 -> NULL */
    head = removeEnd(head);
    display(head);          /* 10 -> 20 -> NULL */
    return 0;
}

Insertion at the start takes $O(1)$ time; removal of the last node takes $O(n)$ time because the list must be traversed to find the second last node.

Why FIFO? A queue is called a FIFO (First In, First Out) structure because elements are inserted at one end (the rear) and removed from the other end (the front). The element that entered first is therefore the first to leave, like people waiting in a line at a ticket counter.

Implementation (array-based circular queue in C):

#include <stdio.h>
#define SIZE 5

int queue[SIZE];
int front = -1, rear = -1;

int isFull()  { return (rear + 1) % SIZE == front; }
int isEmpty() { return front == -1; }

void enqueue(int x) {
    if (isFull()) {
        printf("Queue overflow\n");
        return;
    }
    if (isEmpty())
        front = 0;
    rear = (rear + 1) % SIZE;
    queue[rear] = x;
}

int dequeue() {
    if (isEmpty()) {
        printf("Queue underflow\n");
        return -1;
    }
    int x = queue[front];
    if (front == rear)          /* last element removed */
        front = rear = -1;
    else
        front = (front + 1) % SIZE;
    return x;
}

int main() {
    enqueue(10); enqueue(20); enqueue(30);
    printf("%d\n", dequeue());   /* 10 */
    printf("%d\n", dequeue());   /* 20 */
    enqueue(40);
    printf("%d\n", dequeue());   /* 30 */
    return 0;
}

Both enqueue and dequeue run in $O(1)$ time. The elements come out in the order 10, 20, 30, 40, the same order in which they were inserted.

Binary search tree (BST). A BST is a binary tree in which, for every node, all keys in the left subtree are smaller and all keys in the right subtree are larger than the node's key. An AVL tree is a BST in which the balance factor (height of left subtree minus height of right subtree) of every node is -1, 0 or +1; imbalance is repaired by rotations.

Construction (the duplicate 55 is ignored because a BST/AVL tree holds distinct keys):

1. Insert 10, then 55 (right of 10), then 60 (right of 55): node 10 has balance -2 (right-right case), so rotate left. Root becomes 55 with children 10 and 60.
2. Insert 70 (right of 60). Balanced.
3. Insert 62 (left of 70): node 60 is unbalanced (right-left case). Double rotation makes 62 the subtree root with children 60 and 70. Tree: 55 (10, 62(60, 70)).
4. Insert 20 (right of 10). Balanced.
5. Insert 18 (left of 20): node 10 is unbalanced (right-left case). Double rotation makes 18 the subtree root with children 10 and 20. Tree: 55 (18(10, 20), 62(60, 70)).
6. Insert 12 (right of 10) and 35 (right of 20). All balance factors stay within ±1.

Final AVL tree:

                55
             /      \
          18          62
         /  \        /  \
       10    20    60    70
         \     \
         12     35

Deleting the root (55). The root has two children, so replace it by its inorder successor, the smallest key in the right subtree, which is 60. Delete 60 from its old position (it is a leaf) and put its value at the root.

                60
             /      \
          18          62
         /  \           \
       10    20          70
         \     \
         12     35

Check balance: node 62 has balance -1, node 60 has left height 3 and right height 2 (balance +1), so every node is still within ±1 and no rotation is needed.

Tree traversal means visiting every node of a tree exactly once. For a binary tree the depth-first traversals are inorder, preorder and postorder, and there is also the breadth-first level order traversal.

Consider the tree:

          A
        /   \
       B     C
      / \     \
     D   E     F

1. Inorder (Left, Root, Right).

inorder(node): if node != NULL
    inorder(node->left); visit(node); inorder(node->right)

Result: D B E A C F. For a BST this gives the keys in sorted order.

2. Preorder (Root, Left, Right).

preorder(node): if node != NULL
    visit(node); preorder(node->left); preorder(node->right)

Result: A B D E C F. Used to copy a tree and to get prefix expressions.

3. Postorder (Left, Right, Root).

postorder(node): if node != NULL
    postorder(node->left); postorder(node->right); visit(node)

Result: D E B F C A. Used to delete a tree and to get postfix expressions.

4. Level order (breadth first). Visit nodes level by level from left to right using a queue: enqueue the root; repeatedly dequeue a node, visit it and enqueue its children. Result: A B C D E F.

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

Hash table. A hash table is a data structure that stores keys in an array of size $m$ and uses a hash function $h(k)$ to compute the index where key $k$ is stored, giving average $O(1)$ search, insertion and deletion.

Load factor. $\lambda = n/m$, where $n$ is the number of keys stored and $m$ is the table size. It measures how full the table is; a larger $\lambda$ means more collisions. Here $\lambda = 7/11 \approx 0.64$.

Hash values with $h(k) = k \bmod 11$: 5 → 5, 40 → 7, 18 → 7, 22 → 0, 16 → 5, 30 → 8, 27 → 5.

i) Separate chaining (each slot holds a linked list of the keys that hash to it):

ii) Quadratic probing, using index $(h(k) + i^2) \bmod 11$ for $i = 0, 1, 2, \dots$:

• 5 → slot 5.
• 40 → slot 7.
• 18 → slot 7 is full; $i=1$: slot 8, free, so 18 goes to 8.
• 22 → slot 0.
• 16 → slot 5 is full; $i=1$: slot 6, free, so 16 goes to 6.
• 30 → slot 8 is full; $i=1$: slot 9, free, so 30 goes to 9.
• 27 → slot 5 full; $i=1$: slot 6 full; $i=2$: $5+4=9$ full; $i=3$: $5+9=14 \bmod 11 = 3$, free, so 27 goes to 3.

Binary search finds a key in a sorted array by repeatedly halving the search range. Compare the key with the middle element: if equal, the search ends; if the key is smaller, continue in the left half; otherwise continue in the right half.

Algorithm

low = 0, high = n - 1
while low <= high:
    mid = (low + high) / 2
    if a[mid] == key: return mid
    else if key < a[mid]: high = mid - 1
    else: low = mid + 1
return -1   (not found)

Example. Array: 5, 12, 18, 23, 34, 45, 56 (indices 0 to 6). Search key = 45.

The key is found after 2 comparisons instead of 6 for linear search.

Complexity: the range is halved on every step, so the time is $O(\log n)$ in the worst case and $O(1)$ in the best case; space is $O(1)$ for the iterative version.

Heap. A heap is a complete binary tree that satisfies the heap property: in a max heap every parent is greater than or equal to its children (so the root is the largest), and in a min heap every parent is less than or equal to its children. It is stored in an array, with the children of index $i$ at $2i+1$ and $2i+2$.

Heap as a priority queue. In a priority queue the element with the highest priority is served first. A max heap does this efficiently: the highest priority is always at the root, insert adds the element at the end and moves it up (percolate up), and deleteMax removes the root, moves the last element to the root and moves it down (percolate down). Both take $O(\log n)$ and finding the top item takes $O(1)$.

Building the max heap by inserting 20, 62, 98, 47, 45, 35, 56, 74:

              98
           /      \
        74          62
       /  \        /  \
     47    45    35    56
    /
  20

Serving (dequeue) the highest priority. deleteMax returns 98. Move the last element 20 to the root: [20, 74, 62, 47, 45, 35, 56]. Swap with the larger child 74, then with the larger child 47: [74, 47, 62, 20, 45, 35, 56]. The next element served is therefore 74, then 62, and so on, so the elements leave in order of priority: 98, 74, 62, 56, 47, 45, 35, 20.

Sorting arranges data in a particular order (ascending or descending). It is important because:

• Faster searching: a sorted list can be searched with binary search in $O(\log n)$ instead of $O(n)$ for linear search.
• Easier processing: finding the minimum, maximum, median, duplicates or the k-th largest element becomes trivial in sorted data.
• Efficient algorithms: merging two sorted lists, database joins, and many algorithms (e.g. Kruskal's algorithm sorts the edges) depend on sorted input.
• Better presentation: data such as names in a directory, marks in a result sheet or products by price are easier to read and compare when sorted.
• Detecting duplicates and matching records is easier because equal items are adjacent.

Example. Suppose a list of 1,000,000 student roll numbers is unsorted. To find one roll number we may need up to 1,000,000 comparisons. If the list is sorted, binary search needs at most about $\log_2 10^6 \approx 20$ comparisons. Similarly, for the marks 56, 89, 42, 73, the sorted list 42, 56, 73, 89 shows the lowest, highest and median marks immediately.