Introduction to DSA

Prerequisites: basic programming (variables, loops, functions).

What you will learn

What data structures and algorithms are, and how an abstract data type differs from its implementation.

How to classify data structures and recognise the common algorithmic tasks.

How to argue that an algorithm is correct using preconditions, loop invariants and induction.

Prerequisites: basic programming (variables, loops, functions). Every program in this course is complete C++17 and was compiled and run; the output printed under it is the real output.

1.1 What is a data structure?

A data structure organizes data so it can be stored, accessed, modified, and searched efficiently. Examples: arrays for indexed access, stacks for last-in-first-out processing, and hash tables for fast key lookup.

Analogy: a library could pile every book on the floor (easy to add, slow to find), shelve them alphabetically (fast to find by title, slow to insert in the middle), or keep a card index (fast lookup by several keys, extra space). Each choice makes some operations cheap and others expensive — that trade-off is the heart of the subject.

1.2 What is an algorithm?

An algorithm is a finite sequence of well-defined steps that transforms input into output. It should be correct, terminate under its stated assumptions, and use resources reasonably.

1.3 Data types, ADTs, and implementations

Data type: defines a set of values and permitted operations.

Abstract Data Type (ADT): specifies behavior without prescribing implementation. A stack ADT supports push, pop, and top; it may be implemented using an array or linked list.

Data structure: a concrete representation and implementation of data.

Text equivalent: one abstract interface can have several implementations; users of the ADT see the same operations, while the implementation decides memory layout and constant factors.

flowchart TD
  ADT[Stack ADT: push, pop, top, empty] --> A1[Array-backed stack]
  ADT --> A2[Linked-list-backed stack]
  A1 --> C1[Contiguous memory, amortized O1 push]
  A2 --> C2[One node per element, O1 push, extra pointer per node]

1.4 Classifying data structures

Linear: array, linked list, stack, queue, deque.

Non-linear: tree, heap, graph, trie.

Hash-based: hash table / hash map / hash set.

Static versus dynamic size.

Homogeneous versus heterogeneous representations.

External-memory structures: B-tree/B+ tree and related indexes.

1.5 Typical algorithmic tasks

Searching, sorting, traversal, insertion, deletion, counting, aggregation, optimization, scheduling, pathfinding, matching, and query processing.

1.6 Correctness basics

Preconditions and postconditions.

Base cases and progress toward termination.

Counterexamples and edge cases.

Proof by induction for recursive algorithms.

A loop invariant is a statement that is true before the loop starts, stays true after every iteration, and — combined with the exit condition — gives the result you want. Proving it has three parts: *initialisation* (true before the first iteration), *maintenance* (one iteration keeps it true), and *termination* (when the loop stops, the invariant implies correctness).

Worked example: find the maximum The program below contains the function exactly as specified, prints the invariant after each step (the dry run), and checks the edge case of an empty input.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

The loop invariant is: after processing the first k values, best is the maximum of those k values. Time: O(n); auxiliary space: O(1).

Initialisation: before the loop, best = a[0], the maximum of the first element.

Maintenance: if x > best, the new maximum is x; otherwise it is unchanged.

Termination: after all n values, best is the maximum of the whole array.

Common mistake: initialising best = 0. For an all-negative array such as {-5, -2} that returns 0, a value not in the input. Starting from a[0] (or INT_MIN with care) avoids the bug; the empty case must be decided explicitly.

#include <bits/stdc++.h>
using namespace std;

int maxValue(const vector<int>& a) {
    if (a.empty()) throw invalid_argument("empty input");
    int best = a[0];
    for (int x : a) {
        if (x > best) best = x;
    }
    return best;
}

int main() {
    vector<int> a = {3, -1, 7, 7, 2};
    // dry run: after processing the first k values, best == max of those k values
    int best = a[0];
    for (size_t k = 0; k < a.size(); ++k) {
        if (a[k] > best) best = a[k];
        cout << "k=" << k + 1 << " read " << setw(2) << a[k] << "  best=" << best << '\n';
    }
    cout << "maxValue = " << maxValue(a) << '\n';
    cout << "single element: " << maxValue({-5}) << '\n';
    try {
        maxValue({});
    } catch (const invalid_argument& e) {
        cout << "empty input: invalid_argument(\"" << e.what() << "\")\n";
    }
}

k=1 read  3  best=3
k=2 read -1  best=3
k=3 read  7  best=7
k=4 read  7  best=7
k=5 read  2  best=7
maxValue = 7
single element: -5
empty input: invalid_argument("empty input")

Practice

Easy: return the index of the first maximum; state the invariant.

Medium: return both the minimum and the maximum using fewer than 2n comparisons (hint: process elements in pairs).

Hard: prove by induction that a recursive max(a, n) = max(max(a, n-1), a[n-1]) is correct, and state its stack-space cost.

Quiz

? Which statement describes an abstract data type?
- A specific memory layout such as a contiguous array :: That is a data structure (an implementation).
+ A set of operations and their behaviour, independent of implementation :: A stack ADT can be backed by an array or a linked list.
- A primitive type such as int :: A data type, not an ADT.
- A sorting algorithm :: An algorithm, not a type.

? `best` is initialised to `0` instead of `a[0]`. Which input exposes the bug?
- `{1, 2, 3}` :: Correct answer 3 is still found.
+ `{-5, -2}` :: The function would return 0, which is not in the array.
- `{0}` :: Coincidentally correct.
- `{7, 7}` :: Correct answer 7 is found.

? Which three parts make up a loop-invariant proof? (select all that apply)
+ Initialisation :: True before the first iteration.
+ Maintenance :: Each iteration preserves it.
+ Termination :: At exit, the invariant implies the result.
- Memoisation :: Unrelated technique.