Data Structures – Exam Review Vocabulary

Vocabulary flashcards covering the key data-structure and algorithm concepts present in the lecture notes. They include definitions, properties, and typical complexities to aid exam preparation.

Insertion Sort

Comparison‐based sort that scans from left to right, inserting each element into its correct position among the already-sorted prefix; runs in Θ(n²) worst case, Θ(n) when array is almost sorted, and is in-place and stable.

Merge Sort

Divide-and-conquer comparison sort that recursively splits the array, sorts halves, then merges; runs in Θ(n log n) worst case, is stable, but not in-place (needs Θ(n) extra space).

Heap Sort

Sort that first builds a max-heap in Θ(n) time and repeatedly extracts the maximum into the end of the array; in-place, Θ(n log n) worst case, not stable.

Quick Sort

Recursive divide-and-conquer sort that partitions around a pivot so smaller keys precede it; average Θ(n log n), worst Θ(n²); in-place, not stable.

Pivot (Quick Sort)

Element chosen each partitioning step; its quality determines Quick-Sort’s running time—median yields Θ(n log n), extreme value yields Θ(n²).

Partition Procedure

Linear Θ(n) subroutine that rearranges an array so that elements < pivot come first, pivot is placed, and elements > pivot follow.

Stable Sort

Sorting algorithm that preserves the relative order of keys with equal value (e.g., Merge Sort, Counting Sort).

In-Place Algorithm

Algorithm that sorts or processes data using only O(1) or O(log n) extra memory (e.g., Heap Sort, Quick Sort).

Counting Sort

Linear-time stable sort for n integers in range 0…k−1; uses two auxiliary arrays C(k) and B(n); runs in Θ(n+k).

Radix Sort

Sorts integers by processing d digits least-significant to most-significant with a stable inner sort (often Counting Sort); runs in Θ(d(n+k)).

Bucket Sort

Linear expected-time sort for n real numbers assumed uniformly distributed in (0,1]; places items into n buckets, sorts each bucket, concatenates.

Comparison-Based Sort

Family of sorts whose decisions are based only on key comparisons; has Ω(n log n) lower bound in worst case.

Adjacency Matrix

|V|×|V| boolean matrix where entry (i,j)=1 iff edge (i,j) exists; O(V²) space; O(1) edge lookup, O(V) neighbour scan.

Adjacency List

Array of |V| linked lists, each storing neighbours of a vertex; O(V+E) space; neighbour scan O(deg(v)); edge check O(deg(v)).

Breadth-First Search (BFS)

Graph traversal using a queue; discovers vertices in increasing distance (edges) from source; runs in Θ(V+E).

Depth-First Search (DFS)

Graph traversal that explores as deep as possible along each branch before backtracking; uses recursion or stack; Θ(V+E).

Tree Edge (DFS)

Edge that first discovers a new vertex during DFS and becomes part of the DFS forest.

Back Edge

DFS edge from a vertex to one of its ancestors; indicates a cycle in undirected graphs.

Forward Edge

DFS edge from a vertex to a descendant already discovered (in directed graphs only).

Cross Edge

DFS edge connecting vertices in different subtrees or branches; neither tree, back, nor forward edge.

Topological Sort

Ordering of vertices of a DAG so every directed edge (u,v) goes from earlier to later; obtained by DFS finishing-time decreasing order.

Minimum Spanning Tree (MST)

Subset of edges connecting all vertices with minimum total weight; contains |V|−1 edges and may not be unique.

Safe Edge

Edge that can be added to a partial MST without violating minimality—does not create a cycle with chosen edges.

Kruskal’s Algorithm

Greedy MST algorithm: sort edges by weight, repeatedly add lightest edge that connects two different components using Union-Find; runs in Θ(E log V).

Union–Find (Disjoint Set Forest)

Data structure supporting Make-Set, Find-Set, and Union with near-constant amortized time using union-by-rank and path compression.

Prim’s Algorithm

Greedy MST algorithm that grows a tree from an arbitrary root by repeatedly adding the lightest edge crossing the current cloud; binary-heap version runs in Θ(E log V).

Binary Heap

Array-based complete binary tree satisfying heap property (parent ≥ children for max-heap); supports insert, extract-max/min in Θ(log n).

Max-Heapify

Subroutine that fixes a single node violating the max-heap property by bubbling it down; Θ(log n).

Extract-Min / Extract-Max

Heap operation removing and returning root, then heapifying; Θ(log n).

Binary Search Tree (BST)

Binary tree where left subtree keys < node < right subtree keys; supports search, insert, delete in Θ(h) where h is height.

