Data Structure and Algorithms

An abstract data type (ADT) is a mathematical model of a data structure that specifies the data it stores and the operations that can be performed on it, without saying how they are implemented. The user sees only the interface (e.g. push, pop for a stack), while the implementation (array or linked list) stays hidden.

• It can be traversed in both directions (forward using next, backward using prev).
• A node can be deleted given only a pointer to that node, since its predecessor is reachable through prev (no need to search for the previous node).
• Insertion before a given node is easy and takes $O(1)$ time.
• Operations at the tail (insert or delete last node) are efficient when a tail pointer is kept.

A skip list is a probabilistic data structure made of several layers of sorted linked lists. The bottom layer holds all the elements, and each higher layer is a sparser "express lane" that skips over many elements of the layer below. Search, insertion and deletion take $O(\log n)$ expected time, similar to a balanced tree.

• Function call management and recursion (call stack)
• Expression evaluation and conversion (infix to postfix/prefix, postfix evaluation)
• Checking balanced parentheses
• Undo/redo operations in editors
• Backtracking (e.g. maze solving) and depth-first search
• Browser back-button history

Binary search is more efficient (for sorted data).

• Linear search checks elements one by one, so its worst and average time complexity is $O(n)$.
• Binary search halves the search range at each step, so its worst-case time complexity is $O(\log_2 n)$.

For $n=1{,}000{,}000$, linear search needs up to $10^6$ comparisons while binary search needs about $20$. The only requirement is that the list must be sorted.

A recursion is tail recursion when the recursive call is the very last operation performed by the function, so nothing remains to be done after the call returns. Such calls can be converted into a loop (tail-call optimisation), saving stack space. Example:

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

• File system directory structure
• HTML/XML DOM representation
• Binary search trees for fast searching and sorting
• Heaps for priority queues and heap sort
• Expression trees in compilers
• Decision trees and game trees in AI
• Routing tables and tries (autocomplete, dictionaries)
• B-trees and B+ trees for database indexing
• Huffman trees for data compression

A max heap is a complete binary tree in which the value of every node is greater than or equal to the values of its children, so the largest element is at the root.

Example: the array $[50, 30, 40, 10, 20, 35]$ represents

        50
       /  \
     30    40
    /  \   /
  10   20 35

Each parent ($50>30,40$; $30>10,20$; $40>35$) is at least as large as its children.

An adjacency matrix is a way of representing a graph with $n$ vertices as an $n\times n$ matrix $A$, where $A[i][j]=1$ (or the edge weight) if there is an edge from vertex $i$ to vertex $j$, and $0$ (or $\infty$) otherwise. For an undirected graph the matrix is symmetric. It needs $O(n^2)$ space and allows checking for an edge in $O(1)$ time.

The shortest path problem is the problem of finding a path between two vertices (or from one source to all other vertices) in a weighted graph such that the sum of the edge weights along the path is minimum. It is solved with algorithms such as Dijkstra's (non-negative weights), Bellman-Ford and Floyd-Warshall.

Algorithm POP (array implementation, top initially $-1$)

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

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

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

Time complexity is $O(1)$.

Algorithm ENQUEUE (circular queue of size MAX, front = rear = -1 initially)

1. If (rear + 1) % MAX == front, print "Queue overflow" and stop.
2. If front == -1, set front = 0 (first element).
3. Set rear = (rear + 1) % MAX.
4. Set queue[rear] = item.

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

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

An ADT defines a set of data and the operations on it, hiding the implementation. A linked list fits this definition:

• Data: an ordered collection of elements (nodes holding data and a link).
• Operations: insert (at beginning, end, or position), delete, search, traverse, and check whether it is empty.
• Hidden implementation: the user calls insert() or delete() without needing to know how pointers are rearranged. The same list interface could be implemented with arrays or pointers.

Hence a linked list is an ADT (the "list ADT") whose pointer-based implementation is separate from its interface.

Algorithm. For $i = 0$ to $n-2$: find the index min of the smallest element in a[i..n-1], then swap a[i] with a[min].

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

Time complexity is $O(n^2)$ in all cases.

Using Euclid's algorithm: $\gcd(a,b)=a$ if $b=0$, otherwise $\gcd(a,b)=\gcd(b,\ a \bmod b)$.

Algorithm GCD(a, b)

1. If b == 0, return a.
2. Else return GCD(b, a % b).

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

For example, $\gcd(48,18)=\gcd(18,12)=\gcd(12,6)=\gcd(6,0)=6$.

Expression: $(A*B)+(C*D)$

Postfix expression: $AB*CD*+$

Why complexity analysis is performed.

• To measure how the running time (time complexity) and memory use (space complexity) of an algorithm grow with input size $n$.
• To compare algorithms independently of hardware, language and compiler.
• To choose the most efficient algorithm for large inputs and predict its scalability.

Big Oh notation. $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$

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

Pictorial representation.

 time
  |                       c*g(n)
  |                     /
  |                   /    .  f(n)
  |                 /   .
  |               /  .
  |             /.
  |           /.
  |         . 
  |       /
  |_____/_____|______________ n
             n0

For $n\ge n_0$ the curve $f(n)$ always stays below $c\cdot g(n)$.

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

Definition. A doubly linked list is a linear data structure in which each node has three fields: prev (pointer to the previous node), data, and next (pointer to the next node). It can be traversed in both directions.

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

Algorithm: delete the last node

1. If head == NULL, print "List empty" and stop.
2. If head->next == NULL (only one node), free head, set head = NULL, and stop.
3. Set temp = head.
4. While temp->next != NULL, set temp = temp->next. (temp is now the last node.)
5. Set temp->prev->next = NULL.
6. Free temp.

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

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

