Data Structures and Algorithms

A stack follows LIFO, so with a singly linked list the head of the list is used as the top of the stack. Inserting and deleting at the head takes $O(1)$ time, and the stack grows and shrinks dynamically, so there is no fixed-size overflow.

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

Push(x):

1. Allocate a new node n and set n->data = x.
2. Set n->next = top (link it to the current top).
3. Set top = n.

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;
}

Pop():

1. If top == NULL, the stack is empty (underflow).
2. Otherwise save t = top, set top = top->next, read x = t->data, free(t) and return x.

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;
}

Example: push 10, 20, 30 gives top -> 30 -> 20 -> 10 -> NULL. A pop returns 30 and leaves top -> 20 -> 10. The stack is empty when top == NULL. Memory is used only for stored items, at the cost of an extra pointer per element.

List. A list is a finite, ordered collection of elements of the same type in which every element has a position (first, second, ... last). Typical operations are insert, delete, search, traverse and count. A list can be stored contiguously in an array (static, fixed size) or as a linked list, in which each element is a node holding the data and a pointer to the next node, so the list can grow and shrink at run time.

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

Implementing a stack with a linked list. A stack is a LIFO structure: insertion (push) and deletion (pop) take place only at one end, the top. In a linked list, inserting and deleting at the head (front) takes $O(1)$ time, so the head of the list is used as the top of the stack. The pointer top points to the first node; an empty stack has top = NULL. There is no overflow except when memory is exhausted, and no space is wasted by a fixed array size.

PUSH(x):

1. Create a new node p; if memory is not available, report overflow.
2. p->data = x
3. p->next = top
4. top = p

POP:

1. If top == NULL, report underflow and stop.
2. p = top; x = p->data
3. top = top->next
4. free(p); return x

void push(int x) {
    struct node *p = (struct node*)malloc(sizeof(struct node));
    if (p == NULL) { printf("Overflow\n"); return; }
    p->data = x;
    p->next = top;
    top = p;
}

int pop(void) {
    if (top == NULL) { printf("Underflow\n"); return -1; }
    struct node *p = top;
    int x = p->data;
    top = top->next;
    free(p);
    return x;
}

Both operations are $O(1)$. For example, pushing 10, 20, 30 gives top -> 30 -> 20 -> 10 -> NULL; a pop returns 30 and top then points to 20.

Circular linked list. In a circular linked list the next pointer of the last node points back to the first node instead of NULL, so the nodes form a ring and there is no node with a NULL link. It may be singly circular (each node has next only) or doubly circular (next and prev, with the last node's next pointing to the first and the first node's prev pointing to the last).

 external pointer
      |
      v
  [10|*]-->[20|*]-->[30|*]
    ^                  |
    |__________________|

Features and advantages:

• Any node can be reached from any other node, since traversal can start anywhere and continues round the ring.
• It is convenient to keep a pointer last to the last node; then the first node is last->next, so insertion at both the front and the end takes $O(1)$ time.
• It is suitable for round-robin CPU scheduling, a ring of players in a game, and implementing circular queues.
• Traversal must stop when we return to the starting node (p->next == start) instead of testing for NULL, otherwise it loops forever.

Insertion at the front of a circular list with last pointer:

void insert_front(int x) {
    struct node *p = (struct node*)malloc(sizeof(struct node));
    p->data = x;
    if (last == NULL) {          /* empty list */
        last = p;
        p->next = p;
    } else {
        p->next = last->next;
        last->next = p;
    }
}

Traversal:

void display(void) {
    if (last == NULL) return;
    struct node *p = last->next;
    do {
        printf("%d ", p->data);
        p = p->next;
    } while (p != last->next);
}

