Appendix D — Appendix D: Glossary

Appendix D: Glossary

Quick-reference definitions for terms used in this book. Cross-references in italic.

Abstract class — a class with at least one pure virtual function. Cannot be instantiated directly.

Adjacency list — graph representation where each vertex has a list of its neighbors. O(V + E) space.

Adjacency matrix — graph representation as a V×V grid. O(V²) space.

Amortized analysis — averaging the cost of operations over a sequence; e.g., vector::push_back is amortized O(1).

AVL tree — self-balancing BST with the strict invariant that left/right subtree heights differ by at most 1.

Backtracking — DFS plus undoing state on return. Used for constraint satisfaction (8-queens, sudoku).

Balance factor — for an AVL node, height(left) - height(right).

Base case — the smallest version of a recursive problem, solved directly.

Big-O — upper bound on growth rate. f(n) = O(g(n)) if f ≤ c·g for large n.

Big-Omega (Ω) — lower bound on growth rate.

Big-Theta (Θ) — tight bound. Both O and Ω.

BFS — Breadth-First Search. Layer-by-layer traversal using a queue. O(V + E).

BST — Binary Search Tree. Left subtree all less, right all greater.

Class — a user-defined type with fields and methods.

Compile — translate source code to machine code (or intermediate code).

Const correctness — using const to mark read-only parameters and methods.

Copy constructor — T(const T&). Creates a new object from an existing one.

Copy assignment — T& operator=(const T&). Replaces the contents of an existing object.

DAG — Directed Acyclic Graph. Used for topological sort.

Deep copy — copies the contents a pointer points to, not just the pointer.

Destructor — ~T(). Runs when an object’s lifetime ends.

DFS — Depth-First Search. Recursive (or stack-based) traversal that goes deep before backtracking. O(V + E).

DFA — Deterministic Finite Automaton. Recognizes regular languages.

Dijkstra’s algorithm — shortest path in a graph with non-negative edge weights. O((V + E) log V).

DP — Dynamic Programming. Memoized recursion with overlapping subproblems and optimal substructure.

Edit distance — minimum number of insert/delete/replace edits to convert one string to another.

Friend — a function or class granted access to another class’s private members.

Hash function — maps a key to an array index. Good ones distribute uniformly.

Hash table — array-backed map using a hash function. Average O(1) lookup.

Heap — complete binary tree with the heap property (parent ≥ children for max-heap). Backed by an array.

Heapify — build a heap from an arbitrary array in O(n).

Inductive hypothesis — assumption that the statement holds for k; used to prove k+1.

Inheritance — declaring one class as derived from another, gaining its members.

In-order traversal — visit left, then node, then right. On a BST, produces sorted output.

Iterator — object that traverses a container, exposing * to read, ++ to advance, != to compare.

Leaf — a node with no children.

Linked list — chain of nodes, each pointing to the next.

Load factor — items / buckets in a hash table. Triggers rehash above ~0.7.

LCS — Longest Common Subsequence. 2D DP, O(mn).

LIS — Longest Increasing Subsequence. O(n²) DP or O(n log n) patience-sorting.

Master Theorem — closed-form for solving recurrences of the form T(n) = aT(n/b) + f(n).

Member initializer list — colon syntax for initializing fields in a constructor.

Memoization — top-down DP: recursive solution + cache.

Merge sort — divide-and-conquer sort. O(n log n), O(n) space, stable.

MST — Minimum Spanning Tree. Prim’s or Kruskal’s algorithm.

NFA — Nondeterministic Finite Automaton. Equivalent in power to DFA.

NP — class of problems whose solutions can be verified in polynomial time.

NP-complete — the “hardest” problems in NP. 3-SAT, vertex cover, etc.

Nullptr — typed null pointer (C++11). Prefer over NULL.

Open addressing — collision resolution by probing for the next empty slot.

Operator overloading — defining operators (+, ==, <<) for user types.

P — class of problems solvable in polynomial time.

Pointer — variable holding a memory address.

Polymorphism — runtime dispatch of methods based on object’s actual type.

Post-order traversal — visit left, right, then node. Used for tree deletion.

Pre-order traversal — visit node, then left, then right. Used for tree serialization.

Prefix code — code where no codeword is a prefix of another. Required for Huffman.

Priority queue — abstract data type with push and pop-min (or pop-max). Usually backed by a heap.

Pure virtual — virtual void f() = 0;. Forces derived classes to implement.

Quicksort — divide-and-conquer sort. Average O(n log n), worst O(n²), in place.

RAII — Resource Acquisition Is Initialization. Tying resource lifetime to object lifetime.

Rule of Three — if you write any of (destructor, copy ctor, copy assignment), write all three.

Rule of Five — Rule of Three + move ctor + move assignment (C++11).

Recurrence relation — equation expressing T(n) in terms of smaller values.

Recursion — function that calls itself.

Red-black tree — self-balancing BST using node colors. STL map/set.

Reference — alias for another variable. int& r = x;.

Rotation — restructuring operation for self-balancing trees (right, left, double).

Separate chaining — collision resolution by storing a list of items per bucket.

Shallow copy — copies pointers, not what they point to.

Sift-down — restore heap property by moving a value toward leaves.

Sift-up — restore heap property by moving a value toward the root.

Singleton — pattern guaranteeing exactly one instance of a class.

Stack frame — per-call activation record on the call stack.

Strategy pattern — replacing type-switches with polymorphism via injected behavior.

Strong induction — assume P(j) for all j ≤ k; prove P(k+1).

Subset construction — algorithm converting an NFA to an equivalent DFA.

Template — generic type/function parameterized by a type.

Topological sort — linear ordering of a DAG where every edge u → v has u before v.

Tree — connected undirected graph with no cycles, or rooted hierarchical structure.

Turing machine — abstract computation model with a tape, head, and transition function.

Union-find (DSU) — data structure tracking disjoint sets with find and unite. Used in Kruskal’s.

Vector — C++ dynamic array.

Virtual function — method that can be overridden in derived classes; dispatched via the vtable.

Vtable — per-class table of function pointers used for virtual dispatch.

Weak induction — assume P(k); prove P(k+1).