Data Structures Lab Notes

This article merges eight earlier data structures lab reports. The filler and the full source listings are gone; what remains is the core idea, key data structure, and algorithmic essentials of each experiment, as a revision outline. Code snippets are C++.

1. Recursion and the Stack: Fibonacci Numbers

Problem

Compute the $n$-th Fibonacci number recursively.

Why recursion depends on the stack

Whether a recursive call can return correctly depends on two things: how arguments are passed and where to return to. Take Fib(5):

1. Every recursive level needs fresh storage for that level’s parameters;
2. The “which line do I resume at when this call finishes” return address must also be saved.

Together these form an activation record, pushed by the system onto the call stack. Calls push, returns pop from the top, and control lands back in the right frame.

For Fib(3) = Fib(2) + Fib(1) the call tree is:

Fib(3)
├── Fib(2)
│   ├── Fib(1) → returns 1
│   └── Fib(0) → returns 0
│   gives 1
└── Fib(1) → returns 1
gives 2

Algorithm

int Fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return Fib(n - 1) + Fib(n - 2);
}

This version recomputes the same subproblems over and over, giving exponential time $O(2^n)$. For real use, prefer iteration or memoisation, which is $O(n)$. The recursive form is valuable here because it exposes how the stack works.

2. Partitioning a Set with Conflicts

Problem

Split a set into pairwise disjoint subsets such that no two elements within a subset conflict, using as few subsets as possible. (Typical application: timetabling and scheduling.)

Algorithm: cyclic filtering

1. Describe the conflicts with a 2-D array (a conflict matrix): $conflict[i][j] = 1$ means $i$ and $j$ conflict, $0$ means they do not.
2. Take the first ungrouped element and start a new group with it.
3. Scan the remaining ungrouped elements: if an element conflicts with none of the elements already in the current group, add it; otherwise skip it and leave it for a later round.
4. When a pass ends with elements still ungrouped, open a new group and repeat from step 2 until everything is grouped.

Data structure

A circular queue holds the pending elements. Each pass rotates them around the queue, so no extra storage is needed.

Key points

• “Can this element join the group” must be checked against every element already in the group; checking just one gives wrong results.
• This is a greedy strategy — squeeze in whatever fits now — so it produces a good partition, not necessarily the mathematically optimal one.

3. Sparse Matrix Multiplication

Problem

When a matrix has few non-zero entries, a full 2-D array wastes a lot of space. Store only the non-zeros as triples, then multiply two such matrices.

Data structures

struct Node {          // one non-zero entry
    int i, j;          // row and column index
    int data;          // value
};

struct Matrix {
    int m, n;          // total rows, total columns
    int L;             // number of non-zero entries
    Node* Ma[MAX];     // array of non-zero entries
};

Algorithm

Following $C_{ij} = \sum_k A_{ik} \cdot B_{kj}$, but only accumulating terms where both factors are non-zero:

1. Walk each non-zero entry $(i, k, a)$ of $A$;
2. Search $B$ for non-zero entries $(k, j, b)$ whose row index is $k$;
3. Accumulate $a \times b$ into position $(i, j)$ of the result.

Result entries are created on demand; if an accumulation ends at 0, nothing is stored.

Key points

• Far faster than the naive triple loop, because multiplications by zero are skipped entirely.
• To speed it up further, add a row index to the triple list (a row-linked list) so step 2 does not rescan $B$ from scratch each time.
• Validate that the number of columns of $A$ equals the number of rows of $B$, and that input indices are in range.

4. KMP String Matching

Problem

Find the first occurrence of a pattern in a text. Naive matching shifts the pattern right by one and rewinds the text pointer on a mismatch, which is $O(nm)$ in the worst case. KMP brings it down to $O(n+m)$.

The core: the LPS array

LPS (longest prefix suffix) records, for each position of the pattern, the length of the longest proper prefix that is also a suffix of the substring before that position. It tells us how far the pattern may safely slide on a mismatch, so the text pointer never has to move backwards.

For the pattern ABABCABAB:

Algorithm

// build the LPS array
void computeLPS(const string& pat, vector<int>& lps) {
    int len = 0;          // current longest prefix-suffix match
    lps[0] = 0;
    int i = 1;
    while (i < (int)pat.size()) {
        if (pat[i] == pat[len]) {
            lps[i++] = ++len;
        } else if (len != 0) {
            len = lps[len - 1];   // fall back to the next-longest border
        } else {
            lps[i++] = 0;
        }
    }
}

