1/60
Comprehensive vocabulary flashcards covering fundamental data structures, algorithms, asymptotic analysis, trees, heaps, hash tables, graph algorithms, greedy methods, divide-and-conquer, and randomized algorithms.
Abstract Data Type (ADT)
A formal specification of a data type defined purely in terms of its data items and associated operations from the user's perspective, independent of its concrete programming implementation.
Big-Oh Notation (O)
An asymptotic upper bound stating that T(n)=O(f(n)) if there exist constants c>0 and n0>0 such that T(n)≤c⋅f(n) for all n>n0.
Big-Omega Notation (Ω)
An asymptotic lower bound stating that T(n)=Ω(f(n)) if there exist constants c>0 and n0>0 such that T(n)≥c⋅f(n) for all n>n0.
Big-Theta Notation (Θ)
An asymptotically tight bound stating that T(n)=Θ(f(n)) if and only if T(n)=O(f(n)) and T(n)=Ω(f(n)).
Polynomial Time Efficiency
The formal criterion that an algorithm is efficient if its worst-case step count on an input of size n is bounded by a polynomial p(n)=adnd+⋯+a1n+a0.
Positional List ADT
A list ADT that stores elements at abstract locations called positions, where each position continues to reference the same entry regardless of subsequent insertions or deletions elsewhere in the collection.
Doubly Linked List
A concrete data structure consisting of a sequence of nodes where each node stores an element and references to both its previous (prev) and next (next) nodes, bounded by header and trailer sentinel nodes.
Stack ADT
A sequential collection following Last-In-First-Out (LIFO) semantics, where elements are inserted via push(e) and removed via pop() at the top position.
Queue ADT
A sequential collection following First-In-First-Out (FIFO) semantics, supporting element insertion at the rear via enqueue(e) and element removal from the front via dequeue().
Dynamic Iterator vs. Snapshot Iterator
A snapshot iterator freezes the contents of the data structure at the moment of creation, whereas a dynamic iterator actively reflects modifications made to the collection during iteration.
Rooted Tree
A hierarchical data structure consisting of nodes with parent-child relationships containing a unique root node without a parent, where every other node has a unique parent and no cycles exist.
Internal Node vs. External Node
An internal node is any tree node that has at least one child, whereas an external node (or leaf) has zero children.
Depth of a Node vs. Height of a Tree
The depth of a node is the number of ancestors excluding itself, while the height of a tree is the maximum depth among all nodes in the tree.
Proper Binary Tree
An ordered tree in which each internal node has at most two children, labeled respectively as left and right children, such that every internal node has exactly two children.

Binary Tree Node (Linked Structure)
A concrete representation of a binary tree node containing fields for its stored element, a pointer to its parent node, a pointer to its left child, and a pointer to its right child.

General Tree Node (Linked Structure)
A concrete representation of a general tree node containing fields for its stored element, a reference to its parent node, and a linear sequence/collection of references to all its children.
Preorder Traversal
A tree traversal strategy that visits the current node v before recursively traversing the subtrees rooted at each of its children.
Postorder Traversal
A tree traversal strategy that recursively visits the subtrees rooted at each child of node v before performing the visit operation on node v itself.
Inorder Traversal
A traversal specific to binary trees that recursively visits the left subtree of node v, then visits node v, and finally recursively visits the right subtree of node v.
Euler Tour Traversal
A generic binary tree walk that circumnavigates the perimeter of the tree, visiting each node up to three times: on the left (preorder), from below (inorder), and on the right (postorder).
Binary Search Tree (BST) Property
The ordering condition for a binary tree stating that for every node v, every key in the left subtree of v is strictly less than key(v), and every key in the right subtree of v is strictly greater than key(v).
Inorder Successor (BST Deletion)
The internal node holding the smallest key in the right subtree of node w, used to replace the entry of w when deleting a node possessing two internal children.
AVL Tree
A rank-balanced binary search tree in which the rank of every node represents its subtree height, satisfying the constraint that the heights of the two children of every internal node differ by at most 1.

Trinode Restructuring (Single Rotation)
A local tree rebalancing operation on nodes x, y, and z that restores the AVL balance constraint in O(1) time by rotating the middle-value node to become the parent of the other two.
Map ADT
A searchable collection of unique key-value entries supporting lookup (get(k)), insertion or value replacement (put(k, v)), and deletion (remove(k)).
Priority Queue ADT
An abstract data type storing key-value items that grants access and deletion exclusively to the entry with the minimum key via min() and remove_min().

Min-Heap
A binary tree storing items that satisfies the Heap-Order property (key(v)≥key(parent(v)) for all v=root) and the Complete Binary Tree property, ensuring a height of O(logn).
Upheap vs. Downheap
Upheap restores the heap-order property by swapping a key along an upward path to the root after insertion; downheap restores it by swapping a key downward with its smaller child after removal.
Heap-Sort
A comparison-based sorting algorithm that inserts n elements into a heap priority queue and sequentially executes n remove_min() operations, running in O(nlogn) time.
Array Representation of a Heap
A compact array layout for a heap of size n where the root is at index 0, and for any node at index i, its left child is at 2i+1, its right child is at 2i+2, and its parent is at ⌊(i−1)/2⌋.
Load Factor (α)
The ratio α=Nn representing the average number of entries per bucket in a hash table, where n is the number of stored keys and N is the total array capacity.
Separate Chaining
A collision resolution mechanism where each hash table cell points to an external linked list containing all key-value entries mapped to that bucket index.
Linear Probing
An open addressing technique that resolves collisions by systematically probing consecutive table cells circularly until an empty slot or matching key is found.
DEFUNCT Sentinel
A marker placed in an open addressing hash table slot upon deletion, ensuring that subsequent search probes continue traversing rather than halting prematurely as they would at an empty slot.
Cuckoo Hashing
An open addressing scheme employing two tables and two hash functions where each key has exactly two permitted locations, achieving worst-case O(1) search and removal by evicting existing occupants upon collision.