A binary search tree (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 (duplicates are not allowed or are handled by a fixed rule). An inorder traversal of a BST gives the keys in sorted order.

Node structure

struct node {
    int info;
    struct node *left, *right;
};

Insertion algorithm

1. If the tree is empty, make the new node the root.
2. Otherwise compare the key with the current node. If key $<$ info, go left; if key $>$ info, go right.
3. Repeat until a NULL link is found and attach the new node there.

struct node* insert(struct node *root, int key) {
    if (root == NULL) {
        struct node *p = (struct node*)malloc(sizeof(struct node));
        p->info = key; p->left = p->right = NULL;
        return p;
    }
    if (key < root->info)       root->left  = insert(root->left, key);
    else if (key > root->info)  root->right = insert(root->right, key);
    return root;
}

Search algorithm

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

Deletion has three cases:

1. Node is a leaf: remove it.
2. Node has one child: replace the node by its child.
3. Node has two children: replace its key by the inorder successor (smallest key in the right subtree) or inorder predecessor, then delete that node.

struct node* delete(struct node *root, int key) {
    if (root == NULL) return NULL;
    if (key < root->info)      root->left  = delete(root->left, key);
    else if (key > root->info) root->right = delete(root->right, key);
    else {
        if (root->left == NULL)  { struct node *t = root->right; free(root); return t; }
        if (root->right == NULL) { struct node *t = root->left;  free(root); return t; }
        struct node *s = root->right;
        while (s->left != NULL) s = s->left;
        root->info = s->info;
        root->right = delete(root->right, s->info);
    }
    return root;
}

Example. Insert the keys 50, 30, 70, 20, 40, 60, 80 in this order.

• 50 becomes the root.
• 30 $<$ 50: left child of 50.
• 70 $>$ 50: right child of 50.
• 20 $<$ 50, $<$ 30: left child of 30.
• 40 $<$ 50, $>$ 30: right child of 30.
• 60 $>$ 50, $<$ 70: left child of 70.
• 80 $>$ 50, $>$ 70: right child of 70.

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

Searching for 60: compare with 50 (go right), with 70 (go left), found 60 after 3 comparisons. Inorder traversal gives 20, 30, 40, 50, 60, 70, 80 (sorted). Deleting 30 (two children) replaces it with its inorder successor 40, leaving 40 with left child 20.

Complexity. Search, insert and delete take $O(h)$ where $h$ is the height: $O(\log n)$ for a balanced tree and $O(n)$ in the worst case (a skewed tree from sorted input).

Circular list. A circular list is a linked list in which the last node points back to the first node instead of NULL, so the list forms a ring. Any node can be reached from any other node, and there is no NULL pointer. It may be singly or doubly linked. A single external pointer to the last node gives access to both ends: last->next is the first node.

Stack as a circular list. A stack needs access to only one end (the top). Using a circular list, a single external pointer top/last is kept, and last->next is the top node.

• Push: new node is inserted after last (at the front of the list), so last->next always refers to the top; the last node's link is updated.
• Pop: the node after last is deleted.
• Both operations are done at the same end, in $O(1)$ time. Order is LIFO.

Queue as a circular list. A queue needs access to both ends. With one pointer rear pointing to the last node, rear->next is the front.

• Insert (enqueue): a new node is placed after rear and rear is moved to it.
• Delete (dequeue): the node rear->next (front) is removed.
• Insertion at the rear and deletion at the front, both $O(1)$. Order is FIFO.

Huffman algorithm is a greedy algorithm that builds an optimal prefix code (variable-length binary codes, no code is a prefix of another) for data compression. Frequent symbols get short codes and rare symbols get long codes.

Procedure

1. Create a leaf node for each symbol with its frequency, and put all nodes in a priority queue (min-heap) ordered by frequency.
2. Remove the two nodes with the smallest frequencies.
3. Create a new internal node whose frequency is their sum, with these two nodes as children, and insert it back into the queue.
4. Repeat steps 2 and 3 until only one node remains. It is the root of the Huffman tree.
5. Label every left edge 0 and every right edge 1. The code of a symbol is the sequence of labels from the root to its leaf.

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

• Merge A(5) and B(9) to get N1 = 14.
• Merge C(12) and D(13) to get N2 = 25.
• Merge N1(14) and E(16) to get N3 = 30.
• Merge N2(25) and N3(30) to get N4 = 55.
• Merge F(45) and N4(55) to get root = 100.

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

With left = 0 and right = 1:

Total bits $= 45(1)+12(3)+13(3)+5(4)+9(4)+16(3) = 45+36+39+20+36+48 = 224$.

A fixed 3-bit code would need $3\times100=300$ bits, so Huffman coding saves $76$ bits ($\approx 25\%$).

Decoding is done by reading bits from the root: go left on 0, right on 1, output the symbol on reaching a leaf and restart. With a heap, building the tree takes $O(n\log n)$.

struct S { int a; float b; char c; };   // size about 4+4+1 (+padding) = 12 bytes
union  U { int a; float b; char c; };   // size 4 bytes

Big O notation gives an asymptotic upper bound on the growth rate of an algorithm's running time (or space) as the input size $n$ becomes large. It describes the worst-case order of growth and ignores constants and lower-order terms.

Definition. $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 .$

Example. For $f(n)=3n+2$: since $3n+2\le 4n$ for all $n\ge 2$, we have $c=4$, $n_0=2$, so $f(n)=O(n)$. Similarly $5n^2+3n+1=O(n^2)$.

Common orders (slowest growth to fastest): $O(1)<O(\log n)<O(n)<O(n\log n)<O(n^2)<O(n^3)<O(2^n)<O(n!)$

Examples: array access $O(1)$, binary search $O(\log n)$, linear search $O(n)$, merge sort $O(n\log n)$, bubble sort $O(n^2)$.

Big O is used to compare algorithms independently of the machine and language.

Infix expressions (operator between operands, e.g. $A+B$) need precedence and parenthesis rules. Postfix expressions (operator after operands, $AB+$) do not, so conversion uses a stack to hold operators.

Precedence: ^ (highest, right-associative), then * /, then + -. Parentheses override precedence.

Algorithm

1. Scan the infix expression from left to right.
2. If the symbol is an operand, append it to the postfix output.
3. If it is (, push it on the stack.
4. If it is ), pop operators from the stack to the output until ( is found; discard both parentheses.
5. If it is an operator, pop operators from the stack to the output while the top has higher precedence than the scanned operator (or equal precedence for left-associative operators); then push the scanned operator.
6. After the scan ends, pop all remaining operators to the output.

Example. Convert $A+B*C-D$.

Result: $ABC*+D-$. The algorithm runs in $O(n)$ time.

The Tower of Hanoi is a classic recursive puzzle. There are three pegs (source A, auxiliary B, destination C) and $n$ disks of different sizes stacked on A with the largest at the bottom. The task is to move all disks to C obeying two rules: move only one disk at a time, and never place a larger disk on a smaller one.

Recursive idea

To move $n$ disks from A to C using B:

1. Move the top $n-1$ disks from A to B (using C).
2. Move the largest disk from A to C.
3. Move the $n-1$ disks from B to C (using A).

void toh(int n, char from, char to, char aux) {
    if (n == 0) return;
    toh(n-1, from, aux, to);
    printf("Move disk %d from %c to %c\n", n, from, to);
    toh(n-1, aux, to, from);
}

Example, $n=3$ (A to C using B), 7 moves:

1. Disk 1: A to C
2. Disk 2: A to B
3. Disk 1: C to B
4. Disk 3: A to C
5. Disk 1: B to A
6. Disk 2: B to C
7. Disk 1: A to C

Number of moves. $T(n)=2T(n-1)+1$, $T(1)=1$, giving $T(n)=2^n-1 .$ For $n=3$: $2^3-1=7$. The time complexity is $O(2^n)$. A practical use is the stack-based nature of recursion, and it is a standard demonstration of how recursion simplifies a problem.

A doubly linked list is a linked list in which each node has two pointers: one to the next node and one to the previous node. It can be traversed in both directions.

struct node {
    int info;
    struct node *prev;
    struct node *next;
};

NULL <- [prev|10|next] <-> [prev|20|next] <-> [prev|30|next] -> NULL

Advantages: traversal in both directions; a node can be deleted given only a pointer to it (no need to track the previous node); easy insertion before a node. Disadvantages: extra memory for the second pointer; more pointer updates for each operation.

Example: insert a new node p after node q.

p->prev = q;
p->next = q->next;
if (q->next != NULL)
    q->next->prev = p;
q->next = p;

Example: delete node q.

if (q->prev != NULL) q->prev->next = q->next;
if (q->next != NULL) q->next->prev = q->prev;
free(q);

If the list holds 10, 20, 30 and 25 is inserted after 20, the list becomes 10 <-> 20 <-> 25 <-> 30. Both insertion and deletion at a known position take $O(1)$.

A binary tree is a tree in which each node has at most two children (left and right). The main types are:

1. Strictly (full) binary tree: every node has either 0 or 2 children. A strictly binary tree with $n$ leaves has $2n-1$ nodes.
2. Complete binary tree: all levels are completely filled except possibly the last, and the last level is filled from left to right. Heaps are complete trees.
3. Perfect binary tree: all internal nodes have two children and all leaves are at the same level. It has $2^{h+1}-1$ nodes for height $h$.
4. Skewed binary tree: every node has only a left child (left-skewed) or only a right child (right-skewed); behaves like a linked list.
5. Binary search tree: left subtree keys $<$ node $<$ right subtree keys.
6. Balanced tree (AVL): for every node the heights of the left and right subtrees differ by at most 1.
7. Expression tree: leaves are operands and internal nodes are operators.

Comparison

Both are depth-first traversals of a binary tree, defined recursively. They differ in when the root (current node) is visited.

Example tree:

      A
     / \
    B   C
   / \
  D   E

• Preorder: A B D E C
• Inorder: D B E A C

void preorder(struct node *t) { if (t) { printf("%d ", t->info); preorder(t->left); preorder(t->right); } }
void inorder(struct node *t)  { if (t) { inorder(t->left); printf("%d ", t->info); inorder(t->right); } }

Sorting is the process of arranging the elements of a list in a specified order, ascending or descending (numerically or alphabetically). Sorting makes searching and processing data faster.

Bubble sort. It repeatedly compares adjacent elements and swaps them if they are in the wrong order. After each pass the largest remaining element "bubbles" to its final position at the end. For $n$ elements, $n-1$ passes are needed; pass $i$ compares the first $n-i$ pairs. If a pass makes no swap, the list is sorted and the algorithm can stop.

void bubble(int a[], int n) {
    for (int i = 0; i < n-1; i++) {
        int swapped = 0;
        for (int j = 0; j < n-1-i; j++)
            if (a[j] > a[j+1]) {
                int t = a[j]; a[j] = a[j+1]; a[j+1] = t;
                swapped = 1;
            }
        if (!swapped) break;
    }
}

Example. Sort 5, 1, 4, 2, 8.

• Pass 1: (5,1) swap: 1 5 4 2 8; (5,4) swap: 1 4 5 2 8; (5,2) swap: 1 4 2 5 8; (5,8) no swap. Result 1 4 2 5 8.
• Pass 2: (1,4) no; (4,2) swap: 1 2 4 5 8; (4,5) no. Result 1 2 4 5 8.
• Pass 3: no swaps, so the list is sorted: 1 2 4 5 8.

Complexity. Worst and average case $O(n^2)$ (about $n(n-1)/2$ comparisons); best case $O(n)$ with the swap flag; space $O(1)$; it is stable.

Kruskal's algorithm finds a minimum spanning tree (MST) of a connected, weighted, undirected graph using the greedy approach: it repeatedly adds the cheapest edge that does not form a cycle.

Algorithm

1. Sort all edges in non-decreasing order of weight.
2. Start with a forest in which each vertex is its own component.
3. Take the next smallest edge. If its end points lie in different components, add it to the MST and merge the components (checked with union-find); otherwise discard it, since it would form a cycle.
4. Stop when $V-1$ edges have been selected.

With sorting, the time complexity is $O(E\log E)$.

Example. Vertices A, B, C, D, E with edges: B-C = 1, A-C = 2, D-E = 2, A-B = 4, B-D = 5, C-D = 8, C-E = 10.

Four edges ($V-1=4$) are selected, so the algorithm stops. MST edges: B-C, A-C, D-E, B-D with total weight $1+2+2+5=10$.

Infix notation places the operator between its operands and needs precedence and parenthesis rules. Postfix notation places the operator after its operands and needs neither. A stack is used to hold operators (and parentheses) until their operands have been output, which reverses the order of operators according to precedence.

Algorithm

1. Scan the infix expression from left to right.
2. If the symbol is an operand, send it directly to the postfix output.
3. If it is (, push it on the stack.
4. If it is ), pop operators to the output until ( is on top; pop and discard (.
5. If it is an operator, while the stack top is an operator of higher or equal precedence (for left-associative operators), pop it to the output; then push the scanned operator.
6. At the end of the expression, pop all remaining operators to the output.

Precedence: ^ $>$ *, / $>$ +, -; ( has the lowest precedence while on the stack.

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

The postfix expression is $AB+CD-*$.

Check by evaluation. Let $A=2, B=3, C=7, D=4$. Infix: $(2+3)\times(7-4)=15$. Postfix: push 2, 3; + gives 5; push 7, 4; - gives 3; * gives $5\times3=15$.

Divide and conquer. It is an algorithm design technique that solves a problem in three steps:

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

Examples: merge sort, quick sort, binary search, Strassen's matrix multiplication.

Quick sort. Choose a pivot element, partition the array so that elements smaller than the pivot are on its left and larger elements on its right (the pivot is then in its final position), and sort the two parts recursively. The combine step is trivial.

void quick(int a[], int lo, int hi) {
    if (lo >= hi) return;
    int p = a[lo], i = lo + 1, j = hi;
    while (1) {
        while (i <= hi && a[i] <= p) i++;
        while (a[j] > p) j--;
        if (i >= j) break;
        int t = a[i]; a[i] = a[j]; a[j] = t;
    }
    a[lo] = a[j]; a[j] = p;
    quick(a, lo, j-1);
    quick(a, j+1, hi);
}

Hand test on 78, 34, 21, 43, 7, 18, 9, 56, 38, 19 (first element as pivot). Each partition places the pivot in its final position:

Combining the pivots and single elements in order gives the sorted array:

7, 9, 18, 19, 21, 34, 38, 43, 56, 78

Time complexity of quick sort

• Best case (pivot splits the array into equal halves): $T(n)=2T(n/2)+O(n)$, giving $O(n\log n)$.
• Average case: $O(n\log n)$.
• Worst case (already sorted or reverse-sorted input with first/last pivot, as at the first step above): $T(n)=T(n-1)+O(n)$, giving $O(n^2)$.
• Space: $O(\log n)$ on average for the recursion stack.

Graph traversal visits every vertex reachable from a start vertex exactly once. The two standard methods are depth first search (DFS) and breadth first search (BFS).

Depth first traversal (DFS)

DFS goes as deep as possible along a path before backtracking. It uses a stack (or recursion).

1. Visit the start vertex, mark it visited and push it.
2. While the stack is not empty, look at the top vertex; if it has an unvisited neighbour, visit it, mark it and push it; otherwise pop the top vertex (backtrack).

void dfs(int v) {
    visited[v] = 1; printf("%d ", v);
    for (int w = 0; w < n; w++)
        if (adj[v][w] && !visited[w]) dfs(w);
}

Breadth first traversal (BFS)

BFS visits all neighbours of a vertex before moving to the next level. It uses a queue.

1. Visit the start vertex, mark it and enqueue it.
2. While the queue is not empty, dequeue a vertex and enqueue all its unvisited neighbours (marking them visited as they are visited).

void bfs(int s) {
    int q[MAX], f = 0, r = 0;
    visited[s] = 1; q[r++] = s;
    while (f < r) {
        int v = q[f++]; printf("%d ", v);
        for (int w = 0; w < n; w++)
            if (adj[v][w] && !visited[w]) { visited[w] = 1; q[r++] = w; }
    }
}

Example. Graph with edges A-B, A-C, B-D, B-E, C-F, E-F. Adjacency lists (alphabetical order): A: B, C; B: A, D, E; C: A, F; D: B; E: B, F; F: C, E.

DFS from A: visit A, go to B, then D (dead end, backtrack to B), then E, then F, then C. DFS order: A B D E F C.

BFS from A: queue A; dequeue A and add B, C; dequeue B and add D, E; dequeue C and add F; then D, E, F have no new neighbours. BFS order: A B C D E F.

Complexity. Both take $O(V+E)$ with adjacency lists and $O(V^2)$ with an adjacency matrix. DFS is used for cycle detection, topological sorting and connected components; BFS for shortest paths in unweighted graphs.

Complexity of an algorithm. The complexity of an algorithm measures the resources it needs as a function of the input size $n$. There are two kinds:

• Time complexity: the amount of time (number of basic operations) the algorithm takes.
• Space complexity: the amount of memory the algorithm uses, including input, auxiliary variables and recursion stack.

It is usually expressed in asymptotic notation: Big O (upper bound), Omega (lower bound) and Theta (tight bound), and analysed for the best, average and worst cases.

Finding time complexity

1. Choose the basic operation (comparison, assignment, arithmetic) and the input size $n$.
2. Count how many times it executes as a function of $n$.
3. Keep the dominant term and drop constants and lower-order terms.

Rules:

• A simple statement costs $O(1)$.
• A sequence of statements: add the costs, so the maximum dominates.
• A loop: (cost of the body) $\times$ (number of iterations).
• Nested loops: multiply the iteration counts.
• A loop where the counter doubles or halves each time runs $\log_2 n$ times.
• A recursive algorithm gives a recurrence, e.g. $T(n)=2T(n/2)+n$, solved by substitution or the master theorem, giving $O(n\log n)$.

Examples

for (i = 0; i < n; i++)           // n times
    sum += i;                      // O(n)

for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)       // n * n times
        count++;                   // O(n^2)

for (i = 1; i < n; i *= 2)        // log2 n times
    x++;                           // O(log n)

For the nested loops the operation count is $n^2$, so $T(n)=O(n^2)$. For a loop with a body that runs $1+2+\dots+n=\frac{n(n+1)}{2}$ times, $T(n)=O(n^2)$.

Stack vs queue

Linear queue vs circular queue

Abstract data type (ADT). An ADT is a mathematical model of a data structure that specifies the data it holds and the operations that can be done on it, together with their behaviour, without saying how they are implemented. The user works only through the interface (information hiding). The same ADT can be implemented with arrays or linked lists. Examples: stack, queue, list, tree.

Stack as an ADT

Data: an ordered collection of elements of one type, with insertion and deletion allowed only at one end, the top. It follows the LIFO principle.

Operations:

Axioms: pop(push(S, x)) = S, and peek(push(S, x)) = x.

#define MAX 100
struct stack { int items[MAX]; int top; };   // top = -1 means empty

void push(struct stack *s, int x) {
    if (s->top == MAX-1) printf("Overflow\n");
    else s->items[++s->top] = x;
}
int pop(struct stack *s) {
    if (s->top == -1) { printf("Underflow\n"); return -1; }
    return s->items[s->top--];
}

All operations take $O(1)$ time. Applications include function calls, expression conversion and evaluation, and undo operations.

Recursive algorithm. A recursive algorithm is one that solves a problem by calling itself on smaller instances of the same problem. It must have:

1. A base case (stopping condition) that is solved directly.
2. A recursive case that reduces the problem towards the base case.

Examples: factorial, Fibonacci numbers, Tower of Hanoi, tree traversal.

Implementation in programs. A recursive algorithm is written as a function that calls itself. Each call creates a new activation record (parameters, local variables, return address) on the system call stack. When the base case is reached, calls return one by one, in the reverse order (LIFO).

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

Trace of fact(3): fact(3) calls fact(2), which calls fact(1), which calls fact(0) returning 1. Then fact(1) = 1, fact(2) = 2, fact(3) = 6.

Fibonacci:

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

Points to remember. Without a reachable base case the recursion never ends (stack overflow). Recursion gives short and clear code but uses extra stack space and function-call overhead; any recursive algorithm can be converted to an iterative one using an explicit stack.

Benefits of a linked list over an array

Drawbacks: extra memory for pointers and no direct (random) access, so access to the $i$-th element is $O(n)$.

Inserting a node in a singly linked list

struct node { int info; struct node *next; };

(a) At the beginning:

p = (struct node*)malloc(sizeof(struct node));
p->info = x;
p->next = head;
head = p;

(b) At the end:

p->info = x; p->next = NULL;
if (head == NULL) head = p;
else {
    q = head;
    while (q->next != NULL) q = q->next;
    q->next = p;
}

(c) After a given node q:

p->info = x;
p->next = q->next;
q->next = p;

The order of the last two statements matters: set p->next first, otherwise the rest of the list is lost. Insertion at the beginning or after a given node takes $O(1)$; at the end it takes $O(n)$ (without a tail pointer).

Binary search. It finds a key in a sorted array by repeatedly comparing the key with the middle element:

1. Set low = 0, high = n-1.
2. While low <= high: compute mid = (low + high) / 2.
3. If a[mid] == key, the search is successful; return mid.
4. If key < a[mid], set high = mid - 1; otherwise set low = mid + 1.
5. If the loop ends, the key is not present.

int binsearch(int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key) return mid;
        else if (key < a[mid]) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

A recursive version calls binsearch(a, low, mid-1, key) or binsearch(a, mid+1, high, key).

Example. Search 23 in 2, 5, 8, 12, 16, 23, 38, 56 (indices 0 to 7): mid = 3 (12), 23 $>$ 12 so low = 4; mid = 5 (23), found at index 5.

Time complexity. Each step halves the search range, so the recurrence is $T(n)=T(n/2)+1$, which gives $T(n)=O(\log_2 n)$ in the worst and average case, and $O(1)$ in the best case (key at the middle). Space is $O(1)$ for the iterative version.

Hashing. Hashing is a technique for storing and searching data in nearly constant time. A hash function $h(k)$ maps a key $k$ to an index of a hash table, e.g. $h(k)=k \bmod m$ for table size $m$. When two keys map to the same index, a collision occurs; it is resolved by chaining (linked list at each slot) or open addressing (linear probing, quadratic probing, double hashing). Search, insert and delete take $O(1)$ on average.

Rehashing. In open addressing, as the table fills, the load factor $\lambda = n/m$ (number of keys / table size) grows, collisions increase and performance falls; insertion may even fail. Rehashing builds a new, larger table (usually about twice the size, rounded up to a prime number), a new hash function with the new size is used, and every existing key is reinserted into the new table. It is done when $\lambda$ exceeds a threshold (such as 0.7) or when an insertion fails. Its cost is $O(n)$ but it happens rarely, so the amortised cost of an insertion stays $O(1)$.

Example. Table size $m=7$, $h(k)=k \bmod 7$, linear probing. Insert 13, 15, 6, 24, 23.

• 13 mod 7 = 6, so index 6.
• 15 mod 7 = 1, so index 1.
• 6 mod 7 = 6, occupied, so next free index is 0 (wraps around).
• 24 mod 7 = 3, so index 3.
• 23 mod 7 = 2, so index 2.

Load factor $=5/7\approx0.71>0.7$, so rehash. New size = next prime after $2\times7=14$, that is 17, with $h(k)=k\bmod 17$. Reinsert the keys in old table order 6, 15, 23, 24, 13:

• 6 mod 17 = 6, index 6.
• 15 mod 17 = 15, index 15.
• 23 mod 17 = 6, occupied, so index 7.
• 24 mod 17 = 7, occupied, so index 8.
• 13 mod 17 = 13, index 13.

Load factor falls to $5/17\approx0.29$, so collisions are reduced.

Traversing a binary tree means visiting every node exactly once in some systematic order. Since a tree is not linear, there are several orders. Each is defined recursively in terms of N (visit the node), L (traverse the left subtree) and R (traverse the right subtree).

1. Preorder (N L R): visit the root, traverse the left subtree in preorder, then the right subtree in preorder.

2. Inorder (L N R): traverse the left subtree, visit the root, then traverse the right subtree. For a binary search tree this gives the keys in sorted order.

3. Postorder (L R N): traverse the left subtree, the right subtree, then visit the root.

4. Level order: visit nodes level by level from left to right, using a queue.

void preorder(struct node *t)  { if (t) { printf("%d ", t->info); preorder(t->left); preorder(t->right); } }
void inorder(struct node *t)   { if (t) { inorder(t->left); printf("%d ", t->info); inorder(t->right); } }
void postorder(struct node *t) { if (t) { postorder(t->left); postorder(t->right); printf("%d ", t->info); } }

Example

        A
       / \
      B   C
     / \   \
    D   E   F

• Preorder: A B D E C F
• Inorder: D B E A C F
• Postorder: D E B F C A
• Level order: A B C D E F

Each traversal visits every node once, so the time is $O(n)$; the recursion stack needs $O(h)$ space, where $h$ is the tree height. Preorder is used to copy a tree, inorder to get sorted output, and postorder to delete a tree or evaluate an expression tree.

(a) Dynamic memory allocation

Dynamic memory allocation is the process of requesting memory from the heap at run time, when the program actually needs it, instead of fixing the size at compile time. The memory can be released when it is no longer needed, so the program uses only as much memory as the data requires.

In C, the functions of <stdlib.h> are used:

• malloc(size) allocates size bytes (uninitialised) and returns a void *.
• calloc(n, size) allocates n blocks and initialises them to zero.
• realloc(ptr, newsize) resizes a previously allocated block.
• free(ptr) returns the block to the heap.

int *a = (int *)malloc(n * sizeof(int));
if (a == NULL) { /* allocation failed */ }
...
free(a);

It is the basis of linked lists, trees and graphs, where nodes are created and deleted as needed. Advantages are no wastage of memory and flexible size; disadvantages are slower access and the risk of memory leaks and dangling pointers if free is forgotten or misused.

(b) Game tree

A game tree is a tree that represents all possible moves of a two-player game (such as tic-tac-toe or chess). Each node is a game position (state) and each edge is a legal move. The root is the current position; levels alternate between the two players (MAX and MIN). The leaves are terminal positions (win, lose, draw) which are given a score.

To choose the best move, the minimax algorithm is used: at MAX levels the child with the largest value is chosen and at MIN levels the child with the smallest value is chosen, and values are propagated up to the root. Alpha-beta pruning reduces the work by skipping branches that cannot affect the final decision. Since the tree grows exponentially (branching factor $b$, depth $d$ gives about $b^d$ nodes), real programs limit the depth and use an evaluation function.

Stack

A stack is a linear data structure in which insertion and deletion are done at only one end, called the top. It follows the LIFO (Last In First Out) rule: the element inserted last is removed first. Example: a pile of plates.

Applications of stack

• Function call management and recursion (call stack).
• Conversion of infix expressions to postfix or prefix.
• Evaluation of postfix and prefix expressions.
• Undo/redo in editors; back button in browsers.
• Checking balanced parentheses.
• Reversing a string or list.
• Depth-first search and backtracking (maze, N-queens).

Stack operations

• push(x): insert element $x$ at the top. If the stack is full, it is overflow.
• pop(): remove and return the top element. If the stack is empty, it is underflow.
• peek()/top(): read the top element without removing it.
• isEmpty(), isFull(): test the state of the stack.

Array implementation (with top = -1 initially, size MAX):

void push(int x) {
    if (top == MAX - 1) printf("Overflow");
    else s[++top] = x;
}
int pop() {
    if (top == -1) { printf("Underflow"); return -1; }
    return s[top--];
}

Example. Start with an empty stack.

Each push and pop takes $O(1)$ time.

Singly vs doubly linked list

Node structure of a doubly linked list:

struct node {
    int data;
    struct node *prev, *next;
};
struct node *head = NULL;

Insertion

At the beginning:

void insertBeg(int x) {
    struct node *n = malloc(sizeof(struct node));
    n->data = x; n->prev = NULL; n->next = head;
    if (head != NULL) head->prev = n;
    head = n;
}

After a given node p:

void insertAfter(struct node *p, int x) {
    struct node *n = malloc(sizeof(struct node));
    n->data = x;
    n->next = p->next;
    n->prev = p;
    if (p->next != NULL) p->next->prev = n;
    p->next = n;
}

At the end: traverse to the last node t, then set n->prev = t; n->next = NULL; t->next = n; (if the list is empty, head = n).

Deletion

Delete the first node:

void delBeg() {
    if (head == NULL) return;
    struct node *t = head;
    head = head->next;
    if (head != NULL) head->prev = NULL;
    free(t);
}

Delete a given node p:

void delNode(struct node *p) {
    if (p->prev != NULL) p->prev->next = p->next;
    else head = p->next;            /* p was first */
    if (p->next != NULL) p->next->prev = p->prev;
    free(p);
}

Insertion or deletion at a known position takes $O(1)$ time; finding the position takes $O(n)$.

Shortest path

In a weighted graph, the shortest path between two vertices is the path whose sum of edge weights is minimum among all paths between them. The single-source shortest path problem finds shortest paths from one source vertex to all other vertices.

Dijkstra's algorithm

It works for graphs with non-negative edge weights and uses a greedy strategy: repeatedly pick the unvisited vertex with the smallest known distance and relax its outgoing edges.

1. Set dist[source] = 0 and dist[v] = infinity for all other vertices; mark all vertices unvisited.
2. Select the unvisited vertex $u$ with the smallest dist; mark it visited.
3. For each neighbour $v$ of $u$: if $dist[u] + w(u,v) < dist[v]$, then set $dist[v] = dist[u] + w(u,v)$ and parent[v] = u.
4. Repeat steps 2 and 3 until all vertices are visited.

Dijkstra(G, s):
    for each v: dist[v] = INF, visited[v] = false
    dist[s] = 0
    repeat n times:
        u = unvisited vertex with minimum dist
        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

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

Example. Edges: A-B = 4, A-C = 2, B-C = 1, B-D = 5, C-D = 8, C-E = 10, D-E = 2 (undirected). Source = A.

Shortest distances from A: B = 3, C = 2, D = 8, E = 10. The paths are A-C-B (3), A-C (2), A-C-B-D (8) and A-C-B-D-E (10).

Dynamic memory allocation

Dynamic memory allocation means obtaining memory from the heap at run time as required and releasing it when it is no longer needed. In C it is done using malloc(), calloc(), realloc() and free().

int *p = (int *)malloc(5 * sizeof(int));  /* space for 5 integers */
p = (int *)realloc(p, 10 * sizeof(int));  /* grow to 10 */
free(p);                                  /* release */

Compared with static allocation (fixed at compile time, e.g. int a[5];), it avoids wasting memory, allows structures such as linked lists and trees to grow and shrink, and gives the programmer control over lifetime. The price is slower allocation and the risk of memory leaks and dangling pointers.

Data structure vs abstract data type (ADT)

An ADT is a mathematical/logical model that specifies a set of data and the operations on it, without saying how they are implemented (for example Stack, Queue, List). A data structure is the concrete implementation of that model in a programming language, with actual storage and algorithms (for example a stack implemented using an array or a linked list).

Evaluation of a postfix expression using a stack

In postfix (reverse Polish) notation the operator comes after its operands, e.g. a b +. No parentheses or precedence rules are needed, so the expression can be evaluated in one left-to-right scan with a stack of operands.

Algorithm

1. Create an empty stack.
2. Scan the expression from left to right, one symbol at a time.
3. If the symbol is an operand, push its value onto the stack.
4. If the symbol is an operator, pop two values: first pop gives $op_2$ (the right operand) and second pop gives $op_1$ (the left operand). Compute $op_1 \;\text{operator}\; op_2$ and push the result.
5. After the whole expression is scanned, the single value left on the stack is the result.

evalPostfix(P):
    for each symbol ch in P:
        if ch is operand: push(value(ch))
        else:
            b = pop(); a = pop()
            push(a ch b)
    return pop()

The order matters for non-commutative operators ($-$, $/$, $\wedge$): the second popped value is the left operand.

Example. Evaluate 5 6 2 + * 12 4 / -.

Result $= 37$. Time complexity is $O(n)$ for an expression of $n$ symbols.

Queue as an ADT

A queue is a linear collection in which insertion takes place at one end (rear) and deletion at the other end (front). It follows FIFO (First In First Out). As an abstract data type, it is defined by its data and operations, independent of implementation.

ADT specification

Data: an ordered collection of elements with a front and a rear.

Operations:

• create(): make an empty queue.
• enqueue(x): insert $x$ at the rear. Precondition: queue not full.
• dequeue(): remove and return the front element. Precondition: queue not empty.
• front(): return the front element without removing it.
• isEmpty(): true if the queue has no element.
• isFull(): true if no more elements can be added (bounded implementation).

Array implementation (linear queue)

#define MAX 100
int q[MAX], front = 0, rear = -1;

void enqueue(int x) {
    if (rear == MAX - 1) printf("Overflow");
    else q[++rear] = x;
}
int dequeue() {
    if (front > rear) { printf("Underflow"); return -1; }
    return q[front++];
}

Queue is empty when front > rear. A drawback is that freed positions at the front are not reused; a circular queue (using (rear+1) % MAX) removes this problem.

Linked implementation: enqueue adds a node at the tail and dequeue removes the head node; no fixed size limit.

Each operation takes $O(1)$ time.

Types: simple queue, circular queue, double-ended queue (deque) and priority queue.

Applications: CPU/job scheduling, printer spooling, buffering in I/O, breadth-first search, call centre waiting lines.

Recursive GCD (Euclid's algorithm)

The GCD of two numbers $a$ and $b$ satisfies

$\gcd(a,b)=\begin{cases} a & \text{if } b=0\\ \gcd(b,\; a \bmod b) & \text{otherwise}\end{cases}$

The base case is $b = 0$, and each call reduces $b$, so the recursion terminates.

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int x, y;
    printf("Enter two numbers: ");
    scanf("%d %d", &x, &y);
    printf("GCD of %d and %d = %d\n", x, y, gcd(x, y));
    return 0;
}

Trace for gcd(48, 18):

• gcd(48, 18) calls gcd(18, 12) since $48 \bmod 18 = 12$
• gcd(18, 12) calls gcd(12, 6) since $18 \bmod 12 = 6$
• gcd(12, 6) calls gcd(6, 0) since $12 \bmod 6 = 0$
• gcd(6, 0) returns 6

So $\gcd(48,18)=6$. The time complexity is $O(\log(\min(a,b)))$.

Linked list

A linked list is a linear data structure made of nodes. Each node has a data field and a link (pointer) to the next node; the last node points to NULL. A pointer head holds the address of the first node. Nodes are created dynamically and are not stored in contiguous memory.

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

Types: singly linked list, doubly linked list and circular linked list.

Difference between linked list and array

Arrays suit situations with frequent index access and fixed size; linked lists suit frequent insertions and deletions and unknown size.

Bubble sort

Bubble sort compares adjacent elements and swaps them if they are out of order. After each pass the largest remaining element moves ("bubbles") to its final position at the right end.

Array: 53, 42, 78, 3, 5, 2, 15 (ascending order).

Pass 1

• 53 > 42, swap: 42, 53, 78, 3, 5, 2, 15
• 53 < 78, no swap
• 78 > 3, swap: 42, 53, 3, 78, 5, 2, 15
• 78 > 5, swap: 42, 53, 3, 5, 78, 2, 15
• 78 > 2, swap: 42, 53, 3, 5, 2, 78, 15
• 78 > 15, swap: 42, 53, 3, 5, 2, 15, 78

Pass 2

• 42 < 53, no swap
• 53 > 3, swap: 42, 3, 53, 5, 2, 15, 78
• 53 > 5, swap: 42, 3, 5, 53, 2, 15, 78
• 53 > 2, swap: 42, 3, 5, 2, 53, 15, 78
• 53 > 15, swap: 42, 3, 5, 2, 15, 53, 78

Pass 3

• 42 > 3, swap: 3, 42, 5, 2, 15, 53, 78
• 42 > 5, swap: 3, 5, 42, 2, 15, 53, 78
• 42 > 2, swap: 3, 5, 2, 42, 15, 53, 78
• 42 > 15, swap: 3, 5, 2, 15, 42, 53, 78

Pass 4

• 3 < 5, no swap
• 5 > 2, swap: 3, 2, 5, 15, 42, 53, 78
• 5 < 15, 15 < 42: no swap

Result: 3, 2, 5, 15, 42, 53, 78

Pass 5

• 3 > 2, swap: 2, 3, 5, 15, 42, 53, 78
• remaining comparisons need no swap.

Pass 6: no swap occurs, so the array is sorted.

Sorted array: 2, 3, 5, 15, 42, 53, 78

Time complexity is $O(n^2)$ in the worst and average case; with a "swapped" flag the best case is $O(n)$.

Hashing

Hashing is a technique to store and retrieve data directly using a key, by converting the key into an array index with a hash function. It gives average search, insertion and deletion time of $O(1)$.

Hash table

A hash table is an array of $m$ slots (buckets) in which each record is stored at the index computed from its key. The index of key $k$ is $h(k)$.

Hash function

A hash function $h$ maps a key to an index in $0,\dots,m-1$. A good hash function is quick to compute, distributes keys uniformly and minimises collisions. Common methods:

• Division method: $h(k) = k \bmod m$ (choose $m$ prime).
• Mid-square method: square the key and take the middle digits.
• Folding method: split the key into parts and add them, then take mod $m$.

Example. Table size $m = 10$, hash function $h(k) = k \bmod 10$. Insert keys 25, 42, 17, 38.

Table: index 2 holds 42, index 5 holds 25, index 7 holds 17, index 8 holds 38. To search 17, compute $h(17)=7$ and check index 7 directly.

If a key such as 35 is inserted, $h(35)=5$ is already occupied by 25. This is a collision, which is handled by collision resolution techniques such as chaining or open addressing.

Minimum spanning tree (MST)

A spanning tree of a connected, undirected graph with $V$ vertices is a subgraph that includes all vertices, is connected and has no cycle; it has exactly $V - 1$ edges. For a weighted graph, the minimum spanning tree is the spanning tree whose total edge weight is the smallest. Applications: laying cable, road, pipeline and network design.

Two standard algorithms are Kruskal's and Prim's.

Kruskal's algorithm (greedy on edges)

1. Sort all edges in non-decreasing order of weight.
2. Take the next smallest edge; add it if it does not form a cycle with the edges already chosen (check using union-find), else discard it.
3. Stop when $V - 1$ edges are chosen.

Prim's algorithm (greedy on vertices)

1. Start with any vertex in the tree.
2. Repeatedly choose the minimum-weight edge connecting a tree vertex to a vertex outside the tree and add it.
3. Stop when all vertices are in the tree.

Example. Edges: A-B = 4, A-C = 2, B-C = 1, B-D = 5, C-D = 8, C-E = 10, D-E = 2.

Kruskal: sorted edges B-C (1), A-C (2), D-E (2), A-B (4), B-D (5), C-D (8), C-E (10).

Four edges ($V - 1 = 4$) are chosen: B-C, A-C, D-E, B-D. Total weight $= 1 + 2 + 2 + 5 = 10$.

Complexity: Kruskal $O(E \log E)$; Prim $O(V^2)$ with an array, or $O(E\log V)$ with a heap.

(a) Tail recursion

A recursive function is tail recursive if the recursive call is the very last action performed in the function: nothing remains to be done after the call returns (no multiplication, addition etc. on its result). Because the current stack frame is not needed after the call, a compiler can reuse it (tail-call optimisation), converting the recursion into a loop and using $O(1)$ stack space.

Non-tail recursive factorial (multiplication happens after the call):

int fact(int n) {
    if (n <= 1) return 1;
    return n * fact(n - 1);
}

Tail recursive factorial (using an accumulator):

int fact(int n, int acc) {
    if (n <= 1) return acc;
    return fact(n - 1, n * acc);   /* last action is the call */
}

The tail version is called as fact(5, 1). Tail recursion is easy to convert to iteration and avoids stack overflow for deep recursion.

(b) Collision resolution techniques

A collision occurs when two different keys hash to the same index. The two main families of resolution are:

1. Separate chaining (open hashing). Each table slot holds a linked list of all keys that hash to that slot. A colliding key is simply added to the list. Example with $h(k)=k \bmod 10$: keys 25 and 35 both go to slot 5, so slot 5 holds the list 25 -> 35. Table never overflows and deletion is easy, but extra memory is used for pointers and search can degrade to $O(n)$ if lists grow long.

2. Open addressing (closed hashing). All keys are stored inside the table itself; on a collision another empty slot is searched by a probe sequence.

• Linear probing: try $(h(k)+i) \bmod m$ for $i = 0,1,2,\dots$. Simple, but causes primary clustering.
• Quadratic probing: try $(h(k)+i^2) \bmod m$. Reduces primary clustering but causes secondary clustering.
• Double hashing: try $(h_1(k)+i\,h_2(k)) \bmod m$ using a second hash function. Gives the best distribution.

Example (linear probing, $m=10$): insert 25 at index 5; inserting 35 finds index 5 occupied, so it goes to index 6.

Another approach is rehashing, i.e. growing the table and re-inserting all keys when the load factor becomes high.

Queue

A queue is a linear data structure in which elements are inserted at one end (rear) and deleted from the other end (front). It follows FIFO (First In First Out): the element inserted first is removed first, like people waiting in a line at a ticket counter.

Applications of queue

• CPU process scheduling and job scheduling.
• Printer spooling and other I/O buffering.
• Breadth-first traversal of graphs and trees.
• Handling requests in web servers and call centres.
• Simulation of real-life waiting lines (bank, traffic).
• Data transfer between asynchronous processes (keyboard buffer, pipes).

Queue operations

• enqueue(x): add $x$ at the rear (overflow if full).
• dequeue(): remove and return the front element (underflow if empty).
• front(): look at the front element without removing it.
• isEmpty(), isFull().

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

void enqueue(int x) {
    if (rear == MAX - 1) printf("Overflow");
    else q[++rear] = x;
}
int dequeue() {
    if (front > rear) { printf("Underflow"); return -1; }
    return q[front++];
}

Example. Start with an empty queue.

Each operation takes $O(1)$ time.

Circular linked list

In a circular linked list the pointer of the last node points back to the first node instead of NULL, so the nodes form a ring. It can be singly or doubly linked. Any node can be a starting point, and the whole list can be traversed from any node. It is useful for round-robin scheduling and for implementing circular queues.

Example: with nodes 10, 20, 30, the links are 10 -> 20 -> 30 -> back to 10. An empty list has head == NULL; a one-node list has head->next == head.

Operations on a singly linked list

struct node { int data; struct node *next; };
struct node *head = NULL;

1. Traversal

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

2. Insertion

At the beginning:

void insertBeg(int x) {
    struct node *n = malloc(sizeof(struct node));
    n->data = x; n->next = head; head = n;
}

At the end:

void insertEnd(int x) {
    struct node *n = malloc(sizeof(struct node)), *t = head;
    n->data = x; n->next = NULL;
    if (head == NULL) { head = n; return; }
    while (t->next != NULL) t = t->next;
    t->next = n;
}

After a given node p: n->next = p->next; p->next = n;

3. Deletion

First node:

void delBeg() {
    if (head == NULL) return;
    struct node *t = head; head = head->next; free(t);
}

A node with value $x$:

void delValue(int x) {
    struct node *t = head, *prev = NULL;
    while (t != NULL && t->data != x) { prev = t; t = t->next; }
    if (t == NULL) return;              /* not found */
    if (prev == NULL) head = t->next;   /* first node */
    else prev->next = t->next;
    free(t);
}

4. Search

struct node *search(int x) {
    for (struct node *t = head; t != NULL; t = t->next)
        if (t->data == x) return t;
    return NULL;
}

Insertion/deletion at the beginning take $O(1)$; at the end, search and general deletion take $O(n)$.

Binary search tree (BST)

A binary search tree 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 greater (duplicates are not allowed). An inorder traversal of a BST gives the keys in sorted order. Search, insertion and deletion take $O(h)$ time, where $h$ is the height ($O(\log n)$ for a balanced tree, $O(n)$ for a skewed one).

Program

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

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;
}

struct node *minNode(struct node *t) {
    while (t->left != NULL) t = t->left;
    return t;
}

/* deletion */
struct node *delete(struct node *root, int k) {
    if (root == NULL) return NULL;
    if (k < root->key)
        root->left = delete(root->left, k);
    else if (k > root->key)
        root->right = delete(root->right, k);
    else {
        if (root->left == NULL) {            /* 0 or 1 child (right) */
            struct node *t = root->right;
            free(root);
            return t;
        }
        if (root->right == NULL) {           /* 1 child (left) */
            struct node *t = root->left;
            free(root);
            return t;
        }
        struct node *s = minNode(root->right);   /* inorder successor */
        root->key = s->key;
        root->right = delete(root->right, s->key);
    }
    return root;
}

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

int main() {
    struct node *root = NULL;
    int a[] = {50, 30, 70, 20, 40, 60, 80};
    for (int i = 0; i < 7; i++) root = insert(root, a[i]);
    inorder(root);  printf("\n");      /* 20 30 40 50 60 70 80 */
    root = delete(root, 20);           /* leaf */
    root = delete(root, 30);           /* one child */
    root = delete(root, 50);           /* two children */
    inorder(root);  printf("\n");      /* 40 60 70 80 */
    return 0;
}

Explanation

Insertion: move left or right by comparing the key with the node until a NULL position is reached, and attach the new node there.

Deletion has three cases:

1. Node is a leaf: remove it.
2. Node has one child: replace the node by its child.
3. Node has two children: copy the inorder successor (smallest key of the right subtree) into the node, then delete that successor from the right subtree.

In the sample run, deleting 20 (leaf), then 30 (one child, 40 takes its place), then 50 (two children, replaced by 60) leaves the inorder sequence 40 60 70 80.

Complexity of algorithms

The complexity of an algorithm measures the resources it needs as a function of the input size $n$. There are two kinds:

• Time complexity: the number of basic steps (comparisons, assignments, arithmetic operations) executed.
• Space complexity: the amount of memory needed (input plus auxiliary variables, stack).

How to find it

1. Choose the input size $n$ and decide the basic operation to count.
2. Count how many times each statement is executed, as a function of $n$.
3. Add the counts to get $T(n)$.
4. Keep only the dominant (highest-order) term and drop constants; express using asymptotic notation.

Rules of thumb: a simple statement is $O(1)$; a loop running $n$ times is $O(n)$; nested loops multiply, e.g. two nested loops to $n$ give $O(n^2)$; a loop where the variable is halved or doubled each time is $O(\log n)$; consecutive blocks add, so the larger one dominates; for recursion, write a recurrence such as $T(n)=2T(n/2)+n$ and solve it (here $O(n\log n)$).

Example.

for (i = 0; i < n; i++)        /* n+1 tests */
    for (j = 0; j < n; j++)    /* n(n+1) tests */
        sum = sum + a[i][j];   /* n*n times */

$T(n) \approx n^2 + \text{lower terms}$, so the time complexity is $O(n^2)$.

Asymptotic notations

• Big-O $O(g(n))$: upper bound (worst case).
• Big-Omega $\Omega(g(n))$: lower bound (best case).
• Big-Theta $\Theta(g(n))$: tight bound.

Algorithms are analysed for best, average and worst cases; for example linear search is $O(1)$ best case and $O(n)$ worst case.

Postfix expression ABCD-x+ with A = 5, B = 4, C = 3, D = 7 becomes 5 4 3 7 - x +.

Scan left to right; push operands; for an operator pop the right operand first, then the left operand.

The stack contains one value, so the result is -11.

This equals the infix expression $A + B \times (C - D) = 5 + 4\times(3-7) = 5 - 16 = -11$.

Priority queue

A priority queue is a queue in which every element has a priority, and the element with the highest priority (or lowest, depending on the convention) is served first, regardless of the order of arrival. Elements of equal priority are served in FIFO order.

Operations: insert(x, priority) adds an element, deleteMax()/deleteMin() removes the element with the highest/lowest priority, and peek() reads it. It can be implemented with an ordered or unordered array/list ($O(n)$ for insert or delete) or, most efficiently, with a binary heap ($O(\log n)$ for both).

Example: insert (task A, 2), (task B, 5), (task C, 1). With the largest number meaning highest priority, the removal order is B, A, C, whatever the insertion order.

Why it is needed

An ordinary queue serves strictly in arrival order, which is unsuitable when some items are more urgent. Priority queues are required in:

• CPU scheduling, where system processes get priority over user processes.
• Emergency handling, e.g. hospital patients by severity.
• Dijkstra's shortest path and Prim's MST algorithms (pick the minimum-distance vertex).
• Huffman coding (repeatedly take the two lowest-frequency nodes).
• Network packet scheduling and event-driven simulation.

Recursive program for the nth Fibonacci number

The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, ... defined by

$F(n)=\begin{cases} n & n = 0 \text{ or } 1\\ F(n-1)+F(n-2) & n \ge 2\end{cases}$

#include <stdio.h>

int fib(int n) {
    if (n == 0 || n == 1)      /* base cases */
        return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    int n;
    printf("Enter n: ");
    scanf("%d", &n);
    printf("Fibonacci(%d) = %d\n", n, fib(n));
    return 0;
}

For $n = 5$: $F(5)=F(4)+F(3)=3+2=5$. The sequence is 0, 1, 1, 2, 3, 5, so the 5th term (counting from $F(0)=0$) is 5.

This version recomputes the same values many times, so its time complexity is exponential, about $O(2^n)$, while stack depth is $O(n)$. It can be improved with memoisation or iteration to $O(n)$.

Array implementation of a list

A list is an ordered collection of elements $a_1, a_2, \dots, a_n$. In the array (static/sequential) implementation the elements are stored in consecutive memory locations of an array, and a variable n (or last) records the current number of elements. The $i$-th element is at index $i-1$ and can be reached in $O(1)$ time.

#define MAX 100
int list[MAX];
int n = 0;                       /* number of elements */

Insertion at position $pos$ (0-based): check that the array is not full, shift elements from $pos$ to the end one place to the right, place the new item, and increase n.

void insert(int pos, int x) {
    if (n == MAX) { printf("List full"); return; }
    for (int i = n - 1; i >= pos; i--)
        list[i + 1] = list[i];
    list[pos] = x;
    n++;
}

Deletion at position $pos$: shift elements after $pos$ one place to the left and decrease n.

void delete(int pos) {
    if (pos < 0 || pos >= n) { printf("Invalid"); return; }
    for (int i = pos; i < n - 1; i++)
        list[i] = list[i + 1];
    n--;
}

Traversal and search scan the array from index 0 to $n-1$, taking $O(n)$.

Complexity: access $O(1)$; insertion and deletion $O(n)$ because of shifting (at the end, $O(1)$).

Advantages: simple, fast random access, no pointer overhead. Disadvantages: fixed maximum size, wasted space if not full, and costly insertions and deletions.

Selection sort (descending order)

In each pass, find the largest element in the unsorted part and swap it with the first element of that part.

Array: 4, 71, 32, 19, 61, 2, -5

The last element -5 is then automatically in place.

Sorted array in descending order: 71, 61, 32, 19, 4, 2, -5

Number of comparisons is $n(n-1)/2 = 21$; time complexity $O(n^2)$ in all cases.

Sequential (linear) search

Sequential search examines the elements of a list one by one from the first, comparing each with the key, until a match is found or the list ends.

#include <stdio.h>

int seqSearch(int a[], int n, int key) {
    for (int i = 0; i < n; i++)
        if (a[i] == key)
            return i;        /* found at index i */
    return -1;               /* not found */
}

int main() {
    int a[100], n, key, i, pos;
    printf("Enter number of elements: ");
    scanf("%d", &n);
    printf("Enter %d elements: ", n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("Enter element to search: ");
    scanf("%d", &key);

    pos = seqSearch(a, n, key);
    if (pos == -1)
        printf("%d not found\n", key);
    else
        printf("%d found at position %d\n", key, pos + 1);
    return 0;
}

Complexity: best case $O(1)$ (key is first), worst and average case $O(n)$. It does not need the list to be sorted, and works for arrays and linked lists.

Graph traversal

Graph traversal means visiting every vertex of a graph exactly once in a systematic way, starting from a given source vertex. A visited array is used so that a vertex is not processed twice (graphs may contain cycles). The two standard methods are breadth-first search and depth-first search.

1. Breadth-First Search (BFS)

Visits all vertices at distance 1 from the source, then distance 2, and so on, using a queue.

1. Mark the source visited and enqueue it.
2. Dequeue a vertex $u$, process it, and enqueue all its unvisited neighbours (marking them visited).
3. Repeat until the queue is empty.

2. Depth-First Search (DFS)

Goes as deep as possible along a path before backtracking, using a stack (or recursion).

1. Mark the source visited and push it.
2. Visit an unvisited neighbour of the top vertex and push it; if there is none, pop (backtrack).
3. Repeat until the stack is empty.

Example. Edges: A-B, A-C, B-D, C-D, D-E. Start at A (neighbours taken alphabetically).

• BFS: A, B, C, D, E
• DFS: A, B, D, C, E (A to B to D, then D's unvisited neighbour C, then back to D to E)

Both take $O(V+E)$ time with an adjacency list. Uses: finding connected components, shortest path in unweighted graphs (BFS), cycle detection, topological sorting (DFS), and solving mazes.

(a) Divide and conquer sorting

Divide and conquer solves a problem in three steps: divide it into smaller subproblems, conquer them by solving recursively (a very small problem is solved directly), and combine the sub-solutions into the final answer. Sorting algorithms based on it are merge sort and quick sort.

Merge sort: divide the array into two halves, sort each half recursively, then merge the two sorted halves into one sorted array. Work is in the combine step. Recurrence $T(n)=2T(n/2)+O(n)$ gives $O(n\log n)$ in all cases, with $O(n)$ extra space; it is stable.

Quick sort: choose a pivot, partition the array so that smaller elements are on its left and larger elements on its right, then sort both parts recursively. Work is in the divide step; no combine step is needed. Average time $O(n\log n)$, worst case $O(n^2)$ (bad pivots), in-place.

(b) AVL tree

An AVL tree (Adelson-Velsky and Landis) is a self-balancing binary search tree in which, for every node, the heights of the left and right subtrees differ by at most 1. The balance factor of a node is

$BF = h(\text{left}) - h(\text{right}) \in \{-1, 0, 1\}.$

After an insertion or deletion, if some node gets $|BF| = 2$, the tree is rebalanced by rotations:

• LL case (inserted in left subtree of left child): single right rotation.
• RR case (right of right child): single left rotation.
• LR case (right of left child): left rotation on the child, then right rotation.
• RL case (left of right child): right rotation on the child, then left rotation.

Example: inserting 10, 20, 30 in order gives a right-skewed tree with $BF(10) = -2$ (RR case); a left rotation at 10 makes 20 the root with children 10 and 30.

An AVL tree with $n$ nodes has height $O(\log n)$, so search, insertion and deletion all take $O(\log n)$ time, unlike an ordinary BST which can degrade to $O(n)$.

Why balancing is needed. A binary search tree (BST) gives search, insert and delete in $O(h)$, where $h$ is the height. The shape of the tree depends on the order of insertion. If keys arrive in sorted order the BST degenerates into a linked list with $h = n$, so every operation costs $O(n)$. A balanced tree keeps $h = O(\log n)$, so all operations stay $O(\log n)$.

Example. Insert 10, 20, 30, 40, 50 into an ordinary BST. Each key becomes the right child of the previous one, giving a chain of height 5. Searching 50 needs 5 comparisons, and for $n = 10^6$ keys it would need $10^6$. If the tree is kept balanced (an AVL tree), the same 5 keys form a tree of height 3 (root 20, children 10 and 40, and 30, 50 under 40), and for $n = 10^6$ at most about 20 comparisons are needed.

An AVL tree is a BST in which, for every node, the balance factor $BF = h(\text{left}) - h(\text{right}) \in \{-1, 0, 1\}$. After an insertion that makes some node's BF become $\pm 2$, the tree is repaired by rotations (LL, RR, LR, RL).

Construction of the AVL tree for 24, 12, 8, 15, 35, 30, 57, 40, 45, 78.

1. Insert 24: root 24.
2. Insert 12: left child of 24.
3. Insert 8: left of 12. Node 24 has BF $= +2$ (LL case). Right rotation at 24 gives root 12 with children 8 and 24.
4. Insert 15: goes to the left of 24. Tree: 12 (8, 24(15, -)). Balanced.
5. Insert 35: right of 24. Tree: 12 (8, 24(15, 35)). Balanced.
6. Insert 30: left of 35. Node 12 now has BF $= 1 - 3 = -2$ (RR case, since 24 is right-heavy). Left rotation at 12 gives root 24 with left subtree 12(8, 15) and right subtree 35(30, -).
7. Insert 57: right of 35. Balanced: 35(30, 57).
8. Insert 40: left of 57. Tree: 24 ( 12(8,15), 35(30, 57(40,-)) ). Balanced.
9. Insert 45: right of 40. Node 57 has BF $= +2$ and its left child 40 is right-heavy (LR case). Left rotation at 40 then right rotation at 57 makes 45 the subtree root with children 40 and 57. Now 35(30, 45(40, 57)).
10. Insert 78: right of 57. Node 35 has BF $= 1 - 3 = -2$ and its right child 45 is right-heavy (RR case). Left rotation at 35 makes 45 the subtree root with left child 35(30, 40) and right child 57(-, 78).

Final AVL tree

              24
            /    \
          12      45
         /  \    /   \
        8   15  35    57
               /  \     \
              30  40     78

Check: 24's left subtree has height 2 and right subtree has height 3 (BF $= -1$); 45 has two subtrees of height 2 (BF $= 0$); every other node has $|BF| \le 1$. In-order traversal gives 8, 12, 15, 24, 30, 35, 40, 45, 57, 78, which is sorted, so the BST property holds.

Recursion and the stack. When a function calls itself, each call needs its own parameters, local variables and return address. The system keeps these in an activation record (stack frame) pushed onto the call stack. The most recent call must finish first, which is exactly LIFO order. When the base case is reached the frames are popped one by one, and each returned value is used to complete the pending computation of the caller. So the stack stores the intermediate (pending) results.

Example: factorial.

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

For fact(4):

• Calling phase (push): fact(4) waits for fact(3), which waits for fact(2), which waits for fact(1). The stack holds frames n=4, 3, 2, 1 (top is n=1).
• fact(1) returns 1 and its frame is popped.
• Returning phase (pop): fact(2) computes $2 \times 1 = 2$, fact(3) computes $3 \times 2 = 6$, fact(4) computes $4 \times 6 = 24$.

Infix to postfix: A + B - (C * D / E + F) - G * H

Rules: operands go to output; an operator pops operators of higher or equal precedence (left associative) before being pushed; ( is pushed; ) pops until (.

Postfix expression: $A\,B\,+\,C\,D\,*\,E\,/\,F\,+\,-\,G\,H\,*\,-$

Doubly linked list node.

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

Insertion at the k-th position (positions start at 1; head is the first node).

1. Create a new node n and store the data.
2. If $k = 1$: n->next = head; n->prev = NULL; if head != NULL set head->prev = n; then head = n.
3. Otherwise move a pointer p to the $(k-1)$-th node. If the list is shorter, report an invalid position.
4. Set n->next = p->next; n->prev = p;
5. If p->next != NULL, set p->next->prev = n.
6. Set p->next = n.

struct node *insertK(struct node *head, int x, int k) {
    struct node *n = malloc(sizeof(struct node)), *p = head;
    n->data = x;
    if (k == 1) {
        n->prev = NULL; n->next = head;
        if (head) head->prev = n;
        return n;
    }
    for (int i = 1; i < k - 1 && p; i++) p = p->next;
    if (!p) { free(n); printf("Invalid position\n"); return head; }
    n->next = p->next; n->prev = p;
    if (p->next) p->next->prev = n;
    p->next = n;
    return head;
}

Deletion of the k-th node.

1. If the list is empty, report underflow.
2. Move a pointer p to the $k$-th node; if it does not exist, report an invalid position.
3. If p->prev != NULL, set p->prev->next = p->next; otherwise (deleting the first node) set head = p->next.
4. If p->next != NULL, set p->next->prev = p->prev.
5. free(p).

struct node *deleteK(struct node *head, int k) {
    struct node *p = head;
    for (int i = 1; i < k && p; i++) p = p->next;
    if (!p) { printf("Invalid position\n"); return head; }
    if (p->prev) p->prev->next = p->next; else head = p->next;
    if (p->next) p->next->prev = p->prev;
    free(p);
    return head;
}

Both operations take $O(k)$ time for the traversal, and the pointer changes themselves take $O(1)$.

Stack using a linked list. A stack is LIFO, so the head of a singly linked list is used as the top. Both operations then work at the head and take $O(1)$.

• Push: create a node, set new->next = top, then top = new.
• Pop: if top == NULL report underflow; else save t = top, set top = top->next, return t->data, and free(t).
• Stack empty when top == NULL. There is no overflow except heap exhaustion, and the size is dynamic.

Queue using a linked list. A queue is FIFO, so two pointers are kept: front (delete end) and rear (insert end).

• Enqueue: create a node with next = NULL. If the queue is empty, set front = rear = new; otherwise rear->next = new; rear = new.
• Dequeue: if front == NULL report underflow; else t = front; front = front->next; if front becomes NULL also set rear = NULL; return the data and free(t).
• Both operations take $O(1)$ time and the queue never becomes "full" while memory is available.

Shell sort sorts elements that are a gap apart using insertion sort, and reduces the gap until it is 1. For $n = 10$ use gaps 5, 2, 1.

Initial array: 82, 73, 12, 39, 26, 88, 2, 9, 60, 41

Gap = 5. Compare the pairs (index 0, 5), (1, 6), (2, 7), (3, 8), (4, 9):

• (82, 88): in order.
• (73, 2): swap.
• (12, 9): swap.
• (39, 60): in order.
• (26, 41): in order.

Result: 82, 2, 9, 39, 26, 88, 73, 12, 60, 41

Gap = 2. Sort the two interleaved sub-lists by insertion sort.

• Even positions: 82, 9, 26, 73, 60 sorted gives 9, 26, 60, 73, 82.
• Odd positions: 2, 39, 88, 12, 41 sorted gives 2, 12, 39, 41, 88.

Result: 9, 2, 26, 12, 60, 39, 73, 41, 82, 88

Gap = 1. Ordinary insertion sort on the nearly sorted array: 2 moves before 9; 12 moves before 26; 39 moves before 60; 41 moves before 60; the rest are already in place.

Sorted array: 2, 9, 12, 26, 39, 41, 60, 73, 82, 88

Need for asymptotic notation. The exact running time of an algorithm depends on the machine, compiler, language and input, so it is hard to compare algorithms by measured time. Asymptotic notation describes how the running time (or space) grows as the input size $n \to \infty$, ignoring constants and lower-order terms. It lets us compare algorithms independently of hardware, and predict how they behave for large inputs. For example, $3n^2 + 5n + 7$ is simply described as $O(n^2)$.

Big O notation (upper bound). $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that

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

So $g(n)$ is an asymptotic upper bound on $f(n)$; it is used to state the worst-case growth of an algorithm.

Curve. For $n < n_0$, $f(n)$ may lie above or below $c\,g(n)$. From $n_0$ onward, the curve of $c\,g(n)$ stays above the curve of $f(n)$:

 time
  |                       c*g(n)
  |                     /
  |                   /   ..... f(n)
  |                 / ....
  |               /..
  |             /.
  |           /.
  |         /.
  |_______/_._________________________ n
                   n0

Example. $f(n) = 3n + 2$. Choose $c = 4$, then $3n + 2 \le 4n$ for all $n \ge 2$, so $f(n) = O(n)$ with $n_0 = 2$ and $c = 4$.

Queue. A queue is a linear data structure in which insertion takes place at one end (rear) and deletion takes place at the other end (front), following the FIFO (First In First Out) principle. The main operations are enqueue (insert), dequeue (delete), and checking empty/full.

Circular queue. In a linear array queue, once rear reaches the last index no new element can be inserted even if free space exists at the front after dequeues. In a circular queue the array is treated as a ring: the position after the last index is index 0, so freed space is reused. Indices move using modulo arithmetic: $\text{next} = (i + 1) \bmod N$.

Initially front = rear = -1.

Enqueue(x):

1. If (rear + 1) % N == front, the queue is full: report overflow.
2. If the queue is empty (front == -1), set front = 0.
3. Set rear = (rear + 1) % N.
4. Set Q[rear] = x.

Dequeue():

1. If front == -1, the queue is empty: report underflow.
2. Set x = Q[front].
3. If front == rear, the queue had one element, so set front = rear = -1.
4. Otherwise front = (front + 1) % N.
5. Return x.

void enqueue(int x) {
    if ((rear + 1) % N == front) { printf("Overflow\n"); return; }
    if (front == -1) front = 0;
    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;
}

Both operations take $O(1)$ time. With this convention all $N$ cells can be used.

Binary search works on a sorted array. It compares the key with the middle element and discards half of the array each time, so it runs in $O(\log n)$.

#include <stdio.h>

int binarySearch(int a[], int n, int key) {
    int low = 0, high = n - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == key)
            return mid;              /* found */
        else if (key < a[mid])
            high = mid - 1;          /* search left half */
        else
            low = mid + 1;           /* search right half */
    }
    return -1;                       /* not found */
}

int main() {
    int a[100], n, key, i, pos;
    printf("Enter number of elements: ");
    scanf("%d", &n);
    printf("Enter %d elements in ascending order:\n", n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);
    printf("Enter element to search: ");
    scanf("%d", &key);
    pos = binarySearch(a, n, key);
    if (pos == -1)
        printf("Element not found\n");
    else
        printf("Element found at position %d\n", pos + 1);
    return 0;
}

Table size $m = 5$ (slots 0 to 4), $h(x) = x \bmod 5$. Keys: 0, 1, 2, 4, 5, 7.

Note that there are 6 keys but only 5 slots, so one key cannot be stored unless the table is enlarged.

Initial hash values: $h(0)=0,\ h(1)=1,\ h(2)=2,\ h(4)=4,\ h(5)=0,\ h(7)=2$.

(a) Linear probing: $h(x, i) = (h(x) + i) \bmod 5$.

• 0 goes to slot 0; 1 to slot 1; 2 to slot 2; 4 to slot 4.
• 5: $h = 0$ is occupied, try 1 (occupied), 2 (occupied), 3 (free), so 5 goes to slot 3.
• 7: $h = 2$ is occupied, then 3, 4, 0, 1 are all occupied. The table is full, so 7 cannot be inserted (overflow; the table must be resized, for example to size 7 or 11 and rehashed).

(b) Double hashing: $h(x, i) = (h_1(x) + i \cdot h_2(x)) \bmod 5$, with $h_1(x) = x \bmod 5$ and the second hash $h_2(x) = 3 - (x \bmod 3)$ (a value from 1 to 3).

• 0, 1, 2, 4 go to slots 0, 1, 2, 4 without collision.
• 5: $h_1 = 0$, $h_2 = 3 - (5 \bmod 3) = 1$. Probes: slot 0 (occupied), slot 1 (occupied), slot 2 (occupied), slot 3 (free). So 5 goes to slot 3.
• 7: $h_1 = 2$, $h_2 = 3 - (7 \bmod 3) = 2$. Probes: slot 2, slot 4, slot 1, slot 3, slot 0, all occupied. The table is full, so 7 cannot be placed (overflow).

Both methods place 0, 1, 2, 5, 4 in the same slots here, and both fail for 7 because five keys already fill the table. Double hashing generally spreads keys better, since the probe step depends on the key and so avoids primary clustering.