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