Data Structures and Algorithms

Hashing is a technique that maps a key to an index of a table (hash table) by a hash function, for example $h(k) = k \bmod m$, so that insertion, search and deletion take $O(1)$ time on average. When two keys map to the same index a collision occurs, and a collision resolution technique is needed.

Types of collision resolution

1. Separate chaining (open hashing). Each slot holds a linked list of all keys that hash to it. Keys 15, 25, 35 with $m = 10$ all go to index 5 and form the chain $15 \to 25 \to 35$.

2. Open addressing (closed hashing). All keys are stored in the table itself; on collision another empty slot is found by probing.

Example: $m = 10$, $h(k) = k \bmod 10$, keys 23, 43, 13, 27 (23, 43, 13 all hash to 3, and 27 to 7).

• Linear probing: try $(h(k) + i) \bmod m$ for $i = 0, 1, 2, \dots$. 23 at index 3; 43 at 4; 13 at 5; 27 at 7. Drawback: primary clustering.
• Quadratic probing: try $(h(k) + i^2) \bmod m$. 23 at 3; 43 goes to $3+1 = 4$; 13: index 4 is full, so $3 + 4 = 7$; 27: index 7 is full, so $7 + 1 = 8$. Reduces primary clustering but may cause secondary clustering.
• Double hashing: try $(h_1(k) + i \cdot h_2(k)) \bmod m$ with, say, $h_2(k) = 7 - (k \bmod 7)$. 23 at 3; 43: $h_2 = 6$, so $3 + 6 = 9$; 13: $h_2 = 1$, so $3 + 1 = 4$; 27 at 7. Gives the best distribution.

Other: rehashing (building a larger table when the load factor becomes high).

Chaining never overflows and handles deletion easily but uses extra pointer memory; open addressing saves memory but needs a load factor below 1 and careful deletion.

A data structure is a particular way of organising and storing data in memory so that it can be accessed and modified efficiently. It specifies the data items, the relationships between them and the operations allowed on them. Examples: array, stack, queue, linked list, tree, graph.

Infix to postfix using a stack

Expression: P + Q - (R * S / T + U) - V * W