// search for pat inside text
void KMPSearch(const string& text, const string& pat) {
    int m = pat.size(), n = text.size();
    vector<int> lps(m);
    computeLPS(pat, lps);

    int i = 0, j = 0;          // i walks the text, j walks the pattern
    while (i < n) {
        if (pat[j] == text[i]) { i++; j++; }
        if (j == m) {
            cout << "Match found at index " << i - j << endl;
            j = lps[j - 1];    // keep searching for further matches
        } else if (i < n && pat[j] != text[i]) {
            if (j != 0) j = lps[j - 1];
            else        i++;   // j is already 0, so advance the text pointer instead
        }
    }
}

Key points

• The text pointer i never moves backwards — that is where KMP’s efficiency comes from.
• On a mismatch, fall back with lps[j-1] rather than resetting j to zero.
• The lps construction is itself “matching the pattern against itself” and mirrors the main loop.
• Example: text ABABDABACDABABCABAB, pattern ABABCABAB — the match starts at index 10.

5. Binary Trees: Storage and Traversal

Problem

Given a string of characters in level order (BFS order) where @ marks a missing node, build a binary tree, then implement traversal for both array-based and pointer-based storage.

Two storage schemes

Sequential (array) storage: parent/child relations are computed from indices:

• Parent at index $i$ → left child $2i+1$, right child $2i+2$;
• Conversely, the parent of node $i$ is $\lfloor (i-1)/2 \rfloor$.

Suits complete binary trees; with a sparse tree most of the array is wasted.

Linked storage: a struct with pointers, built with the help of a queue.

struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
};

Construction: push the root, then repeatedly pop a node from the front and attach its left and right children in turn (an @ means that side stays empty), pushing each new child. To build from preorder input instead, swap the queue for a stack.

The three depth-first traversals

void preOrder(TreeNode* p) {          // root → left → right
    if (!p) return;
    visit(p);
    preOrder(p->left);
    preOrder(p->right);
}

void inOrder(TreeNode* p) {           // left → root → right
    if (!p) return;
    inOrder(p->left);
    visit(p);
    inOrder(p->right);
}

void postOrder(TreeNode* p) {         // left → right → root
    if (!p) return;
    postOrder(p->left);
    postOrder(p->right);
    visit(p);
}

Breadth-first traversal

Use a queue to process the tree level by level: on visiting a node, push its left then right child.

void levelOrder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* p = q.front(); q.pop();
        visit(p);
        if (p->left)  q.push(p->left);
        if (p->right) q.push(p->right);
    }
}

Worked example

Input abc@def@@@@ (level order, @ empty) describes this tree:

        a
      /   \
     b     c
    / \   / \
   @   d e   f
      / \ / \ / \
     @  @ @ @ @  @

With array storage, take care where an inorder walk starts: preorder may start at index 0, but inorder must start at the leftmost node of the whole tree, or the left half of the left subtree is missed.

Reconstructing a tree from traversals

• preorder + inorder, postorder + inorder, and level order + inorder each determine a unique binary tree.
• preorder + postorder does not, because it cannot tell whether a lone child hangs on the left or the right.

6. Huffman Trees and Coding

Problem

Assign codes to characters according to their frequency so that the encoded text is as short as possible and no code is a prefix of another (a prefix code, which guarantees unique decoding).

Algorithm

1. Count the frequency of every character.
2. Create one leaf node per character and push them all into a min-heap.
3. While more than one node remains: pop the two least frequent nodes, merge them into a new internal node whose frequency is their sum, and push it back.
4. When one node is left, it is the root of the Huffman tree.

while (minHeap.size() > 1) {
    auto left  = minHeap.top(); minHeap.pop();
    auto right = minHeap.top(); minHeap.pop();
    auto parent = new HuffmanNode('$', left->frequency + right->frequency);
    parent->left = left;
    parent->right = right;
    minHeap.push(parent);
}

Encoding and decoding

• Generate codes: recurse from the root, appending 0 when going left and 1 when going right; at a leaf, the accumulated string is that character’s code.
• Encode: replace every character of the input with its code.
• Decode: start at the root, follow 0 left and 1 right, and on reaching a leaf emit that character and restart from the root.

Key points

• Frequent characters sit close to the root and get short codes — that is the whole idea behind compression.
• Because every character lives at a leaf, no code can be a prefix of another, so decoding is unambiguous.
• Using a min-heap instead of repeated sorting brings construction down to $O(n \log n)$.
• Characters with equal frequency may be ordered either way without changing any code length; only which bit string each receives changes.

7. Binary Search Trees and Deletion

Problem

Build a binary search tree (BST) supporting insertion, inorder traversal, and node deletion.