Set ADT vs. MultiSet (Bag)
A Set ADT stores an unordered collection of unique elements without duplicates, whereas a MultiSet (Bag) allows duplicate elements and tracks the occurrence count of each element.
Adjacency List Structure
A graph storage representation using O(n+m) space where each vertex maintains an incidence list of its connected edges, allowing traversal of incident edges in O(deg(v)) time.

Adjacency Matrix Structure
A graph storage representation using an n×n 2D array where entry A[u,v] stores an edge reference or null, requiring O(n2) space and supporting O(1) edge lookups.
Depth-First Search (DFS)
A graph traversal running in O(n+m) time that follows outgoing edges leading to unexplored vertices as deeply as possible before backtracking, categorizing edges into tree edges and back edges.
Breadth-First Search (BFS)
A graph traversal running in O(n+m) time that visits vertices in successive concentric layers of increasing path distance from a starting vertex s, classifying non-tree edges as cross edges.
Cut Edge (Bridge)
An edge in a connected graph whose removal strictly increases the total number of connected components, thereby disconnecting the graph.
Edge Relaxation
The fundamental update step in shortest-path algorithms that adjusts the tentative distance to vertex z via edge e=(u,z) using the rule D[z]←min{D[z],D[u]+w(u,z)}.
Dijkstra’s Algorithm
A greedy algorithm that computes the shortest path from a start vertex s to all other vertices in a graph with non-negative edge weights, running in O(mlogn) time using a min-heap.
Cut Property (MST)
The theorem establishing that for any subset of vertices S, the minimum-cost edge with exactly one endpoint in S and one in V∖S belongs to every minimum spanning tree of the graph.
Cycle Property (MST)
The theorem establishing that for any cycle C in a graph, the edge with the strictly maximum cost in C cannot belong to any minimum spanning tree.
Prim's Algorithm
A greedy minimum spanning tree algorithm that grows a single tree by iteratively attaching the minimum-weight edge connecting a vertex in the visited set to a vertex outside it, running in O(mlogn) time with a binary heap.
Kruskal's Algorithm
A minimum spanning tree algorithm that considers all edges in non-decreasing order of cost, inserting each edge into the spanning forest if and only if it does not form a cycle, using a Union-Find data structure.
Union-Find ADT
A data structure maintaining an evolving partition of elements into disjoint sets, supporting operations make_sets(A), find(u) (returning the set identifier for u), and union(u, v) (merging the sets of u and v).
Fractional Knapsack Problem
A resource allocation problem where arbitrary fractions 0≤xi≤wi of items can be packed to maximize total benefit within weight capacity W, solved optimally by greedily picking items with the largest benefit-to-weight ratio wibi.
Interval Partitioning Problem
A task scheduling problem aiming to find the minimum number of classrooms required to schedule n lectures without overlaps, solved optimally in O(nlogn) time by greedily assigning lectures ordered by increasing start time.
Prefix Code
A binary character code where no codeword is a prefix of any other codeword, allowing unambiguous decoding and direct representation as leaf nodes of an encoding tree.
Huffman’s Algorithm
A greedy bottom-up algorithm running in O(n+dlogd) time that builds an optimal prefix code tree by repeatedly extracting and merging the two trees with the lowest frequencies using a priority queue.
Merge-Sort
A divide-and-conquer sorting algorithm that splits an array of size n into two halves, recursively sorts each half, and merges them in O(n) time, resulting in an overall time complexity of O(nlogn).
Comparison Sorting Lower Bound
The information-theoretic limit proving that any comparison-based sorting algorithm requires at least Ω(nlogn) comparisons in the worst case, derived from the log2(n!) height of a decision tree with n! leaves.
Maxima-Set (Pareto Frontier)
The set of points in a 2D plane that are not dominated by any other point, where point q dominates p if q.x≥p.x and q.y≥p.y (with q=p); computed via divide-and-conquer in O(nlogn) time.
Karatsuba Integer Multiplication
A divide-and-conquer algorithm that multiplies two n-bit integers using only 3 recursive multiplications of size n/2 instead of 4, achieving a recurrence of T(n)=3T(n/2)+O(n) and a running time of O(nlog23)≈O(n1.585).
Median-of-Medians Selection
A deterministic divide-and-conquer algorithm that finds the kth smallest element in an unsorted array in O(n) worst-case time by partitioning elements into groups of 5 and recursively choosing the median of their medians as a balanced pivot.
Fisher-Yates Shuffle
An unbiased randomized algorithm that permutes an array of n elements uniformly at random in O(n) time by iterating through index i from 0 to n−1 and swapping A[i] with a randomly chosen element from index range {i,…,n−1}.

Skip List Node
A structural node in a skip list maintaining four directional references: before(p) and after(p) on the same horizontal level, and above(p) and below(p) within the same vertical tower.
Skip List
A randomized layered linked-list data structure implementing the Map ADT where towers grow based on independent coin flips, providing O(logn) expected time for search, insertion, and deletion using O(n) expected space.
Discrete Logarithm Problem
The cryptographic hard problem of recovering the integer exponent x given a cyclic group generator g, prime p, and value Y=gxmodp, forming the security foundation of Diffie-Hellman key exchange.