Rules: an operand goes straight to the output; ( is pushed; on ) pop to the output until (; an operator first pops every stack operator of equal or higher precedence, then is pushed. At the end pop everything.

Postfix: PQ+RS*T/U+-VW*-

Binary search

Binary search finds a key in a sorted array by repeatedly comparing it with the middle element and discarding half of the remaining range.

BinarySearch(A, n, key)
1. low = 0, high = n - 1
2. while low <= high
3.     mid = (low + high) / 2
4.     if A[mid] == key  return mid
5.     else if key < A[mid]  high = mid - 1
6.     else  low = mid + 1
7. return -1        // not found

Each step halves the range, so the time is $O(\log n)$ (best case $O(1)$).

Hash table of size 10 with linear probing

Hash function: $h(k) = k \bmod 10$. On a collision try $(h(k)+i) \bmod 10$ for $i = 1, 2, \dots$

Final table:

Deterministic algorithm: at every step the next operation is uniquely defined, so for the same input it always follows the same sequence of steps and gives the same output. Examples: binary search, merge sort, Dijkstra's algorithm.

Non-deterministic algorithm: some steps allow several possible choices, and the algorithm is assumed to "guess" the correct choice (as if it could try all in parallel), so the same input may follow different execution paths. It uses operations such as choice(), failure() and success(). It is a theoretical model used to define the class NP (problems whose solution can be verified in polynomial time), e.g. searching, the travelling salesman decision problem.

Greedy algorithm

A greedy algorithm builds the solution step by step and at every step selects the choice that looks best at that moment (locally optimal), never reconsidering earlier choices, hoping to reach a globally optimal solution.

Features: a candidate set, a selection function, a feasibility check and an objective function. It is fast and simple, but gives an optimal answer only for problems having the greedy-choice property and optimal substructure.

Examples: Kruskal's and Prim's minimum spanning tree, Dijkstra's shortest path, Huffman coding, fractional knapsack, activity selection.

Example (coin change with Rs 1, 2, 5, 10 coins): to pay Rs 28, repeatedly take the largest coin that fits: 10 + 10 + 5 + 2 + 1, giving 5 coins, which is optimal for this coin system.

Constructing the BST from DATASTRUCTURE

Letters in order: D, A, T, A, S, T, R, U, C, T, U, R, E. A BST holds distinct keys, so repeated letters (A, T, U, R, T, U) are ignored after their first insertion. Rule: smaller goes left, larger goes right.

1. D is the root.
2. A < D, left of D.
3. T > D, right of D.
4. S: > D, < T, so left of T.
5. R: > D, < T, < S, so left of S.
6. U: > D, > T, so right of T.
7. C: < D, > A, so right of A.
8. E: > D, < T, < S, < R, so left of R.

            D
          /   \
         A     T
          \   / \
           C S   U
            /
           R
          /
         E

Preorder (Root, Left, Right): D A C T S R E U

Postorder (Left, Right, Root): C A E R S U T D

Circular queue: a queue in which the last position is logically connected back to the first position, so the array is treated as a circle. Elements are inserted at rear and removed from front, and both indices wrap around using modulo arithmetic:

$rear = (rear + 1) \bmod SIZE, \qquad front = (front + 1) \bmod SIZE$

Limitation of the linear queue: in an array-based linear queue, rear only moves forward. After some deletions the freed cells at the front can never be reused, so rear == SIZE - 1 reports "queue full" even though empty cells exist. Example: SIZE = 5, insert 5 items and delete 3. Only 2 items are present but no insertion is possible. The only remedy is shifting all elements, which costs $O(n)$.

How the circular queue overcomes it: when rear reaches the last index, the next insertion goes to index 0 if that cell is free, so every empty cell is reused. The queue is full only when all SIZE cells are occupied, that is when $(rear + 1) \bmod SIZE = front$ (one cell is often left unused to tell full from empty). It is empty when front == -1 (or front == rear in the sacrificed-cell version). Both enqueue and dequeue stay $O(1)$ and memory is used efficiently.

In the example above (SIZE = 5, 2 items remaining), the next insertions simply wrap to indices 0, 1, 2.

A singly linked list is a linear collection of nodes in which each node has a data field and one pointer next to the following node. A pointer head holds the first node, and the last node's next is NULL. Traversal is possible only in the forward direction.

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

Insert at the beginning

InsertBegin(head, item)
1. Create newnode; if memory not available, print "overflow" and stop
2. newnode->data = item
3. newnode->next = head
4. head = newnode

struct node* insertBegin(struct node *head, int item) {
    struct node *n = (struct node*)malloc(sizeof(struct node));
    n->data = item;
    n->next = head;
    return n;             /* new head */
}

Insert at the end

InsertEnd(head, item)
1. Create newnode; newnode->data = item; newnode->next = NULL
2. if head == NULL then head = newnode and stop
3. temp = head
4. while temp->next != NULL: temp = temp->next
5. temp->next = newnode

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

Insertion at the beginning takes $O(1)$; insertion at the end takes $O(n)$ because the list must be traversed (it is $O(1)$ if a tail pointer is kept).

AVL tree: a self-balancing binary search tree in which, for every node, the balance factor $BF = height(left) - height(right)$ is $-1$, $0$ or $+1$. When an insertion makes some node's BF become $\pm 2$, the tree is restored by a rotation (LL, RR, LR or RL), so the height stays $O(\log n)$ and search, insert and delete are all $O(\log n)$.

Construction for 4, 6, 12, 9, 5, 2, 13, 8, 3, 7, 11 (a tree is written as root(left, right)):

Final AVL tree

                 6
              /     \
            4         9
           / \       / \
          2   5     8   12
           \       /    / \
            3     7    11  13

Check: BF(6) = 3 - 3 = 0, BF(4) = 2 - 1 = 1, BF(9) = 2 - 2 = 0, BF(12) = 0, so every node is within $\pm 1$.

Stack: a linear data structure in which insertion (PUSH) and deletion (POP) are done at only one end, called the top. It follows the LIFO (Last In First Out) principle: the element inserted last is removed first. It is an ADT with operations push, pop, peek/top, isEmpty and isFull.

Applications of stack

• Function call management and recursion (call stack)
• Conversion of infix expressions to postfix or prefix
• Evaluation of postfix and prefix expressions
• Matching parentheses and syntax checking in compilers
• Reversing a string or list
• Undo/redo in editors and back button in browsers
• Depth first search of graphs and backtracking (maze, N-queens)
• Tower of Hanoi

Array implementation (stack[MAX], top = -1 initially)

PUSH(stack, item)
1. if top == MAX - 1
2.     print "Stack overflow" and stop
3. top = top + 1
4. stack[top] = item

POP(stack)
1. if top == -1
2.     print "Stack underflow" and stop
3. item = stack[top]
4. top = top - 1
5. return item

#define MAX 100
int stack[MAX], top = -1;

void push(int item) {
    if (top == MAX - 1) { printf("Stack overflow\n"); return; }
    stack[++top] = item;
}

int pop(void) {
    if (top == -1) { printf("Stack underflow\n"); return -1; }
    return stack[top--];
}

Both operations take $O(1)$ time.

Heap: a complete binary tree that satisfies the heap property. In a max-heap every parent is greater than or equal to its children (the root is the largest); in a min-heap every parent is less than or equal to its children (the root is the smallest). It is usually stored in an array, where the children of index $i$ are $2i+1$ and $2i+2$. Heaps are used for heap sort and priority queues.

Quick sort

Quick sort is a divide and conquer sorting method.

1. Choose a pivot (here the first element).
2. Partition: rearrange so that elements $\le$ pivot are on its left and elements $>$ pivot on its right; the pivot is then in its final position.
3. Recursively sort the left and right parts.

QuickSort(A, low, high)
1. if low < high
2.     p = Partition(A, low, high)
3.     QuickSort(A, low, p - 1)
4.     QuickSort(A, p + 1, high)

Partition(A, low, high)
1. pivot = A[low], i = low + 1, j = high
2. repeat
3.     while i <= high and A[i] <= pivot: i = i + 1
4.     while A[j] > pivot: j = j - 1
5.     if i < j swap A[i], A[j]
6. until i >= j
7. swap A[low], A[j]
8. return j

Complexity (Big-Oh)

Space is $O(\log n)$ for the recursion stack (average).

Trace for 8, 10, 5, 12, 14, 5, 7, 13

• Pivot 8: i stops at 10, j stops at 7, swap: 8 7 5 12 14 5 10 13. i stops at 12, j stops at the second 5, swap: 8 7 5 5 14 12 10 13. Now i (at 14) has crossed j (at 5), so swap pivot with A[j]: 5 7 5 8 14 12 10 13. Pivot 8 is fixed.
• Left part 5 7 5, pivot 5: i stops at 7, j stops at the last 5, swap: 5 5 7. Then pointers cross; pivot swaps with itself or the equal 5: 5 5 7.
• Right part 14 12 10 13, pivot 14: i runs off the end, j stops at 13 (13 is not greater than 14); swap pivot with 13: 13 12 10 14. 14 is fixed.
• Part 13 12 10, pivot 13: result 10 12 13.
• Part 10 12, pivot 10 already in place; 12 alone.

Combining: 5 5 7 8 10 12 13 14.

Sorted output: 5, 5, 7, 8, 10, 12, 13, 14

Graph: a non-linear data structure $G = (V, E)$ consisting of a set of vertices (nodes) $V$ and a set of edges $E$ connecting pairs of vertices. Edges may be directed or undirected, weighted or unweighted, and a graph may contain cycles.

Tree: a non-linear hierarchical data structure that is a connected graph without cycles. It has one special node, the root, and every other node has exactly one parent. A tree with $n$ nodes has $n-1$ edges. Every tree is a graph, but not every graph is a tree.

Example graph (undirected): vertices A, B, C, D, E, F with edges A-B, A-C, B-D, B-E, C-F, E-F.

Adjacency lists: A: B, C; B: A, D, E; C: A, F; D: B; E: B, F; F: C, E.

Breadth first traversal (BFS)

It visits all vertices at distance 1 from the start, then distance 2, and so on, using a queue.

BFS(start)
1. mark start visited; enqueue(start)
2. while queue not empty
3.     v = dequeue(); visit v
4.     for each unvisited neighbour w of v: mark w visited; enqueue(w)

Trace from A: queue [A] → visit A, add B, C → visit B, add D, E → visit C, add F → visit D → visit E → visit F.

BFS order: A, B, C, D, E, F. Time $O(V + E)$.

Depth first traversal (DFS)

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

DFS(v)
1. mark v visited; visit v
2. for each unvisited neighbour w of v: DFS(w)

Trace from A: A → B → D (dead end, backtrack to B) → E → F → C (A is already visited, backtrack all the way).

DFS order: A, B, D, E, F, C. Time $O(V + E)$.

BFS finds shortest paths in unweighted graphs; DFS is used for cycle detection, topological sorting and connected components.

(c) Counting number of key operations

Time complexity measures how the number of basic (key) operations grows with the input size $, independent of machine speed, so it is not measured in microseconds, kilobytes or statement count.

(d) 17

Evaluate the postfix expression using a stack: push 5, 7, 4; - gives $7-4=3$; * gives $5\times3=15$; push 8, 4; / gives $8/4=2$; + gives $15+2=17$.

(c) Left-Right-Root

In postorder traversal the left subtree is visited first, then the right subtree, and the root last.

(d) 15

The Tower of Hanoi with $n$ disks needs $2^n-1$ moves, so for 4 disks $2^4-1=15$.

(a) O(n)

For already sorted input each element is compared once with its predecessor and no shifting is needed, so the best case takes $n-1$ comparisons, which is $O(n)$.

(b) rear=(rear+1)%SIZE

The modulo makes rear wrap round to index 0 after the last index, which is what makes the queue circular.

(c) Circular

In a circular linked list the last node points back to the first node, so no node has a NULL pointer.

(a) Stack

DFS goes deep and then backtracks, which is last-in first-out behaviour, so it uses a stack (or the recursion call stack). BFS uses a queue.

(d) All non-leaf nodes with M-1 keys must have M number of children

In a B-tree of order $M$ an internal node with $k$ keys has $k+1$ children, so a node with $M-1$ keys has $M$ children. All leaves are at the same level, keys within a node are in ascending order, and a node needs at least $\lceil M/2 \rceil$ children (not $M$) except the root.

(c) Chaining

Division remainder, folding and mid-square are hash functions that compute an address from a key. Chaining is a collision resolution technique, not a hash function.

A data structure is a systematic way of organising, storing and managing data in a computer so that it can be used efficiently. It defines the data elements, how they are related, and the operations that can be applied to them. Data structures are classified as primitive (int, char, float) and non-primitive; non-primitive ones are linear (array, stack, queue, linked list) and non-linear (tree, graph).

Operations performed on a data structure

1. Traversing: visiting every element exactly once to process it, e.g. printing all items of an array or list.
2. Searching: finding the location of an element with a given key (linear search, binary search), or finding that it is absent.
3. Insertion: adding a new element at a given position, e.g. push into a stack, enqueue into a queue, adding a node to a list.
4. Deletion: removing an existing element, e.g. pop, dequeue, deleting a node.
5. Sorting: arranging the elements in ascending or descending order (bubble, insertion, quick, merge, heap sort).
6. Merging: combining two sorted structures into a single sorted structure.
7. Updating (modification): changing the value of an existing element.
8. Copying/Splitting and creating or destroying the structure are also performed in some cases.

For example, in an array A[5] = {3, 8, 1, 9, 4}: traversing prints all five values, searching 9 returns index 3, inserting 7 at index 2 shifts the following elements right, and deleting index 0 shifts the others left.

Greedy algorithm: an algorithm that builds a solution step by step, always choosing the option that looks best at that moment (locally optimal) without reconsidering earlier choices, in the hope of reaching the global optimum. It works when the problem has the greedy-choice property and optimal substructure. Examples: Kruskal's and Prim's MST, Dijkstra's algorithm, Huffman coding, fractional knapsack.

Heuristic algorithm: an algorithm that uses a rule of thumb or experience-based strategy to find a good, acceptable solution quickly, but without a guarantee that it is optimal or even always correct. It is used when an exact solution is too costly, e.g. the nearest-neighbour method for the travelling salesman problem, or the A* search heuristic.

Big-Oh notation

Big-Oh gives an asymptotic upper bound on the growth rate of an algorithm's running time (usually the worst case). We write $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that

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

Example: for $f(n) = 3n + 2$, take $c = 4$ and $n_0 = 2$: $3n + 2 \le 4n$ for $n \ge 2$, so $f(n) = O(n)$.

Constants and lower order terms are ignored. Common orders, from fastest to slowest growth: $O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$. Examples: binary search $O(\log n)$, linear search $O(n)$, bubble sort $O(n^2)$.

Circular queue: a queue implemented in an array in which the last position is treated as connected to the first, so after the last index the next position is index 0. Elements are added at rear and removed from front. This lets freed cells at the front be reused, which a linear queue cannot do.

Conditions (array Q[SIZE], initially front = -1, rear = -1):

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

Algorithm to insert an item

CQInsert(Q, SIZE, item)
1. if (rear + 1) % SIZE == front
2.     print "Queue overflow" and stop
3. if front == -1                 // first element
4.     front = 0, rear = 0
5. else
6.     rear = (rear + 1) % SIZE
7. Q[rear] = item

#define SIZE 5
int Q[SIZE], front = -1, rear = -1;

void enqueue(int item) {
    if ((rear + 1) % SIZE == front) {
        printf("Queue overflow\n");
        return;
    }
    if (front == -1)
        front = rear = 0;
    else
        rear = (rear + 1) % SIZE;
    Q[rear] = item;
}

The insertion takes $O(1)$ time. Example with SIZE = 5: if rear = 4 and front = 2, then $(4+1) \bmod 5 = 0 \ne 2$, so the queue is not full, and the new item is stored at index 0.

Difference between AVL tree and BST

Construction for 35, 56, 68, 65, 44, 41, 31, 49, 20 (the tree is written as root(left, right), $BF = h_{left} - h_{right}$):

Final AVL tree

                  56
                /    \
             41        68
            /  \      /
          31    44   65
         /  \     \
        20  35    49

Check: BF(31) = 0, BF(41) = 2 - 2 = 0, BF(44) = -1, BF(68) = 1, BF(56) = 3 - 2 = 1, so the tree is a valid AVL tree.

B-tree: a self-balancing multiway search tree, widely used in databases and file systems to keep data sorted on disk. A B-tree of order $m$ has these properties:

• Every node has at most $m$ children and at most $m-1$ keys.
• Every non-root internal node has at least $\lceil m/2 \rceil$ children; the root has at least 2 children (if it is not a leaf).
• A node with $k$ children holds $k-1$ keys in ascending order.
• All leaves are at the same level.

Search, insertion and deletion take $O(\log n)$ time.

Insertion rule (order 4): a node holds at most 3 keys. Insert the key into the proper leaf; if the leaf then has 4 keys, split it: the second key moves up to the parent, the first key stays in the left node and the remaining two keys form the right node. A split may propagate upward.

Construction for 6, 4, 22, 10, 2, 14, 3, 8, 11, 13, 5, 9 (tree written as [root] with its children):

Final B-tree of order 4

                       [ 6 ]
                /                \
           [ 3 ]                [ 10  13 ]
           /    \              /     |      \
        [ 2 ]  [ 4 5 ]     [ 8 9 ]  [ 11 ]  [ 14 22 ]

All leaves are at the same level, every node has at most 3 keys, and every internal node has one more child than keys.

Binary search is a searching technique for a sorted array. It repeatedly compares the key with the middle element and discards the half that cannot contain the key, so the search range halves at every step. It is a divide-and-conquer method with time complexity $O(\log n)$ (best case $O(1)$) and space $O(1)$ in the iterative form.

Algorithm (BinarySearch(A, n, key))

1. Set $low = 0$, $high = n-1$.
2. Repeat steps 3 to 5 while $low \le high$.
3. Set $mid = \lfloor (low + high)/2 \rfloor$.
4. If $A[mid] = key$, return $mid$ (found) and stop.
5. If $key < A[mid]$, set $high = mid - 1$; otherwise set $low = mid + 1$.
6. Return $-1$ (not found).

Example. $A = \{5, 12, 18, 23, 31, 40, 52\}$, key $= 31$.

C function

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

Graph. A graph $G = (V, E)$ is a non-linear data structure consisting of a finite set $V$ of vertices (nodes) and a set $E$ of edges, each edge joining a pair of vertices. A graph may be directed or undirected, and weighted if each edge carries a cost. It is used to model networks such as roads, computer networks and social connections.

Kruskal's algorithm builds a minimum spanning tree (MST) of a connected, weighted, undirected graph by the greedy method: always take the cheapest remaining edge that does not form a cycle.

Steps

1. Sort all edges in non-decreasing order of weight.
2. Start with a forest in which every vertex is its own tree.
3. Take the next smallest edge. If its end points are in different trees, add it to the MST and merge the trees; otherwise discard it (it would form a cycle).
4. Stop when $V-1$ edges have been chosen.

Complexity is $O(E \log E)$, dominated by sorting.

Example. Vertices A to F 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.

Five edges ($V - 1 = 5$) are chosen, so the algorithm stops. The MST edges are B-C, A-C, D-E, E-F, B-D and

$\text{cost} = 1 + 2 + 2 + 3 + 5 = 13.$

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

Applications of stack

• Conversion and evaluation of expressions (infix, postfix, prefix).
• Function calls and recursion (call stack).
• Undo/redo in editors and back button in browsers.
• Parenthesis matching and syntax checking in compilers.
• Reversing a string or list, and depth first search.

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

Rules: operands go straight to output; an operator pops operators of higher or equal precedence from the stack first; ( is pushed, and ) pops until (. Precedence: * and / above + and -.

Postfix: $AB+CD*E/-HI-*F*G+$

Evaluation with $A=4, B=2, C=4, D=3, E=8, F=2, G=3, H=5, I=1$. Scan left to right, pushing operands and applying each operator to the top two values.

Result of the expression $= 39$.

Doubly linked list. A doubly linked list is a linked list in which every node has three fields: prev (address of the previous node), data, and next (address of the next node). It can therefore be traversed in both directions. The prev of the first node and the next of the last node are NULL.

Difference from a circular linked list

(A list can also be both: a circular doubly linked list.)

Node and functions in C

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

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

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

Algorithm, add at beginning: create node N; set $N.prev = NULL$ and $N.next = head$; if the list is not empty set $head.prev = N$; set $head = N$.

Algorithm, add at end: create node N with $N.next = NULL$; if the list is empty, set $N.prev = NULL$ and $head = N$; otherwise move pointer T to the last node, set $T.next = N$ and $N.prev = T$.

Heap. A heap is a complete binary tree (usually stored in an array) that satisfies the heap-order property between each parent and its children. For array index $i$ (1-based) the children are at $2i$ and $2i+1$ and the parent at $\lfloor i/2 \rfloor$.

Heap sort (ascending) uses a max heap: build the heap, then repeatedly swap the root with the last element, reduce the heap size by one and restore the heap.

Data: 2, 9, 3, 12, 15, 8, 11 (array positions 1 to 7).

Build max heap (heapify from position 3 down to 1):

• Position 3 (3) with children 8, 11: swap with 11, giving 2, 9, 11, 12, 15, 8, 3.
• Position 2 (9) with children 12, 15: swap with 15, giving 2, 15, 11, 12, 9, 8, 3.
• Position 1 (2) with children 15, 11: swap with 15, then 2 sinks below 12, giving 15, 12, 11, 2, 9, 8, 3.

Sorting phase (the part after | is the sorted portion):

Sorted result: 2, 3, 8, 9, 11, 12, 15.

Data structure. A data structure is a particular way of organizing, storing and managing data in the memory of a computer so that it can be accessed and modified efficiently. It defines the data, the relationships among the data items, and the operations allowed on them. Examples: array, linked list, stack, queue, tree, graph, hash table.

Data structures are classified as primitive (int, char, float) and non-primitive; non-primitive ones are linear (array, list, stack, queue) or non-linear (tree, graph).

Importance

• Efficiency: the right structure reduces time and memory, for example searching a sorted array by binary search takes $O(\log n)$ against $O(n)$ for a linear scan.
• Organization of large data: helps to handle huge volumes of data (databases, file systems, search engines) in a systematic way.
• Reusability: a well-defined structure and its operations can be reused in many programs.
• Abstraction: users work with operations such as push, pop or insert without needing to know the internal implementation.
• Problem solving: many algorithms depend on a suitable structure, such as a stack for expression evaluation, a queue for scheduling, a graph for shortest routes, a tree for hierarchical data.
• Better program design: makes programs easier to understand, maintain and extend.

Algorithm: convert infix expression to postfix using a stack

Precedence (high to low): ^ (right associative), then * and /, then + and -. Operators of equal precedence associate left to right (except ^).

Input: infix expression $Q$ (token list). Output: postfix expression $P$.

1. Create an empty stack $S$ and an empty output $P$. Push ( onto $S$ and append ) to the end of $Q$.
2. Read the next token $x$ of $Q$ from left to right and repeat steps 3 to 6 until $S$ is empty.
3. If $x$ is an operand, append it to $P$.
4. If $x$ is (, push it onto $S$.
5. If $x$ is an operator:
   • while the top of $S$ is an operator whose precedence is higher than, or equal to, that of $x$ (for ^ only strictly higher), pop it and append it to $P$;
   • push $x$ onto $S$.
6. If $x$ is ):
   • pop operators from $S$ and append them to $P$ until ( is on top;
   • pop and discard (.
7. Exit; $P$ is the postfix expression.

Example. $A + B * C$ gives: A to output; + pushed; B to output; * has higher precedence than +, so it is pushed; C to output; at the end pop * then +. Postfix: $ABC*+$.

C function sketch

int prec(char c){ return c=='^'?3 : (c=='*'||c=='/')?2 : (c=='+'||c=='-')?1 : 0; }

void infixToPostfix(char in[], char post[]) {
    char st[100]; int top = -1, k = 0;
    for (int i = 0; in[i] != '\0'; i++) {
        char c = in[i];
        if (isalnum(c)) post[k++] = c;
        else if (c == '(') st[++top] = c;
        else if (c == ')') {
            while (top >= 0 && st[top] != '(') post[k++] = st[top--];
            top--;                       /* discard '(' */
        } else {
            while (top >= 0 && st[top] != '(' &&
                   (prec(st[top]) > prec(c) ||
                   (prec(st[top]) == prec(c) && c != '^')))
                post[k++] = st[top--];
            st[++top] = c;
        }
    }
    while (top >= 0) post[k++] = st[top--];
    post[k] = '\0';
}

The Fibonacci series is $0, 1, 1, 2, 3, 5, 8, \dots$ where

$F(0) = 0,\quad F(1) = 1,\quad F(n) = F(n-1) + F(n-2) \;\; (n \ge 2).$

C program

#include <stdio.h>

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

int main() {
    int n, i;
    printf("Enter number of terms: ");
    scanf("%d", &n);
    printf("Fibonacci series: ");
    for (i = 0; i < n; i++)
        printf("%d ", fib(i));
    return 0;
}

For $n = 7$ the output is 0 1 1 2 3 5 8. The function calls itself with smaller arguments until it reaches a base case. This simple recursion takes exponential time, about $O(2^n)$, because sub-problems are recomputed.

Insertion sort builds the sorted list one element at a time. The first element is regarded as sorted; each following element (the key) is compared with the elements of the sorted part on its left, larger elements are shifted one place right, and the key is inserted into its correct position. Worst and average time is $O(n^2)$, best case (already sorted) is $O(n)$; it is stable and in place.

Trace: 90, 57, 80, 10, 22, 21, 45, 9, 78 (the part before | is sorted).

Sorted: 9, 10, 21, 22, 45, 57, 78, 80, 90.

Hashing is a technique to store and retrieve data in nearly constant time using a hash table. A hash function $h(k)$ converts a key $k$ into an index of the table, and the record is stored at that index. For a table of size $m$, a common hash function is

$h(k) = k \bmod m.$

When two different keys give the same index, a collision occurs and must be resolved.

Open hashing (separate chaining). Each table slot holds a pointer to a linked list (chain). All keys that hash to the same index are inserted in the list of that slot, so the table never overflows.

Example. $m = 10$, $h(k) = k \bmod 10$, keys: 15, 25, 35, 42, 52, 9, 19.

Here 25 and 35 collide with 15 at index 5, 52 collides with 42 at index 2, and 19 collides with 9 at index 9; each is simply appended to the chain. Search for a key computes $h(k)$ and scans only that chain. Average time is $O(1 + \alpha)$ where $\alpha = n/m$ is the load factor.

Advantages: simple, deletion is easy, table size is not a hard limit. Disadvantage: extra memory for pointers and poorer cache behaviour.

Serial (sequential) algorithm. Instructions are executed one after another on a single processor; only one operation is performed at any instant. Most traditional algorithms are of this type.

Parallel algorithm. The problem is divided into independent sub-problems that are executed simultaneously on multiple processors (or cores), and the partial results are then combined.

Example: sum of $n$ numbers.

• Serial: sum = 0; for i in 1..n: sum = sum + a[i] takes $n-1$ additions one after another, time $O(n)$.
• Parallel: with $n/2$ processors, add pairs simultaneously: step 1 gives $n/2$ partial sums, step 2 gives $n/4$, and so on. For $a = \{1,2,3,4,5,6,7,8\}$: step 1 gives 3, 7, 11, 15; step 2 gives 10, 26; step 3 gives 36. Only $\log_2 8 = 3$ parallel steps are needed, so time is $O(\log n)$.

Merge sort is another example: the two halves can be sorted in parallel.

A queue is a linear data structure that follows First In First Out (FIFO). Insertion (enqueue) is at the rear and deletion (dequeue) is at the front. The basic operations are enqueue, dequeue, peek/display, isEmpty and isFull.

C program (array implementation)

#include <stdio.h>
#define MAX 5

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

int isEmpty() { return front == -1; }
int isFull()  { return rear == MAX - 1; }

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

void dequeue() {
    if (isEmpty()) { printf("Queue underflow\n"); return; }
    printf("Deleted: %d\n", queue[front]);
    if (front == rear) front = rear = -1;   /* queue became empty */
    else front++;
}

void display() {
    if (isEmpty()) { printf("Queue is empty\n"); return; }
    for (int i = front; i <= rear; i++)
        printf("%d ", queue[i]);
    printf("\n");
}

int main() {
    int ch, x;
    do {
        printf("1.Enqueue 2.Dequeue 3.Display 4.Exit: ");
        scanf("%d", &ch);
        switch (ch) {
            case 1: printf("Value: "); scanf("%d", &x); enqueue(x); break;
            case 2: dequeue(); break;
            case 3: display(); break;
        }
    } while (ch != 4);
    return 0;
}

Each operation takes $O(1)$ time. A weakness of this linear queue is that freed space at the front cannot be reused; a circular queue removes this problem.

Circular linked list. A circular linked list is a linked list in which the next pointer of the last node points back to the first node instead of NULL, so the list forms a ring. It can be singly or doubly linked. Any node can be a starting point, and traversal ends when we return to the start node. It is useful for round-robin scheduling and buffers.

Node and deletion functions (singly circular list)

struct node {
    int data;
    struct node *next;
};
struct node *head = NULL;      /* points to first node */

/* delete the first node */
void deleteFirst() {
    if (head == NULL) { printf("List empty\n"); return; }
    struct node *t = head;
    if (head->next == head) {          /* only one node */
        head = NULL;
    } else {
        struct node *last = head;
        while (last->next != head) last = last->next;
        head = head->next;
        last->next = head;
    }
    free(t);
}

/* delete the last node */
void deleteLast() {
    if (head == NULL) { printf("List empty\n"); return; }
    if (head->next == head) { free(head); head = NULL; return; }
    struct node *prev = head, *cur = head->next;
    while (cur->next != head) { prev = cur; cur = cur->next; }
    prev->next = head;
    free(cur);
}

/* delete the node containing key */
void deleteNode(int key) {
    if (head == NULL) { printf("List empty\n"); return; }
    struct node *cur = head, *prev = NULL;
    if (head->data == key) { deleteFirst(); return; }
    do {
        prev = cur;
        cur = cur->next;
        if (cur->data == key) {
            prev->next = cur->next;
            free(cur);
            return;
        }
    } while (cur != head);
    printf("Key not found\n");
}

Algorithm for deleting a given node

1. If the list is empty, report underflow and stop.
2. If the first node holds the key: if it is the only node, set $head = NULL$; otherwise find the last node, set $head = head.next$ and $last.next = head$; free the old first node.
3. Otherwise traverse with two pointers (prev, cur) until cur->data = key or cur returns to head.
4. If found, set $prev.next = cur.next$ and free cur; else report "not found".

Huffman algorithm. Huffman coding is a greedy algorithm for lossless data compression. It assigns shorter binary codes to characters that occur more often and longer codes to rarer ones. The codes are prefix codes (no code is the prefix of another), so a bit stream can be decoded unambiguously.

Algorithm

1. Create a leaf node for every character with its frequency and place all nodes in a min priority queue.
2. Remove the two nodes with the smallest frequencies, create a new internal node whose frequency is their sum, with these two as children, and insert it back.
3. Repeat step 2 until only one node (the root) remains.
4. Label left edges 0 and right edges 1; the path from the root to a leaf is that character's code.

Example. Frequencies: a = 5, b = 9, c = 12, d = 13, e = 16, f = 45.

• 5 + 9 = 14 (a, b)
• 12 + 13 = 25 (c, d)
• 14 + 16 = 30 (14, e)
• 25 + 30 = 55
• 45 + 55 = 100 (root; f left, 55 right)

Total $= 224$ bits, against $3 \times 100 = 300$ bits for fixed 3-bit codes.

B-tree of order 5. Order 5 means at most 5 children and 4 keys per node; every non-root node has at least 2 keys. When a node gets a fifth key it splits and the median key moves up. The key 55 appears twice in the data; a B-tree stores distinct keys, so the second 55 is ignored.

Insertion of 20, 10, 26, 55, 80, 11, 9, 60, 67, 22, 76, 56, 45, 34, 100, 150:

1. 20, 10, 26, 55 give the node [10, 20, 26, 55].
2. Insert 80: overflow [10, 20, 26, 55, 80]; median 26 goes up. Root [26] with children [10, 20] and [55, 80].
3. Insert 11, 9: left child becomes [9, 10, 11, 20]. Insert 60, 67: right child becomes [55, 60, 67, 80].
4. Insert 22: left child overflows [9, 10, 11, 20, 22]; median 11 goes up. Root [11, 26]; children [9, 10], [20, 22], [55, 60, 67, 80].
5. Insert 76: right child overflows [55, 60, 67, 76, 80]; median 67 goes up. Root [11, 26, 67]; children [9, 10], [20, 22], [55, 60], [76, 80].
6. Insert 56: [55, 56, 60]. Insert 45: [45, 55, 56, 60].
7. Insert 34: that child overflows [34, 45, 55, 56, 60]; median 55 goes up. Root [11, 26, 55, 67].
8. Insert 100 and 150: last child becomes [76, 80, 100, 150].

Final B-tree

                [ 11 | 26 | 55 | 67 ]
               /     |     |     |    \
          [9,10] [20,22] [34,45] [56,60] [76,80,100,150]

Minimum spanning tree (MST). A spanning tree of a connected, undirected graph $G$ is a subgraph that contains all vertices, is connected and has no cycles (it has exactly $V-1$ edges). In a weighted graph, the spanning tree whose total edge weight is the smallest is the minimum spanning tree. Applications: laying cables, pipelines or roads at least cost, network design.

Kruskal's algorithm finds the MST by a greedy strategy.

1. Sort all edges in non-decreasing order of weight.
2. Make each vertex a separate set (tree).
3. For each edge $(u, v)$ in sorted order: if $u$ and $v$ belong to different sets, add the edge to the MST and union the two sets; otherwise skip it because it would form a cycle.
4. Stop when the MST has $V - 1$ edges.

KRUSKAL(G):
    T = empty
    for each vertex v: MAKE-SET(v)
    sort edges by weight
    for each edge (u, v) in order:
        if FIND(u) != FIND(v):
            T = T + {(u, v)}
            UNION(u, v)
    return T

Time complexity is $O(E \log E)$ (sorting dominates); the disjoint-set operations are almost constant.

Example. Vertices A to F; 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.

The remaining edges (D-F 6, C-D 8, C-E 10) are not needed. MST edges: B-C, A-C, D-E, E-F, B-D.

$\text{Total weight} = 1 + 2 + 2 + 3 + 5 = 13.$

Abstract data type (ADT). An ADT is a mathematical model of a data structure that specifies the type of data stored and the operations that may be performed on it, together with what those operations do, but not how they are implemented. The user sees only the interface; the implementation (array or linked list, for example) is hidden. A stack ADT, for instance, is defined by push, pop, peek, isEmpty and isFull following the LIFO rule, whether it is built on an array or a linked list. Other ADTs: queue, list, tree, graph.

Conversion of $aUSDb*c-d+e/f/(g+h)$ to postfix. Precedence: $ (exponent, right associative) highest, then * and /, then + and -; equal precedence is left to right.

Postfix expression: $abUSDc*d-ef/gh+/+$

Linked list. A linked list is a linear collection of elements called nodes, where each node contains data and a link (pointer) to the next node. Nodes need not be in contiguous memory, so the size can grow or shrink at run time and insertion/deletion needs no shifting of elements.

Types of linked list

• Singly linked list: each node has data and one next pointer; traversal only forward; the last node points to NULL.
• Doubly linked list: each node has prev, data and next; traversal in both directions.
• Circular linked list: the last node points back to the first (singly or doubly), so there is no NULL.

Node structure

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

Insert at beginning of a doubly linked list

1. Create a new node N and set $N.data = x$.
2. Set $N.prev = NULL$ and $N.next = head$.
3. If $head \ne NULL$, set $head.prev = N$.
4. Set $head = N$.

Delete from beginning

1. If $head = NULL$, print "underflow" and stop.
2. Set $T = head$.
3. Set $head = head.next$.
4. If $head \ne NULL$, set $head.prev = NULL$.
5. Free $T$.

void insertBegin(int x) {
    struct node *n = malloc(sizeof(struct node));
    n->data = x; n->prev = NULL; n->next = head;
    if (head) head->prev = n;
    head = n;
}
void deleteBegin() {
    if (head == NULL) { printf("Underflow\n"); return; }
    struct node *t = head;
    head = head->next;
    if (head) head->prev = NULL;
    free(t);
}

Both operations take $O(1)$ time.

Prim's algorithm finds a minimum spanning tree (MST) of a connected, weighted, undirected graph by growing a single tree from a start vertex. At each step it adds the cheapest edge that connects a vertex already in the tree to a vertex outside it.

Steps

1. Choose any start vertex and put it in the tree set $T$.
2. Among all edges with one end in $T$ and the other outside $T$, pick the edge of minimum weight.
3. Add that edge and its new vertex to the tree.
4. Repeat until all $V$ vertices are in the tree ($V-1$ edges).

Time complexity is $O(V^2)$ with an adjacency matrix and $O(E \log V)$ with a binary heap.

Illustration. Vertices A to F; 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. Start at A.

All six vertices are now included. MST edges: A-C, C-B, B-D, D-E, E-F.

$\text{Total weight} = 2 + 1 + 5 + 2 + 3 = 13.$

Limitation of a linear queue over a circular queue. In a linear (array) queue, rear only moves forward and front only moves forward on deletion. After some deletions the positions at the beginning of the array are empty but can never be reused, because insertion is allowed only when $rear = MAX-1$ is not reached. The queue reports "overflow" even though free cells exist, so memory is wasted (or all elements must be shifted at cost $O(n)$). A circular queue treats the array as a ring, so rear wraps around to index 0 and the freed cells are reused.

Circular queue algorithms (array of size MAX; initially $front = rear = -1$)

Insert (enqueue)

1. If $(rear + 1) \bmod MAX = front$, print "overflow" and stop.
2. If $front = -1$, set $front = rear = 0$; otherwise set $rear = (rear + 1) \bmod MAX$.
3. Set $Q[rear] = x$.

Delete (dequeue)

1. If $front = -1$, print "underflow" and stop.
2. Set $x = Q[front]$.
3. If $front = rear$, set $front = rear = -1$ (queue becomes empty); otherwise set $front = (front + 1) \bmod MAX$.
4. Return $x$.

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

Divide and conquer is an algorithm design strategy 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 if small enough).
3. Combine the sub-solutions into the solution of the original problem.

Examples: binary search, merge sort, quick sort. Its running time typically follows $T(n) = aT(n/b) + f(n)$.

Binary search searches a sorted array by comparing the key with the middle element and discarding half of the array each time. In the divide-and-conquer view: divide at the middle, conquer one half only, nothing to combine. Time is $O(\log n)$.

Algorithm

1. Set $low = 0$, $high = n-1$.
2. While $low \le high$: compute $mid = \lfloor (low + high)/2 \rfloor$.
3. If $A[mid] = key$, return $mid$.
4. If $key < A[mid]$, set $high = mid - 1$; else set $low = mid + 1$.
5. If the loop ends, return $-1$ (not found).

Illustration. $A = \{3, 8, 14, 21, 27, 35, 42, 50, 64\}$ (indices 0 to 8), key $= 42$.

The key is found at index 6 in two comparisons. For key $= 10$: mid = 4 (27) gives $high = 3$; mid = 1 (8) gives $low = 2$; mid = 2 (14) gives $high = 1$; now $low > high$, so the key is not present.

Minimax algorithm. Minimax is a recursive decision (backtracking) algorithm used in two-player zero-sum games such as tic-tac-toe or chess. One player, MAX, tries to maximize the score and the opponent, MIN, tries to minimize it. The game tree is built to some depth; leaf positions get a utility value; then values are propagated upward: a MAX node takes the largest value of its children and a MIN node takes the smallest. At the root, MAX chooses the move leading to the best guaranteed value assuming the opponent plays optimally. Time is $O(b^d)$ for branching factor $b$ and depth $d$; alpha-beta pruning can cut the search.

Huffman tree. Frequencies: A 10, E 15, I 12, O 3, U 4, S 13, T 1 (total 58).

1. Merge the two smallest, T (1) and O (3), into node N1 = 4.
2. Smallest now N1 (4) and U (4): merge into N2 = 8.
3. Smallest: N2 (8) and A (10): merge into N3 = 18.
4. Smallest: I (12) and S (13): merge into N4 = 25.
5. Smallest: E (15) and N3 (18): merge into N5 = 33.
6. Merge N4 (25) and N5 (33) into the root = 58.

                    (58)
                 0 /    \ 1
               (25)      (33)
              0/  \1    0/   \1
             I    S    E    (18)
                            0/  \1
                          (8)    A
                         0/ \1
                      (4)    U
                     0/ \1
                    T    O

Huffman codes (left edge 0, right edge 1)

Total $= 24 + 26 + 30 + 30 + 16 + 5 + 15 = 146$ bits, compared with $3 \times 58 = 174$ bits for a fixed 3-bit code.

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

Applications: expression conversion and evaluation (infix, postfix, prefix); recursion and function-call management; parenthesis matching; undo/redo and browser back; reversing data; depth first search and backtracking.

Array implementation algorithms (stack $S$ of size $MAX$, $top = -1$ initially)

PUSH(x)

1. If $top = MAX - 1$, print "stack overflow" and stop.
2. Set $top = top + 1$.
3. Set $S[top] = x$.

POP()

1. If $top = -1$, print "stack underflow" and stop.
2. Set $x = S[top]$.
3. Set $top = top - 1$.
4. Return $x$.

Linked list implementation. The stack is a singly linked list in which the head (top) pointer is the top of the stack. Push inserts a node at the beginning and pop deletes the first node, so both are $O(1)$ and there is no fixed size limit (overflow happens only when memory is exhausted).

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

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

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

Push: create node, set its next to top, set top to the new node. Pop: if top is NULL report underflow; else save top, move top to top->next, free the saved node and return its data. The stack is empty when top == NULL.

External sorting. External sorting is used when the data to be sorted is too large to fit in main memory and resides on external storage (disk or tape). The data is sorted in chunks that fit in memory (runs), the sorted runs are written to disk, and then the runs are merged. The standard method is external merge sort; the main cost is the number of disk accesses.

Heap sort. Heap sort uses a binary max heap (a complete binary tree where every parent is $\ge$ its children).

1. Build a max heap from the array (heapify nodes from $\lfloor n/2 \rfloor$ down to 1).
2. Repeat $n-1$ times: swap the root (largest) with the last element of the heap, reduce the heap size by 1, and heapify the root to restore the heap.

Time is $O(n \log n)$ in all cases, space $O(1)$, not stable.

Trace for 82, 90, 10, 12, 15, 77, 55, 23, 25, 32 (positions 1 to 10).

Building the max heap

• Position 5 (15) with child 32: swap, giving 82, 90, 10, 12, 32, 77, 55, 23, 25, 15.
• Position 4 (12) with children 23, 25: swap with 25, giving 82, 90, 10, 25, 32, 77, 55, 23, 12, 15.
• Position 3 (10) with children 77, 55: swap with 77, giving 82, 90, 77, 25, 32, 10, 55, 23, 12, 15.
• Position 2 (90): already larger than its children.
• Position 1 (82) with children 90, 77: swap with 90.

Max heap: 90, 82, 77, 25, 32, 10, 55, 23, 12, 15

Sorting phase (after | is the sorted part)

Sorted: 10, 12, 15, 23, 25, 32, 55, 77, 82, 90.

BST vs AVL tree

The balance factor is $BF = h(\text{left subtree}) - h(\text{right subtree})$.

Deleting a node from an AVL tree. The node is first removed as in an ordinary BST, with no rebalancing yet:

• a leaf is simply removed;
• a node with one child is replaced by that child;
• a node with two children is replaced by a value from its left child's subtree, the largest value there (the in-order predecessor), and the node that held that value is removed.

Then the balance factors are recomputed from the changed place up to the root. A node with $BF = \pm 2$ would need a rotation.

Worked example. Consider the AVL tree

          10
        /    \
       5      15
      / \
     2   7

Removing 5 (two children): the largest value in its left child's subtree (just node 2) is 2, so 2 replaces 5 and the old leaf 2 is removed. The BST before rebalancing:

          10
        /    \
       2      15
        \
         7

Balance factors (leaf height 1, empty subtree height 0):

All balance factors lie in $\{-1, 0, +1\}$, so this tree is still an AVL tree and no rotation is required. If some node had reached $\pm 2$, a single or double rotation would then be applied.

Stack. A stack is a linear data structure in which insertion (push) and deletion (pop) take place at one end only, called the top. The element inserted last is removed first, so it follows the LIFO (Last In First Out) principle.

Why a stack is an ADT. An Abstract Data Type is defined by the data it holds and the operations allowed on it, not by how it is implemented. A stack is specified entirely by its operations: push(x), pop(), peek(), isEmpty() and isFull(), together with the LIFO rule. The user only needs these operations; the stack may be implemented with an array or a linked list without changing the way it is used. Because the interface is separated from the implementation, the stack is an ADT.

Applications of stack

1. Conversion of infix expressions to postfix or prefix, and evaluation of postfix expressions.
2. Function call management and recursion (the call stack stores return addresses and local variables).
3. Undo/redo operations in editors and browser back-history.
4. Checking balanced parentheses and syntax parsing in compilers.

Postfix expression: 4 5 + 7 3 - 2 + *

Scan left to right. Push operands; on an operator pop the top two values (second popped is the left operand), apply the operator and push the result.

Result = 54.

Tower of Hanoi. 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 under these rules: only one disk is moved at a time, only the top disk of a peg can be moved, and a larger disk may never be placed on a smaller one.

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

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

The problem reduces to the same problem with $n-1$ disks, with base case $n = 1$ (move the disk directly).

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

The number of moves satisfies $T(n) = 2T(n-1) + 1$, giving $T(n) = 2^n - 1$. For $n = 3$ there are 7 moves.

Hashing. Hashing is a technique that maps a key to a position in a table (hash table) using a hash function $h(k)$, so that searching, insertion and deletion take $O(1)$ time on average. A common function is $h(k) = k \bmod m$, where $m$ is the table size.

Collision. A collision occurs when two different keys give the same index, $h(k_1) = h(k_2)$.

Open addressing. All keys are stored in the table itself. When the home slot is occupied, other slots are examined in a fixed probe sequence until an empty one is found: $(h(k) + f(i)) \bmod m$ for $i = 0, 1, 2, \dots$

1. Linear probing: $f(i) = i$. Check the next slots one by one. It is simple but causes primary clustering.
2. Quadratic probing: $f(i) = i^2$. Probes slots at distance 1, 4, 9, ... which reduces primary clustering (but gives secondary clustering).
3. Double hashing: $f(i) = i \cdot h_2(k)$, where $h_2$ is a second hash function (for example $h_2(k) = 7 - (k \bmod 7)$). The step size depends on the key, which spreads keys well.

Example (linear probing, $m = 10$). Insert 25, 35, 45: $h(25) = 5$ goes to slot 5; $h(35) = 5$ is occupied so it goes to slot 6; $h(45) = 5$ finds 5 and 6 occupied and goes to slot 7.

Binary search is a searching technique for a sorted array. It compares the key with the middle element; if they are equal the search ends, if the key is smaller the search continues in the left half, otherwise in the right half. The search range is halved each step, so the time complexity is $O(\log n)$.

Trace. The data is not sorted, so sort it first:

2, 5, 7, 8, 11, 12, 19, 21, 21 (indices 0 to 8). Key = 12.

The key 12 is found at index 5 of the sorted array (6th position) after 3 comparisons.

Big-oh notation. Big-oh gives an asymptotic upper bound on the growth of an algorithm's running time. $f(n) = O(g(n))$ if there exist positive constants $c$ and $n_0$ such that

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

For example, $f(n) = 3n + 2 = O(n)$ since $3n + 2 \le 4n$ for $n \ge 2$. It describes the worst-case growth and ignores constants and lower-order terms.

Divide and conquer. A problem is solved by three steps:

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

Example: merge sort. Divide the array into two halves, sort each half recursively, then merge the two sorted halves. For 38, 27, 43, 3: split into (38, 27) and (43, 3), then into single elements; merge to (27, 38) and (3, 43); merge to 3, 27, 38, 43. The recurrence is

$T(n) = 2T(n/2) + O(n) \;\Rightarrow\; T(n) = O(n \log n).$

Other examples are binary search and quick sort.

Depth of a node: the number of edges on the path from the root to that node (the root has depth 0). The depth of the tree is the maximum depth of any node.

Degree of a node: the number of children (sub-trees) of that node. A leaf has degree 0. The degree of a tree is the maximum degree of its nodes.

Traversals. The tree figure is not reproduced here, so the traversals are shown on this tree:

        A
      /   \
     B     C
    / \     \
   D   E     F

Here the depth of A is 0, B and C are 1, and D, E, F are 2; the degree of A and B is 2, of C is 1 and of D, E, F is 0.

• Pre-order (Root, Left, Right): A, B, D, E, C, F
• In-order (Left, Root, Right): D, B, E, A, C, F
• Post-order (Left, Right, Root): D, E, B, F, C, A

Dynamic implementation of a queue. A queue can be implemented with a singly linked list, so its size is not fixed. Two pointers are kept: front (the first node, where deletion happens) and rear (the last node, where insertion happens).

struct node { int data; struct node *next; };
struct node *front = NULL, *rear = NULL;

Enqueue

1. Create a new node and set its data; next = NULL.
2. If the queue is empty (front == NULL), set front = rear = new.
3. Otherwise set rear->next = new and rear = new.

Dequeue

1. If front == NULL, report underflow and stop.
2. Set temp = front, read its data, and set front = front->next.
3. If front becomes NULL, set rear = NULL.
4. Free temp.

Both operations take $O(1)$ time.

Insertion at the end of a singly linked list (head pointer head)

1. Create node new with data and new->next = NULL.
2. If head == NULL, set head = new and stop.
3. Set temp = head; while temp->next != NULL, move temp = temp->next.
4. Set temp->next = new.

Deletion at the end

1. If head == NULL, report underflow.
2. If head->next == NULL (one node), free head and set head = NULL.
3. Otherwise set temp = head; while temp->next->next != NULL, move temp = temp->next.
4. Free temp->next and set temp->next = NULL.

Both operations need traversal of the list, so each takes $O(n)$ time.

Complete binary tree. A binary tree in which every level is completely filled except possibly the last, and the nodes of the last level are filled from left to right. A binary tree with $n$ nodes stored in an array has children of node $i$ at $2i+1$ and $2i+2$ (0-based).

Skewed tree. A binary tree in which every node has only one child, so it behaves like a linked list. It is left-skewed if all children are left children and right-skewed if all are right children. Its height is $n - 1$.

Heap sort function (max-heap)

void heapify(int a[], int n, int i) {
    int largest = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && a[l] > a[largest]) largest = l;
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest != i) {
        int t = a[i]; a[i] = a[largest]; a[largest] = t;
        heapify(a, n, largest);
    }
}

void heapSort(int a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)   /* build max-heap */
        heapify(a, n, i);
    for (int i = n - 1; i > 0; i--) {
        int t = a[0]; a[0] = a[i]; a[i] = t;   /* move max to end */
        heapify(a, i, 0);
    }
}

