Data Structures and Algorithms with C Dictionary

Terms used in the course, each with a short definition and the chapter where it is explained. The chapter column links to that chapter's lecture notes.

TermDefinitionChapter
abstract data type (ADT)A type defined by its values and operations alone, independently of how they are implemented.1 · Introduction and Algorithm Analysis
Ackermann functionA very fast-growing recursive function whose inverse, α(n), bounds the cost of union-find.16 · Sets and Union-Find
activity networkA directed graph that shows the tasks of a project and the precedence relations among them.18 · Shortest Paths and Activity Networks
activity on edge (AOE) networkAn activity network in which the tasks are edges and the events are vertices.18 · Shortest Paths and Activity Networks
activity on vertex (AOV) networkAn activity network in which the tasks are vertices and the precedence relations are edges.18 · Shortest Paths and Activity Networks
address-of operator (&)The unary operator that yields the address of an object.4 · Linked Lists
adjacency listA representation that keeps, for each vertex, a linked list of its neighbors.15 · Graphs
adjacency matrixAn n×n matrix in which a[i][j] = 1 if there is an edge between i and j.15 · Graphs
adjacency multilistA representation of an undirected graph in which each edge is stored once but appears in the edge lists of both of its endpoints.15 · Graphs
adjacentTwo vertices that are joined by an edge.15 · Graphs
aggregate analysisAn analysis that counts the total cost of all the steps together rather than of a single step; one way of doing amortized analysis.8 · Stack and Queue Applications
algorithmA method that solves a problem in a finite number of precise and effective steps.1 · Introduction and Algorithm Analysis
alignmentThe compiler's placement of fields at addresses that are multiples of a given size; it affects the size of structures.2 · Arrays and Structures
all-pairs shortest pathsThe problem of finding a shortest path between every pair of vertices.18 · Shortest Paths and Activity Networks
amortized analysisFinding the cost per operation by dividing the total cost of a sequence of operations by the number of operations.1 · Introduction and Algorithm Analysis
ancestorAny node on the path from the root to a given node.10 · Trees
arrayA structure whose elements have the same type, are stored consecutively in memory, and are accessed by index.2 · Arrays and Structures
arrow operator (->)The operator that accesses a structure field through a pointer: p->field is the same as (*p).field.1 · Introduction and Algorithm Analysis
associativityThe rule that decides whether operators of equal precedence are applied from left to right or from right to left.8 · Stack and Queue Applications
asymptotic notationA notation that compares the growth rates of functions for large n by discarding constant factors.1 · Introduction and Algorithm Analysis
available space listA list that keeps freed nodes so that they can be reused (avail).4 · Linked Lists
average caseThe expected running time over a given distribution of inputs.1 · Introduction and Algorithm Analysis
AVL treeA search tree that keeps the height difference of the two subtrees of every node at most 1.11 · Search Trees
back edgeIn DFS, an edge to an already marked ancestor other than the parent; it shows that the graph contains a cycle.15 · Graphs
backtrackingA search method that extends a partial solution step by step and undoes the last choice when it reaches a dead end.3 · Recursion, Binary Search and Backtracking
balance factorThe height of the left subtree minus the height of the right subtree.11 · Search Trees
balanced parenthesesChecking with a stack whether every opening parenthesis is closed by one of the right type and in the right order.6 · Stacks
balanced treeA search tree whose height is kept at O(lg n).10 · Trees
band matrixA matrix whose nonzero elements lie in a band around the main diagonal.2 · Arrays and Structures
base caseThe case in which a recursion returns a result directly, without calling itself.1 · Introduction and Algorithm Analysis
Bellman-Ford algorithmA shortest-path algorithm that relaxes all edges n − 1 times and allows negative weights.18 · Shortest Paths and Activity Networks
best caseThe running time for the input that needs the fewest steps among inputs of the same size.1 · Introduction and Algorithm Analysis
Big OAn upper bound: f(n) = O(g(n)) if f(n) ≤ c·g(n) for all n ≥ n₀.1 · Introduction and Algorithm Analysis
Big OmegaA lower bound: f(n) = Ω(g(n)) if f(n) ≥ c·g(n) for all n ≥ n₀.1 · Introduction and Algorithm Analysis
Big ThetaA tight bound: f(n) = Θ(g(n)) if f(n) is both O(g(n)) and Ω(g(n)).1 · Introduction and Algorithm Analysis
binary searchSearching a sorted array by halving the range at every step; O(lg n).3 · Recursion, Binary Search and Backtracking
binary search tree (BST)A binary tree in which, at every node, the keys in the left subtree are smaller and those in the right subtree are larger.11 · Search Trees
binary treeA tree in which every node has at most two children, a left and a right one.9 · The List ADT and Generalized Lists
bipartite graphA graph whose vertices can be split into two groups so that every edge joins the two groups.15 · Graphs
bottom-upAn approach that first builds small pieces and then combines them into the whole.1 · Introduction and Algorithm Analysis
bottom-up heap construction (heapify)Turning an array into a heap in O(n) time by sifting down from the last internal node to the root.13 · Priority Queues and Heaps
breadth-first search (BFS)A traversal that visits vertices in order of their distance from the start, using a queue.7 · Queues
brute forceAn approach that tries every possible solution one by one.1 · Introduction and Algorithm Analysis
B-treeA balanced m-way search tree that stores many keys per node and keeps all leaves at the same level.11 · Search Trees
bubble sortA sort that compares neighboring elements and swaps those that are out of order, moving the large ones to the end.19 · Basic Sorting Algorithms
bucketThe compartment of a hash table that corresponds to one index.14 · Hash Tables
bucket sortA method that distributes elements into buckets by value range and then sorts each bucket separately.19 · Basic Sorting Algorithms
bufferMemory that temporarily holds data between a producer and a consumer.7 · Queues
cacheA small, fast memory in which the processor keeps frequently used data; the reason arrays are faster than linked structures.6 · Stacks
call by referencePassing the address of a variable so that the function can modify it.11 · Search Trees
call by valuePassing a copy of the argument; in C all arguments are passed this way.6 · Stacks
call stackThe stack that holds the frames of the active function calls.1 · Introduction and Algorithm Analysis
callocA function that allocates a block of n elements and sets it to zero.2 · Arrays and Structures
capacityThe number of elements a dynamic array can hold without reallocating.1 · Introduction and Algorithm Analysis
childA node directly below a given node.3 · Recursion, Binary Search and Backtracking
circular linked listA linked list in which the last node points to the first node.4 · Linked Lists
circular queueA queue implementation in which an index that reaches the end of the array wraps around to the beginning.7 · Queues
collapsing ruleLinking the nodes on the path directly to the root while finding a set.16 · Sets and Union-Find
collisionTwo different keys falling into the same bucket.14 · Hash Tables
column-major orderStoring a multidimensional array column by column.2 · Arrays and Structures
compactionShifting the polynomials still in use to the beginning of the array when it is full, so as to reclaim the freed space.5 · Polynomials and Sparse Matrices
complete binary treeA binary tree that is full except possibly at the last level, which is filled from left to right.10 · Trees
complete graphA graph in which every pair of vertices is joined by an edge; with n vertices it has n(n − 1)/2 edges.15 · Graphs
compound literalA C99 expression that creates a temporary, unnamed structure object and fills in its fields, for example (element){row, col, dir}.8 · Stack and Queue Applications
compressed sparse column (CSC)The column-major counterpart of CSR: a sparse matrix is compressed by columns instead of rows.5 · Polynomials and Sparse Matrices
compressed sparse row (CSR)A representation that stores a sparse matrix with arrays of values, column indices, and row start positions.5 · Polynomials and Sparse Matrices
connectedHaving a path between every pair of vertices.15 · Graphs
connected componentOne of the largest connected subgraphs of a graph.15 · Graphs
const qualifierA keyword declaring that a variable, or the object a pointer points to, will not be modified.1 · Introduction and Algorithm Analysis
counting sortA sort that counts how many times each key value occurs and then places the elements directly into position.5 · Polynomials and Sparse Matrices
critical pathThe longest path from start to finish; it determines the shortest possible duration of the project.18 · Shortest Paths and Activity Networks
cutA partition of the vertices of a graph into two nonempty groups, S and V − S; an edge with one end in S and the other in V − S crosses the cut.17 · Minimum Spanning Trees
cycleA path that returns to the vertex it started from; it occurs in linked lists as well as in graphs.4 · Linked Lists
cycle detectionFinding out whether a linked structure contains a path that leads back to itself.4 · Linked Lists
dangling pointerA pointer that still points to an object that has been freed or whose lifetime has ended.2 · Arrays and Structures
decision treeA binary tree that shows all possible outcomes of the comparisons made by a comparison-based algorithm.19 · Basic Sorting Algorithms
decrease keyDecreasing the key of an element in a heap and restoring its position; used in Dijkstra's and Prim's algorithms.13 · Priority Queues and Heaps
degreeIn a tree, the number of children of a node; in a graph, the number of edges incident to a vertex.10 · Trees
depthThe largest level in a tree; the textbook also uses this name for the height of a tree.10 · Trees
depth-first search (DFS)A traversal that goes to a neighbor and descends as deep as possible, using a stack or recursion.6 · Stacks
depth-first spanning treeA spanning tree made of the edges along which vertices are first entered during a DFS.15 · Graphs
deque (double-ended queue)A queue in which insertion and removal are possible at both ends.7 · Queues
dequeueRemoving the element at the front of a queue.7 · Queues
dereference (*)The unary operator that reaches the object a pointer points to.4 · Linked Lists
descendantAny node below a given node.10 · Trees
dictionaryAn ADT that stores key–value pairs and supports lookup by key.14 · Hash Tables
Dijkstra's algorithmA greedy algorithm that finds shortest paths for nonnegative weights by finalizing the nearest vertex at each step.18 · Shortest Paths and Activity Networks
direct addressingUsing the key itself as an array index.14 · Hash Tables
directed acyclic graph (DAG)A directed graph that contains no directed cycle.18 · Shortest Paths and Activity Networks
directed graph (digraph)A graph whose edges each have a tail and a head.15 · Graphs
disjoint setsSets with no common element; every element belongs to exactly one set.16 · Sets and Union-Find
divide and conquerAn approach that splits a problem into smaller subproblems and combines their solutions.20 · Advanced Sorting Algorithms
division methodThe hash function h(k) = k mod m, where m is usually chosen to be prime.14 · Hash Tables
double hashingDetermining the probe step with a second hash function.14 · Hash Tables
double rotationTwo single rotations performed one after the other in opposite directions.11 · Search Trees
doublingDoubling the capacity when the array is full; this makes the amortized cost of appending O(1).2 · Arrays and Structures
doubly linked listA linked list in which every node points to both its predecessor and its successor.4 · Linked Lists
down-heapMoving the element at the root down by swapping it with its larger (or smaller) child.13 · Priority Queues and Heaps
dummy activityA task of duration zero that is added only to express a precedence relation.18 · Shortest Paths and Activity Networks
dynamic arrayAn array that is enlarged with realloc when it becomes full.1 · Introduction and Algorithm Analysis
dynamic memory allocationRequesting memory at run time with malloc, calloc, or realloc.2 · Arrays and Structures
edgeA connection between two vertices.15 · Graphs
enqueueAdding an element at the rear of a queue.7 · Queues
enumeration (enum)A C type consisting of named integer constants.2 · Arrays and Structures
equivalence classEach of the disjoint sets into which a reflexive, symmetric, and transitive relation partitions the elements.16 · Sets and Union-Find
eventIn an activity-on-edge network, the moment that a vertex represents: the time at which all activities entering it have finished.18 · Shortest Paths and Activity Networks
exponentialGrowth such as 2n, which doubles whenever one more element is added to the input.1 · Introduction and Algorithm Analysis
expression evaluationComputing the value of an arithmetic expression while respecting operator precedence.6 · Stacks
expression treeA binary tree whose internal nodes are operators and whose leaves are operands.10 · Trees
external sortingSorting in which the data does not fit in memory and auxiliary storage such as a disk is used.19 · Basic Sorting Algorithms
fast transposeA method that transposes a sparse matrix in O(columns + terms) time by first counting the elements in each column.5 · Polynomials and Sparse Matrices
Fibonacci heapAn advanced heap that performs decrease-key in amortized O(1) time.13 · Priority Queues and Heaps
FIFO (first in, first out)The order in which the element inserted first is removed first; the rule of a queue.7 · Queues
findDetermining which set an element belongs to by returning the root of that set.16 · Sets and Union-Find
Floyd-Warshall algorithmAn algorithm that finds all-pairs shortest paths in O(n³) time by adding intermediate vertices one at a time.18 · Shortest Paths and Activity Networks
foldingProducing a hash value by splitting the key into parts and adding the parts.14 · Hash Tables
forestA collection of disjoint trees.17 · Minimum Spanning Trees
freeThe function that returns a block allocated with malloc to the system.1 · Introduction and Algorithm Analysis
free floatThe slack that an activity can use without delaying the earliest start time of its successors.18 · Shortest Paths and Activity Networks
frontThe end of a queue that holds the next element to be removed.7 · Queues
function pointerA pointer that holds the address of a function; this is how a comparison function is passed to qsort.20 · Advanced Sorting Algorithms
garbage collectionAutomatically finding and reclaiming nodes that can no longer be reached.9 · The List ADT and Generalized Lists
generalized listA list whose elements may be atoms or other lists.9 · The List ADT and Generalized Lists
global variableA variable defined at file level that can be accessed from all functions.6 · Stacks
graphA structure consisting of vertices and the edges that join them: G = (V, E).10 · Trees
greedy methodAn approach that makes the choice that looks best at the moment at every step and never goes back on it.17 · Minimum Spanning Trees
hash floodingAn attack in which the attacker sends many keys that fall into the same bucket, degrading hash table lookups to O(n) and costing the server O(n²) work.14 · Hash Tables
hash functionA function that converts a key into an index smaller than the table size.14 · Hash Tables
hash tableA table that maps a key directly to a bucket by a hash function; average access time is O(1).14 · Hash Tables
headThe pointer that points to the first node of a linked list.4 · Linked Lists
header fileA .h file that carries type and function declarations and is added with #include.1 · Introduction and Algorithm Analysis
header nodeA node that holds no data and sits at the start of the list, removing the special case of an empty list.4 · Linked Lists
heapA complete binary tree in which the key of every node is larger (or smaller) than the keys of its children.13 · Priority Queues and Heaps
heap memoryThe region of memory allocated with malloc that lives until it is freed.2 · Arrays and Structures
heap sortAn in-place algorithm that sorts an array by turning it into a heap and repeatedly moving the root to the end.13 · Priority Queues and Heaps
heightThe number of levels from a node down to its farthest leaf; the balance of an AVL tree is measured by it.10 · Trees
heuristicA method that approaches a solution quickly with a clever choice rule without guaranteeing the best one, for example Warnsdorff's rule in the knight's tour.3 · Recursion, Binary Search and Backtracking
home addressThe index that a key's hash function gives, that is, h(k).14 · Hash Tables
Horner's methodEvaluating a polynomial by nested multiplication: a₀ + x(a₁ + x(a₂ + …)).2 · Arrays and Structures
hybrid sortA method that combines several sorting algorithms, for example quick sort and insertion sort.20 · Advanced Sorting Algorithms
implementationThe concrete writing of an ADT with a particular data structure and code.1 · Introduction and Algorithm Analysis
in placeWorking with only a constant amount of extra memory besides the input.2 · Arrays and Structures
incidentThe relationship between an edge and its endpoints: edge (v0, v1) is incident on vertices v0 and v1.15 · Graphs
include guardThe #ifndef … #define … #endif pattern that prevents a header from being included twice in the same file.1 · Introduction and Algorithm Analysis
incoming precedence (icp)The precedence an operator has at the moment it is read from the input.8 · Stack and Queue Applications
incomplete typeA type whose size is not yet known; only a pointer to it can be defined.1 · Introduction and Algorithm Analysis
in-degreeIn a directed graph, the number of edges coming into a vertex.15 · Graphs
indexAn integer that specifies the position of an element in an array.2 · Arrays and Structures
infixThe notation in which the operator is written between the two operands: a + b.8 · Stack and Queue Applications
inorderA traversal that visits the left subtree, then the root, then the right subtree.3 · Recursion, Binary Search and Backtracking
inorder predecessorThe node visited immediately before a given node in an inorder traversal.12 · Threaded Binary Trees
inorder successorThe node visited immediately after a given node in an inorder traversal.12 · Threaded Binary Trees
in-place sortA sort that uses only a constant amount of extra memory.13 · Priority Queues and Heaps
insertion sortA sort that inserts each element by shifting it to its correct place in the sorted part before it.19 · Basic Sorting Algorithms
in-stack precedence (isp)The precedence an operator has while it waits on the stack.8 · Stack and Queue Applications
interfaceThe types and function declarations a module exposes to the outside; in C it lives in the header file.1 · Introduction and Algorithm Analysis
internal nodeA node that has at least one child.10 · Trees
internal sortingSorting in which all the data resides in main memory and every element is accessed in constant time.19 · Basic Sorting Algorithms
introsortA quick sort that switches to heap sort when the recursion depth limit is exceeded.20 · Advanced Sorting Algorithms
invariantA property of a loop or structure that remains true at every step.20 · Advanced Sorting Algorithms
inverse Ackermann function α(n)An extremely slowly growing function that in practice never exceeds 4.16 · Sets and Union-Find
inversionA pair of elements in an array with i < j but a[i] > a[j].19 · Basic Sorting Algorithms
isomorphicAble to be made the same structure by a one-to-one matching of their nodes.10 · Trees
keyThe value used to search for, sort, or distinguish elements.5 · Polynomials and Sparse Matrices
knight's tourThe problem of visiting every square of the board exactly once with a chess knight.3 · Recursion, Binary Search and Backtracking
Kruskal's algorithmAn MST algorithm that tries edges in increasing order of cost and takes those that do not form a cycle.16 · Sets and Union-Find
leafA node that has no children.3 · Recursion, Binary Search and Backtracking
least significant digit (LSD)In multikey sorting, the key or digit with the lowest priority; LSD radix sort starts from this digit.20 · Advanced Sorting Algorithms
levelThe distance of a node from the root; the root is at level 1.10 · Trees
level-orderVisiting nodes level by level from left to right, using a queue.7 · Queues
LIFO (last in, first out)The order in which the element inserted last is removed first; the rule of a stack.6 · Stacks
linear probingOn a collision, looking at the next bucket in sequence.14 · Hash Tables
linear (sequential) searchSearching by comparing elements one by one from beginning to end; O(n).1 · Introduction and Algorithm Analysis
linkA pointer field that connects a node to another node.4 · Linked Lists
linked listA sequence of elements scattered in memory, in which each node holds the address of the next one.1 · Introduction and Algorithm Analysis
list ADTA type for a sequence of elements that supports insertion, deletion, and access by position.9 · The List ADT and Generalized Lists
load factorThe ratio of the number of elements in the table to the number of buckets: α = n / m.14 · Hash Tables
look-up tableAn array in which values that would otherwise be computed with a chain of conditions are stored in advance, for example the row and column increments of the eight directions in a maze.8 · Stack and Queue Applications
lower boundThe least time that any algorithm solving a problem must spend; Ω(n lg n) for comparison-based sorting.19 · Basic Sorting Algorithms
lower triangular matrixA square matrix in which all elements above the main diagonal are zero.2 · Arrays and Structures
macroA name defined with #define that is replaced as text before compilation.1 · Introduction and Algorithm Analysis
magic squareAn n×n table of numbers in which every row, column, and main diagonal has the same sum.1 · Introduction and Algorithm Analysis
mallocA function that allocates a block of memory of the requested number of bytes and returns NULL on failure.1 · Introduction and Algorithm Analysis
mappingA relation that assigns a value to each index; in the abstract view, this is what an array is.2 · Arrays and Structures
mark and sweepA two-phase garbage collection: elements reachable from the root pointers are marked, then memory is scanned and the unmarked elements are reclaimed; it also collects cycles.9 · The List ADT and Generalized Lists
max-heapA heap in which every node is greater than or equal to its children; the largest element is at the root.13 · Priority Queues and Heaps
mazeA grid of walls and paths; a route from entrance to exit is found by backtracking with a stack.6 · Stacks
median-of-threeChoosing the pivot as the median of the first, middle, and last elements.20 · Advanced Sorting Algorithms
memory leakMemory that can no longer be reached but has not been freed.4 · Linked Lists
mergeCombining two sorted arrays or lists into a single sorted array.5 · Polynomials and Sparse Matrices
merge sortAn algorithm that splits an array in two, sorts the parts, and merges the sorted parts; O(n lg n).20 · Advanced Sorting Algorithms
mid-squareA hash function that squares the key and uses the middle r bits of the result as the index; the table size m is the r-th power of 2.14 · Hash Tables
min-heapA heap in which every node is less than or equal to its children; the smallest element is at the root.13 · Priority Queues and Heaps
minimum spanning tree (MST)A spanning tree whose edge costs have the smallest sum.15 · Graphs
modular arithmeticComputation with remainders; circular queues and hash functions rely on it.7 · Queues
monotonic stackA stack whose element values are kept in decreasing order from bottom to top; it solves problems such as “next greater element to the right” in O(n).8 · Stack and Queue Applications
Morris traversalAn inorder traversal with no stack and O(1) extra memory that temporarily sets up and removes threads.12 · Threaded Binary Trees
most significant digit (MSD)In multikey sorting, the key or digit with the highest priority (K0); for example, the leftmost digit of a number.20 · Advanced Sorting Algorithms
multidimensional arrayAn array whose elements are accessed with more than one index.2 · Arrays and Structures
multigraphA graph that may have more than one edge between two vertices; the Königsberg graph is an example.15 · Graphs
multiplication methodFinding the index by multiplying the fractional part of k·A by m.14 · Hash Tables
multivariate polynomialA polynomial with more than one variable; it is represented by a generalized list.9 · The List ADT and Generalized Lists
negative cycleA cycle whose edge weights sum to a negative value; it makes the shortest path undefined.18 · Shortest Paths and Activity Networks
nodeA structure that holds data and one or more link fields.3 · Recursion, Binary Search and Backtracking
non-comparison sortA sort that does not compare elements with one another and is therefore not bound by the n lg n lower bound, such as radix sort.20 · Advanced Sorting Algorithms
NP-completeThe class of problems such that if a polynomial-time algorithm is found for any one of them, all can be solved in polynomial time; SAT is the first member of this class.3 · Recursion, Binary Search and Backtracking
n-queens problemThe problem of placing n queens on an n×n board so that no two threaten each other.3 · Recursion, Binary Search and Backtracking
null character ('\0')The character with value zero that marks the end of a string.2 · Arrays and Structures
null pointer (NULL)A pointer that points to no object; it represents an empty list and an empty subtree.1 · Introduction and Algorithm Analysis
opaque typeA structure type of which only the name is declared and whose fields are hidden from the user; the C counterpart of an ADT.1 · Introduction and Algorithm Analysis
open addressingOn a collision, looking for another empty position inside the table.14 · Hash Tables
operandIn an expression, a value to which an operation is applied: variables such as a and b, or constants such as 4 and 2.8 · Stack and Queue Applications
operatorIn an expression, a symbol such as +, −, *, / that specifies the operation to perform.8 · Stack and Queue Applications
operator precedenceThe rule that determines which operator is applied first in an expression.8 · Stack and Queue Applications
optimal substructureThe property that every intermediate part of a shortest path is itself a shortest path between its own endpoints.18 · Shortest Paths and Activity Networks
orthogonal listA representation in which every edge node appears in both a row list and a column list.15 · Graphs
out-degreeIn a directed graph, the number of edges leaving a vertex.15 · Graphs
overflowAn attempt to insert into a full structure.6 · Stacks
paddingMeaningless bytes the compiler places between structure fields for alignment; this is why structures are not compared byte by byte.2 · Arrays and Structures
parentThe node directly above a given node.10 · Trees
parent arrayAn array that stores the parent of each element in the tree; the root holds a negative value.16 · Sets and Union-Find
partitionSplitting an array into two parts, the elements smaller than the pivot and those larger.20 · Advanced Sorting Algorithms
pathA sequence of consecutively adjacent vertices.15 · Graphs
path compressionThe general name of the collapsing rule; it shortens later find operations.16 · Sets and Union-Find
perfect binary treeA binary tree with all levels full, having 2k − 1 nodes at depth k; the textbook (Horowitz) calls this a full binary tree.10 · Trees
performance analysisEstimating the time and memory requirements of a program independently of the machine.1 · Introduction and Algorithm Analysis
performance measurementRunning a program on a particular machine and compiler and measuring its actual running time; it depends on the machine.1 · Introduction and Algorithm Analysis
permutationOne of the possible arrangements of the elements of a set; n elements have n! permutations.1 · Introduction and Algorithm Analysis
pivotThe element chosen in quick sort to divide the array in two.20 · Advanced Sorting Algorithms
pointerA variable that holds the memory address of an object.2 · Arrays and Structures
pointer arithmeticAdding an integer to or subtracting it from a pointer; the unit is one element of the pointed-to type, not a byte.2 · Arrays and Structures
pointer to pointerA pointer that holds the address of a pointer; it is used to change the caller's pointer.9 · The List ADT and Generalized Lists
polynomialA sum of terms, each made of a coefficient and an exponent.5 · Polynomials and Sparse Matrices
popRemoving the element at the top of a stack.6 · Stacks
postfix (reverse Polish notation)The notation, which needs no parentheses, in which the operator is written after the operands: a b +.8 · Stack and Queue Applications
postorderA traversal that visits the left subtree, then the right subtree, then the root.3 · Recursion, Binary Search and Backtracking
predecessorThe node that comes immediately before a given node in the inorder sequence.12 · Threaded Binary Trees
prefix (Polish notation)The notation in which the operator is written before the operands: + a b.8 · Stack and Queue Applications
preorderA traversal that visits the root, then the left subtree, then the right subtree.9 · The List ADT and Generalized Lists
preprocessorThe stage that processes directives such as #include and #define before compilation.1 · Introduction and Algorithm Analysis
primary clusteringIn linear probing, the formation of long consecutive blocks of occupied buckets.14 · Hash Tables
Prim's algorithmAn MST algorithm that starts from one vertex and adds the vertex joined to the tree by the cheapest edge.17 · Minimum Spanning Trees
priority queueA queue from which the element with the highest (or lowest) priority is always removed.5 · Polynomials and Sparse Matrices
probeIn open addressing, checking whether a bucket is empty.14 · Hash Tables
probe sequenceIn open addressing, the order of slots examined for a key, h(k, i).14 · Hash Tables
program stepA meaningful piece of code whose running time is independent of the input size; the unit of step counting.1 · Introduction and Algorithm Analysis
pushAdding an element to the top of a stack.4 · Linked Lists
quadratic probingOn a collision, looking at buckets i² steps away.14 · Hash Tables
queueA linear structure in which insertion is done at the rear and removal at the front.7 · Queues
quick sortAn algorithm that partitions an array around a pivot element and sorts the two parts recursively.19 · Basic Sorting Algorithms
radix sortSorting numbers digit by digit, starting from the least significant digit, with a stable sort.20 · Advanced Sorting Algorithms
random accessBeing able to access any element of an array in constant time, that is O(1), regardless of the array's length.4 · Linked Lists
reallocA function that enlarges or shrinks an allocated block, moving it if necessary.1 · Introduction and Algorithm Analysis
rearThe end of a queue where a new element is inserted.7 · Queues
recordA unit of data made of one or more fields that is moved as a whole during sorting.19 · Basic Sorting Algorithms
recurrence relationAn equation that defines a function in terms of its own smaller values, such as T(n) = 2T(n/2) + n.3 · Recursion, Binary Search and Backtracking
recursionA function calling itself with a smaller input.1 · Introduction and Algorithm Analysis
recursiveCalling itself; using recursion.1 · Introduction and Algorithm Analysis
red-black treeA search tree that keeps its height O(lg n) through rules on node colors.11 · Search Trees
reference countThe number of pointers that point to a node; when it drops to zero, the node is returned.9 · The List ADT and Generalized Lists
rehashing (resizing)Enlarging the table when the load factor grows and hashing all the keys again.14 · Hash Tables
relaxationUpdating a distance value when a shorter path is found through an edge.18 · Shortest Paths and Activity Networks
return addressThe address of the instruction at which execution continues when a call ends.3 · Recursion, Binary Search and Backtracking
reverse-deleteAn MST algorithm that starts with all edges and tries them in decreasing order of cost, deleting each one that does not disconnect the graph; the reverse of Kruskal's.17 · Minimum Spanning Trees
reversing a listReversing the order of a list by changing the direction of its links; in place and O(n).4 · Linked Lists
rootThe topmost node of a tree, which has no parent.3 · Recursion, Binary Search and Backtracking
rotationAn operation that changes the local structure of a tree while preserving the search order.11 · Search Trees
row-major orderStoring a multidimensional array row by row consecutively; the layout of C.2 · Arrays and Structures
satisfiability (SAT)The problem of whether some assignment of variables makes a logical formula true.3 · Recursion, Binary Search and Backtracking
secondary clusteringIn quadratic probing, keys with the same home address follow the same probe sequence and block one another.14 · Hash Tables
selection sortA sort that at each step finds the smallest of the remaining elements and puts it in the next position.1 · Introduction and Algorithm Analysis
self-balancing treeA tree that restores its balance by itself through rotations after insertions and deletions.11 · Search Trees
self-loopAn edge that joins a vertex to itself; simple graphs do not contain them.15 · Graphs
self-referential structA structure with a pointer field of its own type; the basis of linked nodes.2 · Arrays and Structures
sentinelA special value or node placed at the end so that a separate boundary check in a loop becomes unnecessary.1 · Introduction and Algorithm Analysis
separate chainingKeeping the keys that fall into each bucket in a linked list; in the slides it is simply called “chaining”.14 · Hash Tables
Shell sortA sort that applies insertion sort to elements far apart, using decreasing gaps.19 · Basic Sorting Algorithms
short-circuit evaluationIn the && and || operators, not evaluating the remaining operand once the result is known.2 · Arrays and Structures
shortest pathA path between two vertices whose edge costs have the smallest sum.8 · Stack and Queue Applications
siblingChildren of the same parent.3 · Recursion, Binary Search and Backtracking
simple uniform hashingThe assumption that every key falls into each of the m buckets with probability 1/m, independently of the other keys.14 · Hash Tables
singly linked listA linked list in which each node points only to the next node.4 · Linked Lists
sizeofThe operator that gives the size of a type or object in bytes at compile time.1 · Introduction and Algorithm Analysis
skewed treeA tree all of whose nodes extend in a single direction, behaving like a list.10 · Trees
slackThe difference between the latest and earliest time of a task; zero for critical tasks.18 · Shortest Paths and Activity Networks
slotEach cell of a hash table; used synonymously with bucket.14 · Hash Tables
Sollin's (Borůvka's) algorithmAn MST algorithm that in each round selects the cheapest outgoing edge of every component.17 · Minimum Spanning Trees
sortingPutting elements into ascending or descending order by their keys.1 · Introduction and Algorithm Analysis
space complexityThe amount of memory a program needs as a function of the input size.1 · Introduction and Algorithm Analysis
spanning forestIn a graph that is not connected, the collection of spanning trees of its components.17 · Minimum Spanning Trees
spanning treeA subgraph of a connected graph that joins all its vertices without cycles; it has n − 1 edges.15 · Graphs
sparse matrixA matrix most of whose elements are zero; only the nonzero ones are stored.5 · Polynomials and Sparse Matrices
splay treeA search tree that moves the accessed node to the root by rotations.11 · Search Trees
stable (sort)A sort that preserves the relative order of elements with equal keys.19 · Basic Sorting Algorithms
stackA linear structure in which insertion and removal take place only at the top end.6 · Stacks
stack frame (activation record)A record that holds the parameters, local variables, and return address of a call; the text also calls it simply a “frame”.1 · Introduction and Algorithm Analysis
stack overflowThe call stack exceeding its allotted memory; it usually happens with very deep or infinite recursion.3 · Recursion, Binary Search and Backtracking
stringIn C, a char array terminated by '\0'.2 · Arrays and Structures
structA C type that gathers fields of different types into a single record.1 · Introduction and Algorithm Analysis
subgraphA graph whose vertices and edges are subsets of the vertices and edges of a graph.15 · Graphs
subsetA set formed from some of the elements of a set; n elements have 2n subsets.3 · Recursion, Binary Search and Backtracking
subtreeA tree made of a node and all its descendants.9 · The List ADT and Generalized Lists
successorThe node that comes immediately after a given node in the inorder sequence; used in deletion and in threaded trees.12 · Threaded Binary Trees
swapExchanging the values of two variables.1 · Introduction and Algorithm Analysis
synonymsKeys that fall to the same home address, that is, keys that collide.14 · Hash Tables
system life cycleThe development process consisting of the requirements, analysis, design, coding, and verification phases.1 · Introduction and Algorithm Analysis
tagged unionA structure that records with an enum tag which field is valid.2 · Arrays and Structures
tail (of a generalized list)In a generalized list, the list that remains after the first element is removed.9 · The List ADT and Generalized Lists
tail recursionRecursion in which the recursive call is the last operation of the function; it is easily converted into a loop.3 · Recursion, Binary Search and Backtracking
threadIn a threaded tree, a pointer that points to the predecessor or successor in place of an empty child.10 · Trees
threaded binary treeA binary tree whose null pointers point to the inorder predecessor and successor.10 · Trees
time complexityThe number of steps a program executes as a function of the input size.1 · Introduction and Algorithm Analysis
tokenAn item processed as a single unit while parsing an expression: an operand, an operator, or a parenthesis.8 · Stack and Queue Applications
tombstoneIn open addressing, a mark placed in a deleted bucket so that a search does not stop there.14 · Hash Tables
topThe end of a stack where the most recently inserted element is.6 · Stacks
top-downA design approach that first treats the problem as a whole and then splits it into ever smaller parts.1 · Introduction and Algorithm Analysis
topological orderAn ordering of vertices in which the tail of every edge comes before its head.15 · Graphs
tortoise and hareFloyd's method of finding a cycle with two pointers, one advancing one step and the other two steps at a time.4 · Linked Lists
total floatThe difference between the latest and earliest start times of an activity; it is shared among the activities on the same path and can be spent only once along the path.18 · Shortest Paths and Activity Networks
Towers of HanoiThe problem of moving disks among three pegs according to the rules; it takes 2n − 1 moves.3 · Recursion, Binary Search and Backtracking
transposeThe matrix obtained by interchanging the rows and columns of a matrix.2 · Arrays and Structures
traversalVisiting every element of a structure once in a particular order.2 · Arrays and Structures
treeA hierarchical structure with no cycles that starts from a root and branches into subtrees.1 · Introduction and Algorithm Analysis
tripleIn a sparse matrix, the (row, column, value) record that holds one nonzero element.5 · Polynomials and Sparse Matrices
typedefA C declaration that gives a new name to an existing type.1 · Introduction and Algorithm Analysis
undefined behaviorA situation for which the C standard does not determine the result, for example access beyond an array's bounds; the program may crash or appear to work correctly.2 · Arrays and Structures
underflowAn attempt to remove an element from an empty structure.6 · Stacks
undirected graphA graph whose edges have no direction.15 · Graphs
undoReversing the most recent operations in reverse order; implemented with a stack.6 · Stacks
unionThe operation of merging two sets into one.16 · Sets and Union-Find
union by rankIn a union, using the height bound (rank) instead of the tree weight.16 · Sets and Union-Find
union (C)A C type whose fields all share the same memory region; only one field is valid at a time.2 · Arrays and Structures
union-findA disjoint-set structure that supports the union and find operations.16 · Sets and Union-Find
universal hashingChoosing the hash function at random at the start from a family in which two different keys collide with probability at most 1/m.14 · Hash Tables
up-heapMoving an inserted element up to its proper place by swapping with its parent.13 · Priority Queues and Heaps
vertexAn element of a graph; the same term as node in a tree is used.15 · Graphs
void pointer (void *)A pointer of unspecified type; in generic routines such as qsort it is cast to any type.20 · Advanced Sorting Algorithms
weighted graph (network)A graph whose edges are assigned a cost or length.15 · Graphs
weighting ruleIn a union, attaching the tree with fewer nodes under the tree with more nodes; also called union by size.16 · Sets and Union-Find
worst caseThe running time for the input that needs the most steps among inputs of the same size.1 · Introduction and Algorithm Analysis
wrap-aroundIn a circular queue, the index returning to the start after the last cell, by (rear + 1) % MAX.7 · Queues

Course page: Data Structures and Algorithms with C · © Sercan Külcü. All rights reserved.