Quick sort with the first element as pivot. Data: $11, 13, 8, 15, 20, 22, 4, 3, 26, 2$.

Pass 1 (pivot 11). Move i right to the first element greater than the pivot and j left to the first element not greater than it, and swap them until they cross:

• swap $13$ and $2$: $11,2,8,15,20,22,4,3,26,13$
• swap $15$ and $3$: $11,2,8,3,20,22,4,15,26,13$
• swap $20$ and $4$: $11,2,8,3,4,22,20,15,26,13$
• pointers cross; swap the pivot with $4$: $[4,2,8,3]\ \mathbf{11}\ [22,20,15,26,13]$

Left part $[4,2,8,3]$, pivot 4: $[3,2]\ 4\ [8]$. Then $[3,2]$ with pivot 3 gives $[2]\ 3$. So the left part sorts to $2,3,4,8$.

Right part $[22,20,15,26,13]$, pivot 22: $[13,20,15]\ 22\ [26]$.

• $[13,20,15]$, pivot 13: $13\ [20,15]$, and $[20,15]$ sorts to $15,20$.

So the right part sorts to $13,15,20,22,26$.

Sorted output:

$2,\ 3,\ 4,\ 8,\ 11,\ 13,\ 15,\ 20,\ 22,\ 26$

Average time complexity is $O(n\log n)$; the worst case is $O(n^2)$.

A collision occurs when two keys hash to the same index of the hash table.

Collision resolution techniques

1. Open addressing (closed hashing): linear probing, quadratic probing, double hashing.
2. Separate chaining (open hashing): each table slot holds a linked list of all keys that hash to it.
3. Rehashing (resizing the table and re-inserting keys).

Linear probing. If the slot $h(k)$ is occupied, the following slots are tried one by one, wrapping around the table, until an empty slot is found:

$\text{index}_i=(h(k)+i)\bmod m,\quad i=0,1,2,\dots$

Searching follows the same probe sequence until the key or an empty slot is found.

Example. Table size $m=7$, $h(k)=k \bmod 7$, insert $50, 700, 76, 85$:

• $50 \bmod 7=1$, so it goes to slot 1.
• $700 \bmod 7=0$, so it goes to slot 0.
• $76 \bmod 7=6$, so it goes to slot 6.
• $85 \bmod 7=1$, but slot 1 is occupied, so try slot 2, which is free, and place it there.

Linear probing is simple and cache-friendly, but it suffers from primary clustering (long runs of filled slots).

Why balance a binary search tree. In a BST, search, insertion and deletion take time proportional to the height $h$. If keys arrive in sorted order the tree degenerates into a linked list with $h=n$ and operations cost $O(n)$. A balanced tree keeps $h=O(\log n)$, so all operations take $O(\log n)$ time (e.g. AVL, red-black trees).

Binary search tree vs multiway search tree

B-tree of order 5. Each node has at most 4 keys and 5 children; every non-root node has at least 2 keys. When a node gets 5 keys, it splits at the median, which moves up. The duplicate key 60 (inserted second time) is ignored.

1. Insert $20, 40, 80, 30$: leaf $[20,30,40,80]$.
2. Insert $120$: overflow; median 40 moves up. Root $[40]$ with leaves $[20,30]$ and $[80,120]$.
3. Insert $90, 50$: right leaf becomes $[50,80,90,120]$.
4. Insert $140$: overflow; median 90 moves up. Root $[40,90]$; leaves $[20,30]$, $[50,80]$, $[120,140]$.
5. Insert $110, 60, 100$: leaves $[20,30]$, $[50,60,80]$, $[100,110,120,140]$.
6. Insert $200$: overflow; median 120 moves up. Root $[40,90,120]$; leaves $[20,30]$, $[50,60,80]$, $[100,110]$, $[140,200]$.
7. Insert $190, 250$: last leaf becomes $[140,190,200,250]$. The second $60$ is a duplicate and is ignored.
8. Insert $130$: it goes to the last leaf, which overflows to $[130,140,190,200,250]$. Median 190 moves up, so the root becomes $[40,90,120,190]$ with leaves $[130,140]$ and $[200,250]$.
9. Insert $220$: leaf $[200,220,250]$.
10. Insert $170$: leaf $[130,140,170]$.

Final B-tree

                [ 40 | 90 | 120 | 190 ]
               /     |      |      |     \
        [20,30] [50,60,80] [100,110] [130,140,170] [200,220,250]

Applications of a minimum spanning tree (MST)

• Designing least-cost networks: computer, telephone, electrical, water and road networks
• Cluster analysis in data mining and image segmentation
• Approximation algorithms for the travelling salesman problem
• Circuit design (minimising wire length)

Kruskal's vs Prim's algorithm

Dijkstra's algorithm (shortest path from $s$ to $t$)

1. Set $dist(s)=0$ and $dist(v)=\infty$ for every other vertex; mark all vertices unvisited.
2. Pick the unvisited vertex $u$ with the smallest $dist$ and mark it visited.
3. For each neighbour $v$ of $u$, if $dist(u)+w(u,v)<dist(v)$, set $dist(v)=dist(u)+w(u,v)$ and $prev(v)=u$.
4. Repeat steps 2-3 until $t$ is visited. The value $dist(t)$ is the shortest distance, and following $prev$ pointers back from $t$ to $s$ gives the path.

The weighted graph is given as a figure in the original question and is not reproduced here. Applying the above steps, starting from $s$, to its edge weights gives the shortest distance and path to $t$.