Insertion

Compare recursively: smaller goes left, larger goes right, and an empty slot gets a new node.

TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    if (val < root->val)      root->left  = insert(root->left,  val);
    else if (val > root->val) root->right = insert(root->right, val);
    return root;   // duplicates are not inserted
}

Inorder traversal

An inorder walk of a BST yields an increasing sequence — the quickest sanity check that the tree was built correctly.

Deleting a node

Deletion is the easiest step to get wrong. There are three cases:

TreeNode* remove(TreeNode* root, int val) {
    if (!root) return nullptr;
    if (val < root->val)      root->left  = remove(root->left,  val);
    else if (val > root->val) root->right = remove(root->right, val);
    else {
        if (!root->left)  { auto t = root->right; delete root; return t; }
        if (!root->right) { auto t = root->left;  delete root; return t; }
        // two children: find the smallest node of the right subtree
        TreeNode* succ = root->right;
        while (succ->left) succ = succ->left;
        root->val   = succ->val;
        root->right = remove(root->right, succ->val);
    }
    return root;
}

Replacing with the largest node of the left subtree (the inorder predecessor) is equally valid.

Deleting the whole tree

Free nodes in postorder; releasing a parent before its children loses the pointers you still need.

8. Threaded Binary Trees

Problem

A binary tree with $n$ nodes has $2n$ pointer fields, but only $n-1$ edges are actually used, leaving $n+1$ null pointers wasted. Threading reuses those nulls to store the predecessor/successor under some traversal order, so traversal no longer needs a stack or recursion.

Data structure

struct Node {
    int data;
    Node *left, *right;
    int ltag, rtag;   // 0: points to a child; 1: it is a thread (predecessor/successor)
};

Algorithm (inorder threading)

Walk the tree inorder recursively while keeping a global pre pointer to the last visited node:

Node* pre = nullptr;

void thread(Node* p) {
    if (!p) return;
    thread(p->left);              // handle the left subtree first

    if (!p->left) {               // left child empty: point it at the predecessor
        p->left = pre;
        p->ltag = 1;
    }
    if (pre && !pre->right) {     // predecessor's right child empty: point it here
        pre->right = p;
        pre->rtag = 1;
    }

    pre = p;                      // advance the predecessor
    thread(p->right);             // then the right subtree
}

Key points

• left / right are overloaded: only ltag / rtag distinguish a child from a thread. Mistaking a thread for a child pointer leads to infinite loops.
• Inorder threading must recurse left first, then handle the current node, then recurse right; where pre = p sits determines what the threads point at.
• Preorder and postorder threading follow the same idea; what changes is when the current node is processed and the order of pre updates.
• A threaded tree traverses in $O(1)$ extra space, with no stack and no recursion.

9. Graph Storage: Adjacency Matrix vs. Adjacency List

Adjacency matrix

Store edges in a 2-D array adj[V][V]: adj[i][j] = 1 (or the edge weight) means an edge $i \to j$ exists.

• Pros: testing whether two vertices are adjacent is $O(1)$; simple to implement.
• Cons: space is always $O(V^2)$, which is very wasteful for sparse graphs; enumerating a vertex’s neighbours scans a whole row, $O(V)$.
• For an undirected graph the matrix is symmetric about the main diagonal.

Adjacency list

An array of lists: adj[i] holds every vertex adjacent to $i$.

vector<int> adj[MAX];          // each element is a linked list / dynamic array
void addEdge(int u, int v) {
    adj[u].push_back(v);
    adj[v].push_back(u);       // add the reverse edge for undirected graphs
}

• Pros: space $O(V + E)$, friendly to sparse graphs; enumerating neighbours touches only edges that exist.
• Cons: testing adjacency requires scanning a list, $O(V)$ worst case.
• In a directed graph, adj[u] holds outgoing edges, so computing in-degrees needs an extra pass or a separate reverse adjacency list.

Choosing between them

Checks when building a graph

After reading an edge $(u, v)$, validate $0 \le u, v < V$ to avoid out-of-range access; for unweighted graphs, do not add the same edge twice, as it distorts traversals and degree counts.

10. Kruskal and Minimum Spanning Trees

Problem

Find a spanning tree of minimum total weight in a weighted connected undirected graph.

Algorithm (greedy)

1. Sort all edges by weight ascending.
2. Consider each edge in turn: if its endpoints are not yet in the same set, add the edge to the tree and merge the two sets; otherwise adding it would create a cycle, so discard it.
3. Stop once $V-1$ edges have been chosen.