Sorting 12, 9, 1, 13, 16, 24, 21, 5

Build the max-heap (heapify from index 3 down to 0):

• Index 3 (13): child 5, no change.
• Index 2 (1): swap with 24: 12, 9, 24, 13, 16, 1, 21, 5
• Index 1 (9): swap with 16: 12, 16, 24, 13, 9, 1, 21, 5
• Index 0 (12): swap with 24, then with 21: 24, 16, 21, 13, 9, 1, 12, 5

Extract the maximum repeatedly (the part after | is sorted):

Sorted: 1, 5, 9, 12, 13, 16, 21, 24. Time complexity is $O(n \log n)$.

Graph traversal visits every vertex reachable from a start vertex exactly once.

Breadth First Traversal (BFS) uses a queue and visits vertices level by level.

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

Depth First Traversal (DFS) uses a stack (or recursion) and goes as deep as possible before backtracking.

1. Push the start vertex and mark it visited.
2. Visit an unvisited neighbour of the top vertex and push it; if none exists, pop the top.
3. Repeat until the stack is empty.

Example. Graph with edges A-B, A-C, B-D, C-D, D-E, start at A (neighbours in alphabetical order):

• BFS: queue A; visit A, add B, C; visit B, add D; visit C; visit D, add E; visit E. Order: A, B, C, D, E.
• DFS: A, then B, then D (from B), then C (unvisited neighbour of D), back to D, then E. Order: A, B, D, C, E.