Inorder Traversal

BST traversal visiting Left–Node–Right; outputs keys in sorted order.

AVL Tree

Self-balancing BST where heights of left and right subtrees differ by ≤1 at every node; guarantees Θ(log n) operations.

Rotation (AVL)

Constant-time local restructuring (single or double) used to restore AVL balance after insert/delete.

B-Tree

Multi-way balanced search tree optimized for disks; each node holds between t−1 and 2t−1 keys; all leaves at same depth.

Minimum Degree t (B-Tree)

Parameter controlling B-Tree node capacity; each non-root node stores at least t−1 keys and at most 2t−1.

SplitChild (B-Tree)

Operation that splits a full child during insertion: middle key moves up, child divided into two nodes.

Hash Table

Dictionary using a hash function h(k) to map keys to buckets; expected Θ(1) search/insert/delete under uniform hashing.

Load Factor (α)

n/m, the average number of keys per bucket; determines expected performance of hash tables.

Chaining (Hashing)

Collision resolution storing all keys that hash to same index in a linked list; expected Θ(1+α) search time.

Open Addressing

Collision resolution that stores all keys inside the table itself, probing alternative slots when collisions occur.

Linear Probing

Open addressing strategy that scans sequentially (h(k)+i) mod m for first empty slot; suffers from clustering.

Quadratic Probing

Open addressing that probes h(k)+c₁i+c₂i² mod m; reduces primary clustering but still limited permutations.

Double Hashing

Open addressing that uses second hash g(k) as probe step: h(k)+i·g(k) mod m; provides up to m permutations, minimal clustering.

Skip List

Probabilistic layered linked lists where each element appears in higher levels with probability ½; expected Θ(log n) search, insert, delete.

Linked List

Sequence of nodes where each points to the next; supports O(1) insert/delete at known position, O(n) search.

Queue

FIFO abstract data type supporting enqueue at rear and dequeue from front; can be array or linked list.

Stack

LIFO abstract data type supporting push and pop at top; array or linked list implementation.

Amortized Analysis

Technique that averages the running time of an operation over a sequence, giving tighter bounds than worst-case per operation.

Priority Queue

ADT storing elements with keys, supporting insert and extract-max/min; often implemented with heaps.

Disjoint Set (Set of Disjoint Sets)

Collection of non-overlapping sets with Make-Set, Union, and Find operations; enables cycle detection in Kruskal.

Union by Rank

Heuristic that attaches the shorter (or lower rank) tree under the taller one during Union to limit height.

Path Compression

Find-Set heuristic that flattens tree structure by making each traversed node point directly to root.

Randomized-Select

Quickselect algorithm picking random pivots to find the i-th order statistic in expected Θ(n) time.

Deterministic Select (Median-of-Medians)

Selection algorithm grouping by fives to choose good pivot; guarantees Θ(n) worst-case time.

Bucket (Hash/Sort)

Container used to collect keys that share a property (same hash value or range) before further processing.

Node Depth

Number of edges from the root to the node in a tree.

Tree Height

Maximum depth among all nodes; height of an empty tree is −1.

Full Binary Tree

Binary tree where every node has either 0 or 2 children.

Perfect Binary Tree

Binary tree that is both full and all leaves are at the same depth.

Heap Sort Worst-Case Time

Always Θ(n log n) because each of n extracts costs Θ(log n).

Counting Sort Complexity

Θ(n+k) time and Θ(n+k) space, linear when k=O(n).

Radix Sort Complexity

Θ(d(n+k)) where d is number of digits and k base size; linear when d and k are O(1) wrt n.

Bucket Sort Assumption

Inputs are uniformly distributed over (0,1] (or known finite range) so expected bucket sizes are constant.

BFS Complexity

Visits each vertex and edge once: Θ(V+E).

DFS Complexity

Also Θ(V+E) since each edge explored once.

Skip List Expected Complexity

Search, insert, delete run in Θ(log n) on average; space O(n).

Hash Table Expected Search Time

Under uniform hashing, Θ(1) average for both successful and unsuccessful searches when α=O(1).

Heap Operations Complexity

Insert and extract-max/min Θ(log n); peek Θ(1); build-heap Θ(n).

Prim with Binary Heap

Runs in Θ(E log V) using binary heap for priority queue of vertex keys.

Kruskal Complexity

Θ(E log E) for sorting plus near-linear Union-Find operations; simplifies to Θ(E log V).

Dijkstra’s Algorithm

Shortest-path algorithm for non-negative weights using a priority queue; binary-heap implementation runs in Θ(E log V).