sort(edges.begin(), edges.end(),
     [](const Edge& a, const Edge& b) { return a.weight < b.weight; });

UnionFind uf(numNodes);
vector<Edge> result;
for (const Edge& e : edges) {
    if (uf.find(e.start) != uf.find(e.end)) {   // disconnected → safe to add
        result.push_back(e);
        uf.unite(e.start, e.end);
    }
}

Union-Find

Kruskal hinges on “are these two vertices already connected?”, which is exactly what a disjoint-set structure answers well:

• Find(x): locate the root of $x$’s set, which also tells whether two vertices share a set.
• Union(a, b): merge two sets.

Two optimisations together make the amortised cost nearly constant:

int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);   // path compression
    return parent[x];
}

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    if (rank[a] < rank[b]) swap(a, b);   // union by rank
    parent[b] = a;
    if (rank[a] == rank[b]) rank[a]++;
}

Key points

• Time complexity is $O(E \log E)$, dominated by the sort.
• Best suited to sparse graphs. For dense graphs Prim’s algorithm ($O(V^2)$, or $O(E \log V)$ with a heap) is usually faster.
• Sorting the edges and using Union-Find for cycle detection are the two moves at the heart of Kruskal.

11. Dijkstra and Single-Source Shortest Paths

Problem

Given a weighted graph and a source $s$, find the shortest distance from $s$ to every other vertex.

Algorithm (greedy + priority queue)

1. Set the source distance to 0 and all others to infinity.
2. Put (distance, vertex) pairs into a priority queue and repeatedly extract the vertex $u$ with the smallest distance — its shortest distance is now final.
3. Relax: for each neighbour $v$ of $u$, if $dist[u] + w(u,v) < dist[v]$ then update $dist[v]$ and push the new (dist[v], v) pair.
4. Repeat 2–3 until the queue is empty.

vector<int> dijkstra(const vector<vector<int>>& g, int src) {
    int n = g.size();
    vector<int> dist(n, INF);
    // min-heap: the smallest element always sits at the front
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;        // stale entry, skip it
        for (int v = 0; v < n; v++) {
            if (g[u][v] == 0) continue;   // 0 means no direct edge
            if (dist[u] + g[u][v] < dist[v]) {
                dist[v] = dist[u] + g[u][v];
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

Key points

• Negative edge weights are not supported. Dijkstra’s correctness relies on an extracted vertex’s distance never decreasing again, and negative edges break that assumption; use Bellman-Ford or SPFA instead.
• With an adjacency matrix the inner scan is $O(V)$ and the total is $O(V^2)$; switching to an adjacency list with a priority queue brings it to $O(E \log V)$.
• A vertex may be pushed several times, so skip stale entries by checking d > dist[u] on pop.
• Using 0 to mean “no edge” is a convention; if zero-weight edges are legitimate, use a separate marker or an adjacency list.

12. Critical Paths

Problem

In an AON (activity-on-node) network, where each vertex is an activity with a duration and precedence constraints, find the sequence of activities that determines the project’s total duration.

• Earliest start (ES): the soonest an activity can begin.
• Latest start (LS): the latest it may begin without delaying the whole project.
• Slack: $LS - ES$. Activities with zero slack are the critical activities, and together they form the critical path.

Forward pass for ES

Process the topological order from the start events towards the end:

An initial activity with no predecessors gets $ES = 0$. The project duration is $T = \max_v (ES[v] + duration[v])$.

void calcEarliest() {
    // must process in topological order, or a predecessor's ES is not ready yet
    for (int u : topoOrder) {
        for (int v : activities[u].next) {
            earliest[v] = max(earliest[v], earliest[u] + activities[u].duration);
        }
    }
}

Backward pass for LS

Walk the reverse topological order back from the end events:

A terminal activity with no successors has $LS = ES = T - duration$. (Equivalently, set $LF[\cdot] = T$, so $LS = LF - duration$ and $LF[u] = \min_{v \in succ(u)} LS[v]$.)

void calcLatest() {
    for (int u : reverseTopoOrder) {
        for (int v : activities[u].next) {
            latest[u] = min(latest[u], latest[v] - activities[u].duration);
        }
    }
}

Key points

• Both passes must proceed strictly in topological order, or the predecessors/successors being read have not been computed yet.
• Do not identify start events by “the adjacency list is empty” — an empty adjacency list marks an end event (out-degree 0). Start events are those with in-degree 0; getting this backwards invalidates the whole computation.
• There may be more than one critical path; mark every activity whose slack is 0.
• To shorten the project you can only compress critical activities; compressing the others achieves nothing.

Summary