Both take $O(V + E)$ time with adjacency lists.

Dijkstra's algorithm. The graph in the question is not reproduced, so the method is shown on this graph with weights: A-B = 4, A-C = 1, C-B = 2, B-D = 1, C-D = 5, B-E = 6, D-E = 3.

Set $d(A) = 0$ and all others $\infty$. Repeatedly pick the unvisited vertex with the smallest distance, fix it, and relax its edges: if $d(u) + w(u,v) < d(v)$ then $d(v) = d(u) + w(u,v)$.

Shortest distances from A: B = 3 (A-C-B), C = 1 (A-C), D = 4 (A-C-B-D), E = 7 (A-C-B-D-E).

Difference between stack and queue

General applications of a stack

1. Expression conversion (infix to postfix/prefix) and postfix evaluation.
2. Function calls and recursion (the call stack).
3. Parenthesis matching and syntax checking in compilers.
4. Undo/redo in editors, browser back button, and depth-first graph traversal.

Linked list. A linked list is a linear data structure made of nodes, where each node holds data and a pointer to the next node. Nodes are allocated dynamically and need not be contiguous in memory, so the size can grow or shrink at run time. The first node is pointed to by head, and the last node's pointer is NULL.

Doubly linked list. Each node has two pointers, prev and next, so it can be traversed in both directions. The prev of the first node and the next of the last node are NULL.

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

Circular linked list. The last node points back to the first node instead of NULL, so there is no end and any node can be reached from any other. It can be singly or doubly linked.

[10] -> [20] -> [30] -> (back to 10)

Differences

Recursion is a technique in which a function solves a problem by calling itself on smaller instances of the same problem. A recursive function is a function that calls itself; it must have a base case that stops the recursion and a recursive case that moves towards the base case.

Fibonacci numbers. $F(0) = 0$, $F(1) = 1$, $F(n) = F(n-1) + F(n-2)$ for $n \ge 2$.

#include <stdio.h>

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

int main() {
    int n = 7;
    printf("fib(%d) = %d\n", n, fib(n));   /* prints 13 */
    return 0;
}

For $n = 4$: $F(4) = F(3) + F(2) = 2 + 1 = 3$. This simple version takes exponential time, $O(2^n)$.