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.
| Term | Definition | Chapter |
|---|---|---|
| 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 function | A very fast-growing recursive function whose inverse, α(n), bounds the cost of union-find. | 16 · Sets and Union-Find |
| activity network | A 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) network | An activity network in which the tasks are edges and the events are vertices. | 18 · Shortest Paths and Activity Networks |
| activity on vertex (AOV) network | An 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 list | A representation that keeps, for each vertex, a linked list of its neighbors. | 15 · Graphs |
| adjacency matrix | An n×n matrix in which a[i][j] = 1 if there is an edge between i and j. | 15 · Graphs |
| adjacency multilist | A 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 |
| adjacent | Two vertices that are joined by an edge. | 15 · Graphs |
| aggregate analysis | An 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 |
| algorithm | A method that solves a problem in a finite number of precise and effective steps. | 1 · Introduction and Algorithm Analysis |
| alignment | The 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 paths | The problem of finding a shortest path between every pair of vertices. | 18 · Shortest Paths and Activity Networks |
| amortized analysis | Finding the cost per operation by dividing the total cost of a sequence of operations by the number of operations. | 1 · Introduction and Algorithm Analysis |
| ancestor | Any node on the path from the root to a given node. | 10 · Trees |
| array | A 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 |
| associativity | The 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 notation | A notation that compares the growth rates of functions for large n by discarding constant factors. | 1 · Introduction and Algorithm Analysis |
| available space list | A list that keeps freed nodes so that they can be reused (avail). | 4 · Linked Lists |
| average case | The expected running time over a given distribution of inputs. | 1 · Introduction and Algorithm Analysis |
| AVL tree | A search tree that keeps the height difference of the two subtrees of every node at most 1. | 11 · Search Trees |
| back edge | In DFS, an edge to an already marked ancestor other than the parent; it shows that the graph contains a cycle. | 15 · Graphs |
| backtracking | A 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 factor | The height of the left subtree minus the height of the right subtree. | 11 · Search Trees |
| balanced parentheses | Checking with a stack whether every opening parenthesis is closed by one of the right type and in the right order. | 6 · Stacks |
| balanced tree | A search tree whose height is kept at O(lg n). | 10 · Trees |
| band matrix | A matrix whose nonzero elements lie in a band around the main diagonal. | 2 · Arrays and Structures |
| base case | The case in which a recursion returns a result directly, without calling itself. | 1 · Introduction and Algorithm Analysis |
| Bellman-Ford algorithm | A shortest-path algorithm that relaxes all edges n − 1 times and allows negative weights. | 18 · Shortest Paths and Activity Networks |
| best case | The running time for the input that needs the fewest steps among inputs of the same size. | 1 · Introduction and Algorithm Analysis |
| Big O | An upper bound: f(n) = O(g(n)) if f(n) ≤ c·g(n) for all n ≥ n₀. | 1 · Introduction and Algorithm Analysis |
| Big Omega | A lower bound: f(n) = Ω(g(n)) if f(n) ≥ c·g(n) for all n ≥ n₀. | 1 · Introduction and Algorithm Analysis |
| Big Theta | A tight bound: f(n) = Θ(g(n)) if f(n) is both O(g(n)) and Ω(g(n)). | 1 · Introduction and Algorithm Analysis |
| binary search | Searching 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 tree | A tree in which every node has at most two children, a left and a right one. | 9 · The List ADT and Generalized Lists |
| bipartite graph | A graph whose vertices can be split into two groups so that every edge joins the two groups. | 15 · Graphs |
| bottom-up | An 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 force | An approach that tries every possible solution one by one. | 1 · Introduction and Algorithm Analysis |
| B-tree | A balanced m-way search tree that stores many keys per node and keeps all leaves at the same level. | 11 · Search Trees |
| bubble sort | A sort that compares neighboring elements and swaps those that are out of order, moving the large ones to the end. | 19 · Basic Sorting Algorithms |
| bucket | The compartment of a hash table that corresponds to one index. | 14 · Hash Tables |
| bucket sort | A method that distributes elements into buckets by value range and then sorts each bucket separately. | 19 · Basic Sorting Algorithms |
| buffer | Memory that temporarily holds data between a producer and a consumer. | 7 · Queues |
| cache | A small, fast memory in which the processor keeps frequently used data; the reason arrays are faster than linked structures. | 6 · Stacks |
| call by reference | Passing the address of a variable so that the function can modify it. | 11 · Search Trees |
| call by value | Passing a copy of the argument; in C all arguments are passed this way. | 6 · Stacks |
| call stack | The stack that holds the frames of the active function calls. | 1 · Introduction and Algorithm Analysis |
| calloc | A function that allocates a block of n elements and sets it to zero. | 2 · Arrays and Structures |
| capacity | The number of elements a dynamic array can hold without reallocating. | 1 · Introduction and Algorithm Analysis |
| child | A node directly below a given node. | 3 · Recursion, Binary Search and Backtracking |
| circular linked list | A linked list in which the last node points to the first node. | 4 · Linked Lists |
| circular queue | A queue implementation in which an index that reaches the end of the array wraps around to the beginning. | 7 · Queues |
| collapsing rule | Linking the nodes on the path directly to the root while finding a set. | 16 · Sets and Union-Find |
| collision | Two different keys falling into the same bucket. | 14 · Hash Tables |
| column-major order | Storing a multidimensional array column by column. | 2 · Arrays and Structures |
| compaction | Shifting 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 tree | A binary tree that is full except possibly at the last level, which is filled from left to right. | 10 · Trees |
| complete graph | A 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 literal | A 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 |
| connected | Having a path between every pair of vertices. | 15 · Graphs |
| connected component | One of the largest connected subgraphs of a graph. | 15 · Graphs |
| const qualifier | A keyword declaring that a variable, or the object a pointer points to, will not be modified. | 1 · Introduction and Algorithm Analysis |
| counting sort | A sort that counts how many times each key value occurs and then places the elements directly into position. | 5 · Polynomials and Sparse Matrices |
| critical path | The longest path from start to finish; it determines the shortest possible duration of the project. | 18 · Shortest Paths and Activity Networks |
| cut | A 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 |
| cycle | A path that returns to the vertex it started from; it occurs in linked lists as well as in graphs. | 4 · Linked Lists |
| cycle detection | Finding out whether a linked structure contains a path that leads back to itself. | 4 · Linked Lists |
| dangling pointer | A pointer that still points to an object that has been freed or whose lifetime has ended. | 2 · Arrays and Structures |
| decision tree | A binary tree that shows all possible outcomes of the comparisons made by a comparison-based algorithm. | 19 · Basic Sorting Algorithms |
| decrease key | Decreasing 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 |
| degree | In a tree, the number of children of a node; in a graph, the number of edges incident to a vertex. | 10 · Trees |
| depth | The 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 tree | A 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 |
| dequeue | Removing 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 |
| descendant | Any node below a given node. | 10 · Trees |
| dictionary | An ADT that stores key–value pairs and supports lookup by key. | 14 · Hash Tables |
| Dijkstra's algorithm | A greedy algorithm that finds shortest paths for nonnegative weights by finalizing the nearest vertex at each step. | 18 · Shortest Paths and Activity Networks |
| direct addressing | Using 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 sets | Sets with no common element; every element belongs to exactly one set. | 16 · Sets and Union-Find |
| divide and conquer | An approach that splits a problem into smaller subproblems and combines their solutions. | 20 · Advanced Sorting Algorithms |
| division method | The hash function h(k) = k mod m, where m is usually chosen to be prime. | 14 · Hash Tables |
| double hashing | Determining the probe step with a second hash function. | 14 · Hash Tables |
| double rotation | Two single rotations performed one after the other in opposite directions. | 11 · Search Trees |
| doubling | Doubling the capacity when the array is full; this makes the amortized cost of appending O(1). | 2 · Arrays and Structures |
| doubly linked list | A linked list in which every node points to both its predecessor and its successor. | 4 · Linked Lists |
| down-heap | Moving the element at the root down by swapping it with its larger (or smaller) child. | 13 · Priority Queues and Heaps |
| dummy activity | A task of duration zero that is added only to express a precedence relation. | 18 · Shortest Paths and Activity Networks |
| dynamic array | An array that is enlarged with realloc when it becomes full. | 1 · Introduction and Algorithm Analysis |
| dynamic memory allocation | Requesting memory at run time with malloc, calloc, or realloc. | 2 · Arrays and Structures |
| edge | A connection between two vertices. | 15 · Graphs |
| enqueue | Adding 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 class | Each of the disjoint sets into which a reflexive, symmetric, and transitive relation partitions the elements. | 16 · Sets and Union-Find |
| event | In 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 |
| exponential | Growth such as 2n, which doubles whenever one more element is added to the input. | 1 · Introduction and Algorithm Analysis |
| expression evaluation | Computing the value of an arithmetic expression while respecting operator precedence. | 6 · Stacks |
| expression tree | A binary tree whose internal nodes are operators and whose leaves are operands. | 10 · Trees |
| external sorting | Sorting in which the data does not fit in memory and auxiliary storage such as a disk is used. | 19 · Basic Sorting Algorithms |
| fast transpose | A 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 heap | An 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 |
| find | Determining which set an element belongs to by returning the root of that set. | 16 · Sets and Union-Find |
| Floyd-Warshall algorithm | An 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 |
| folding | Producing a hash value by splitting the key into parts and adding the parts. | 14 · Hash Tables |
| forest | A collection of disjoint trees. | 17 · Minimum Spanning Trees |
| free | The function that returns a block allocated with malloc to the system. | 1 · Introduction and Algorithm Analysis |
| free float | The slack that an activity can use without delaying the earliest start time of its successors. | 18 · Shortest Paths and Activity Networks |
| front | The end of a queue that holds the next element to be removed. | 7 · Queues |
| function pointer | A pointer that holds the address of a function; this is how a comparison function is passed to qsort. | 20 · Advanced Sorting Algorithms |
| garbage collection | Automatically finding and reclaiming nodes that can no longer be reached. | 9 · The List ADT and Generalized Lists |
| generalized list | A list whose elements may be atoms or other lists. | 9 · The List ADT and Generalized Lists |
| global variable | A variable defined at file level that can be accessed from all functions. | 6 · Stacks |
| graph | A structure consisting of vertices and the edges that join them: G = (V, E). | 10 · Trees |
| greedy method | An 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 flooding | An 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 function | A function that converts a key into an index smaller than the table size. | 14 · Hash Tables |
| hash table | A table that maps a key directly to a bucket by a hash function; average access time is O(1). | 14 · Hash Tables |
| head | The pointer that points to the first node of a linked list. | 4 · Linked Lists |
| header file | A .h file that carries type and function declarations and is added with #include. | 1 · Introduction and Algorithm Analysis |
| header node | A node that holds no data and sits at the start of the list, removing the special case of an empty list. | 4 · Linked Lists |
| heap | A 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 memory | The region of memory allocated with malloc that lives until it is freed. | 2 · Arrays and Structures |
| heap sort | An 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 |
| height | The number of levels from a node down to its farthest leaf; the balance of an AVL tree is measured by it. | 10 · Trees |
| heuristic | A 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 address | The index that a key's hash function gives, that is, h(k). | 14 · Hash Tables |
| Horner's method | Evaluating a polynomial by nested multiplication: a₀ + x(a₁ + x(a₂ + …)). | 2 · Arrays and Structures |
| hybrid sort | A method that combines several sorting algorithms, for example quick sort and insertion sort. | 20 · Advanced Sorting Algorithms |
| implementation | The concrete writing of an ADT with a particular data structure and code. | 1 · Introduction and Algorithm Analysis |
| in place | Working with only a constant amount of extra memory besides the input. | 2 · Arrays and Structures |
| incident | The relationship between an edge and its endpoints: edge (v0, v1) is incident on vertices v0 and v1. | 15 · Graphs |
| include guard | The #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 type | A type whose size is not yet known; only a pointer to it can be defined. | 1 · Introduction and Algorithm Analysis |
| in-degree | In a directed graph, the number of edges coming into a vertex. | 15 · Graphs |
| index | An integer that specifies the position of an element in an array. | 2 · Arrays and Structures |
| infix | The notation in which the operator is written between the two operands: a + b. | 8 · Stack and Queue Applications |
| inorder | A traversal that visits the left subtree, then the root, then the right subtree. | 3 · Recursion, Binary Search and Backtracking |
| inorder predecessor | The node visited immediately before a given node in an inorder traversal. | 12 · Threaded Binary Trees |
| inorder successor | The node visited immediately after a given node in an inorder traversal. | 12 · Threaded Binary Trees |
| in-place sort | A sort that uses only a constant amount of extra memory. | 13 · Priority Queues and Heaps |
| insertion sort | A 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 |
| interface | The types and function declarations a module exposes to the outside; in C it lives in the header file. | 1 · Introduction and Algorithm Analysis |
| internal node | A node that has at least one child. | 10 · Trees |
| internal sorting | Sorting in which all the data resides in main memory and every element is accessed in constant time. | 19 · Basic Sorting Algorithms |
| introsort | A quick sort that switches to heap sort when the recursion depth limit is exceeded. | 20 · Advanced Sorting Algorithms |
| invariant | A 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 |
| inversion | A pair of elements in an array with i < j but a[i] > a[j]. | 19 · Basic Sorting Algorithms |
| isomorphic | Able to be made the same structure by a one-to-one matching of their nodes. | 10 · Trees |
| key | The value used to search for, sort, or distinguish elements. | 5 · Polynomials and Sparse Matrices |
| knight's tour | The problem of visiting every square of the board exactly once with a chess knight. | 3 · Recursion, Binary Search and Backtracking |
| Kruskal's algorithm | An MST algorithm that tries edges in increasing order of cost and takes those that do not form a cycle. | 16 · Sets and Union-Find |
| leaf | A 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 |
| level | The distance of a node from the root; the root is at level 1. | 10 · Trees |
| level-order | Visiting 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 probing | On a collision, looking at the next bucket in sequence. | 14 · Hash Tables |
| linear (sequential) search | Searching by comparing elements one by one from beginning to end; O(n). | 1 · Introduction and Algorithm Analysis |
| link | A pointer field that connects a node to another node. | 4 · Linked Lists |
| linked list | A sequence of elements scattered in memory, in which each node holds the address of the next one. | 1 · Introduction and Algorithm Analysis |
| list ADT | A type for a sequence of elements that supports insertion, deletion, and access by position. | 9 · The List ADT and Generalized Lists |
| load factor | The ratio of the number of elements in the table to the number of buckets: α = n / m. | 14 · Hash Tables |
| look-up table | An 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 bound | The least time that any algorithm solving a problem must spend; Ω(n lg n) for comparison-based sorting. | 19 · Basic Sorting Algorithms |
| lower triangular matrix | A square matrix in which all elements above the main diagonal are zero. | 2 · Arrays and Structures |
| macro | A name defined with #define that is replaced as text before compilation. | 1 · Introduction and Algorithm Analysis |
| magic square | An n×n table of numbers in which every row, column, and main diagonal has the same sum. | 1 · Introduction and Algorithm Analysis |
| malloc | A function that allocates a block of memory of the requested number of bytes and returns NULL on failure. | 1 · Introduction and Algorithm Analysis |
| mapping | A relation that assigns a value to each index; in the abstract view, this is what an array is. | 2 · Arrays and Structures |
| mark and sweep | A 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-heap | A 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 |
| maze | A grid of walls and paths; a route from entrance to exit is found by backtracking with a stack. | 6 · Stacks |
| median-of-three | Choosing the pivot as the median of the first, middle, and last elements. | 20 · Advanced Sorting Algorithms |
| memory leak | Memory that can no longer be reached but has not been freed. | 4 · Linked Lists |
| merge | Combining two sorted arrays or lists into a single sorted array. | 5 · Polynomials and Sparse Matrices |
| merge sort | An algorithm that splits an array in two, sorts the parts, and merges the sorted parts; O(n lg n). | 20 · Advanced Sorting Algorithms |
| mid-square | A 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-heap | A 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 arithmetic | Computation with remainders; circular queues and hash functions rely on it. | 7 · Queues |
| monotonic stack | A 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 traversal | An 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 array | An array whose elements are accessed with more than one index. | 2 · Arrays and Structures |
| multigraph | A graph that may have more than one edge between two vertices; the Königsberg graph is an example. | 15 · Graphs |
| multiplication method | Finding the index by multiplying the fractional part of k·A by m. | 14 · Hash Tables |
| multivariate polynomial | A polynomial with more than one variable; it is represented by a generalized list. | 9 · The List ADT and Generalized Lists |
| negative cycle | A cycle whose edge weights sum to a negative value; it makes the shortest path undefined. | 18 · Shortest Paths and Activity Networks |
| node | A structure that holds data and one or more link fields. | 3 · Recursion, Binary Search and Backtracking |
| non-comparison sort | A 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-complete | The 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 problem | The 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 type | A 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 addressing | On a collision, looking for another empty position inside the table. | 14 · Hash Tables |
| operand | In 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 |
| operator | In an expression, a symbol such as +, −, *, / that specifies the operation to perform. | 8 · Stack and Queue Applications |
| operator precedence | The rule that determines which operator is applied first in an expression. | 8 · Stack and Queue Applications |
| optimal substructure | The 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 list | A representation in which every edge node appears in both a row list and a column list. | 15 · Graphs |
| out-degree | In a directed graph, the number of edges leaving a vertex. | 15 · Graphs |
| overflow | An attempt to insert into a full structure. | 6 · Stacks |
| padding | Meaningless bytes the compiler places between structure fields for alignment; this is why structures are not compared byte by byte. | 2 · Arrays and Structures |
| parent | The node directly above a given node. | 10 · Trees |
| parent array | An array that stores the parent of each element in the tree; the root holds a negative value. | 16 · Sets and Union-Find |
| partition | Splitting an array into two parts, the elements smaller than the pivot and those larger. | 20 · Advanced Sorting Algorithms |
| path | A sequence of consecutively adjacent vertices. | 15 · Graphs |
| path compression | The general name of the collapsing rule; it shortens later find operations. | 16 · Sets and Union-Find |
| perfect binary tree | A 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 analysis | Estimating the time and memory requirements of a program independently of the machine. | 1 · Introduction and Algorithm Analysis |
| performance measurement | Running a program on a particular machine and compiler and measuring its actual running time; it depends on the machine. | 1 · Introduction and Algorithm Analysis |
| permutation | One of the possible arrangements of the elements of a set; n elements have n! permutations. | 1 · Introduction and Algorithm Analysis |
| pivot | The element chosen in quick sort to divide the array in two. | 20 · Advanced Sorting Algorithms |
| pointer | A variable that holds the memory address of an object. | 2 · Arrays and Structures |
| pointer arithmetic | Adding 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 pointer | A pointer that holds the address of a pointer; it is used to change the caller's pointer. | 9 · The List ADT and Generalized Lists |
| polynomial | A sum of terms, each made of a coefficient and an exponent. | 5 · Polynomials and Sparse Matrices |
| pop | Removing 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 |
| postorder | A traversal that visits the left subtree, then the right subtree, then the root. | 3 · Recursion, Binary Search and Backtracking |
| predecessor | The 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 |
| preorder | A traversal that visits the root, then the left subtree, then the right subtree. | 9 · The List ADT and Generalized Lists |
| preprocessor | The stage that processes directives such as #include and #define before compilation. | 1 · Introduction and Algorithm Analysis |
| primary clustering | In linear probing, the formation of long consecutive blocks of occupied buckets. | 14 · Hash Tables |
| Prim's algorithm | An MST algorithm that starts from one vertex and adds the vertex joined to the tree by the cheapest edge. | 17 · Minimum Spanning Trees |
| priority queue | A queue from which the element with the highest (or lowest) priority is always removed. | 5 · Polynomials and Sparse Matrices |
| probe | In open addressing, checking whether a bucket is empty. | 14 · Hash Tables |
| probe sequence | In open addressing, the order of slots examined for a key, h(k, i). | 14 · Hash Tables |
| program step | A meaningful piece of code whose running time is independent of the input size; the unit of step counting. | 1 · Introduction and Algorithm Analysis |
| push | Adding an element to the top of a stack. | 4 · Linked Lists |
| quadratic probing | On a collision, looking at buckets i² steps away. | 14 · Hash Tables |
| queue | A linear structure in which insertion is done at the rear and removal at the front. | 7 · Queues |
| quick sort | An algorithm that partitions an array around a pivot element and sorts the two parts recursively. | 19 · Basic Sorting Algorithms |
| radix sort | Sorting numbers digit by digit, starting from the least significant digit, with a stable sort. | 20 · Advanced Sorting Algorithms |
| random access | Being able to access any element of an array in constant time, that is O(1), regardless of the array's length. | 4 · Linked Lists |
| realloc | A function that enlarges or shrinks an allocated block, moving it if necessary. | 1 · Introduction and Algorithm Analysis |
| rear | The end of a queue where a new element is inserted. | 7 · Queues |
| record | A unit of data made of one or more fields that is moved as a whole during sorting. | 19 · Basic Sorting Algorithms |
| recurrence relation | An 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 |
| recursion | A function calling itself with a smaller input. | 1 · Introduction and Algorithm Analysis |
| recursive | Calling itself; using recursion. | 1 · Introduction and Algorithm Analysis |
| red-black tree | A search tree that keeps its height O(lg n) through rules on node colors. | 11 · Search Trees |
| reference count | The 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 |
| relaxation | Updating a distance value when a shorter path is found through an edge. | 18 · Shortest Paths and Activity Networks |
| return address | The address of the instruction at which execution continues when a call ends. | 3 · Recursion, Binary Search and Backtracking |
| reverse-delete | An 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 list | Reversing the order of a list by changing the direction of its links; in place and O(n). | 4 · Linked Lists |
| root | The topmost node of a tree, which has no parent. | 3 · Recursion, Binary Search and Backtracking |
| rotation | An operation that changes the local structure of a tree while preserving the search order. | 11 · Search Trees |
| row-major order | Storing 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 clustering | In quadratic probing, keys with the same home address follow the same probe sequence and block one another. | 14 · Hash Tables |
| selection sort | A 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 tree | A tree that restores its balance by itself through rotations after insertions and deletions. | 11 · Search Trees |
| self-loop | An edge that joins a vertex to itself; simple graphs do not contain them. | 15 · Graphs |
| self-referential struct | A structure with a pointer field of its own type; the basis of linked nodes. | 2 · Arrays and Structures |
| sentinel | A 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 chaining | Keeping the keys that fall into each bucket in a linked list; in the slides it is simply called “chaining”. | 14 · Hash Tables |
| Shell sort | A sort that applies insertion sort to elements far apart, using decreasing gaps. | 19 · Basic Sorting Algorithms |
| short-circuit evaluation | In the && and || operators, not evaluating the remaining operand once the result is known. | 2 · Arrays and Structures |
| shortest path | A path between two vertices whose edge costs have the smallest sum. | 8 · Stack and Queue Applications |
| sibling | Children of the same parent. | 3 · Recursion, Binary Search and Backtracking |
| simple uniform hashing | The 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 list | A linked list in which each node points only to the next node. | 4 · Linked Lists |
| sizeof | The operator that gives the size of a type or object in bytes at compile time. | 1 · Introduction and Algorithm Analysis |
| skewed tree | A tree all of whose nodes extend in a single direction, behaving like a list. | 10 · Trees |
| slack | The difference between the latest and earliest time of a task; zero for critical tasks. | 18 · Shortest Paths and Activity Networks |
| slot | Each cell of a hash table; used synonymously with bucket. | 14 · Hash Tables |
| Sollin's (Borůvka's) algorithm | An MST algorithm that in each round selects the cheapest outgoing edge of every component. | 17 · Minimum Spanning Trees |
| sorting | Putting elements into ascending or descending order by their keys. | 1 · Introduction and Algorithm Analysis |
| space complexity | The amount of memory a program needs as a function of the input size. | 1 · Introduction and Algorithm Analysis |
| spanning forest | In a graph that is not connected, the collection of spanning trees of its components. | 17 · Minimum Spanning Trees |
| spanning tree | A subgraph of a connected graph that joins all its vertices without cycles; it has n − 1 edges. | 15 · Graphs |
| sparse matrix | A matrix most of whose elements are zero; only the nonzero ones are stored. | 5 · Polynomials and Sparse Matrices |
| splay tree | A 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 |
| stack | A 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 overflow | The call stack exceeding its allotted memory; it usually happens with very deep or infinite recursion. | 3 · Recursion, Binary Search and Backtracking |
| string | In C, a char array terminated by '\0'. | 2 · Arrays and Structures |
| struct | A C type that gathers fields of different types into a single record. | 1 · Introduction and Algorithm Analysis |
| subgraph | A graph whose vertices and edges are subsets of the vertices and edges of a graph. | 15 · Graphs |
| subset | A set formed from some of the elements of a set; n elements have 2n subsets. | 3 · Recursion, Binary Search and Backtracking |
| subtree | A tree made of a node and all its descendants. | 9 · The List ADT and Generalized Lists |
| successor | The node that comes immediately after a given node in the inorder sequence; used in deletion and in threaded trees. | 12 · Threaded Binary Trees |
| swap | Exchanging the values of two variables. | 1 · Introduction and Algorithm Analysis |
| synonyms | Keys that fall to the same home address, that is, keys that collide. | 14 · Hash Tables |
| system life cycle | The development process consisting of the requirements, analysis, design, coding, and verification phases. | 1 · Introduction and Algorithm Analysis |
| tagged union | A 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 recursion | Recursion 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 |
| thread | In a threaded tree, a pointer that points to the predecessor or successor in place of an empty child. | 10 · Trees |
| threaded binary tree | A binary tree whose null pointers point to the inorder predecessor and successor. | 10 · Trees |
| time complexity | The number of steps a program executes as a function of the input size. | 1 · Introduction and Algorithm Analysis |
| token | An item processed as a single unit while parsing an expression: an operand, an operator, or a parenthesis. | 8 · Stack and Queue Applications |
| tombstone | In open addressing, a mark placed in a deleted bucket so that a search does not stop there. | 14 · Hash Tables |
| top | The end of a stack where the most recently inserted element is. | 6 · Stacks |
| top-down | A design approach that first treats the problem as a whole and then splits it into ever smaller parts. | 1 · Introduction and Algorithm Analysis |
| topological order | An ordering of vertices in which the tail of every edge comes before its head. | 15 · Graphs |
| tortoise and hare | Floyd'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 float | The 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 Hanoi | The problem of moving disks among three pegs according to the rules; it takes 2n − 1 moves. | 3 · Recursion, Binary Search and Backtracking |
| transpose | The matrix obtained by interchanging the rows and columns of a matrix. | 2 · Arrays and Structures |
| traversal | Visiting every element of a structure once in a particular order. | 2 · Arrays and Structures |
| tree | A hierarchical structure with no cycles that starts from a root and branches into subtrees. | 1 · Introduction and Algorithm Analysis |
| triple | In a sparse matrix, the (row, column, value) record that holds one nonzero element. | 5 · Polynomials and Sparse Matrices |
| typedef | A C declaration that gives a new name to an existing type. | 1 · Introduction and Algorithm Analysis |
| undefined behavior | A 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 |
| underflow | An attempt to remove an element from an empty structure. | 6 · Stacks |
| undirected graph | A graph whose edges have no direction. | 15 · Graphs |
| undo | Reversing the most recent operations in reverse order; implemented with a stack. | 6 · Stacks |
| union | The operation of merging two sets into one. | 16 · Sets and Union-Find |
| union by rank | In 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-find | A disjoint-set structure that supports the union and find operations. | 16 · Sets and Union-Find |
| universal hashing | Choosing 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-heap | Moving an inserted element up to its proper place by swapping with its parent. | 13 · Priority Queues and Heaps |
| vertex | An 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 rule | In 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 case | The running time for the input that needs the most steps among inputs of the same size. | 1 · Introduction and Algorithm Analysis |
| wrap-around | In a circular queue, the index returning to the start after the last cell, by (rear + 1) % MAX. | 7 · Queues |
No terms match your search.
Course page: Data Structures and Algorithms with C · © Sercan Külcü. All rights reserved.