Algorithms 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 |
|---|---|---|
| A* search | A search algorithm that expands nodes in order of f = g + h and is guided by a heuristic to find a shortest path. | 6 · Shortest Paths |
| adaptive (sort) | Describes a sorting algorithm that runs faster when the input is already partially sorted. | 3 · Sorting Algorithms |
| adjacency list | A graph representation that stores a list of neighbors for each vertex, using O(V + E) memory. | 5 · Graph Traversal |
| adjacency matrix | A graph representation that records the presence (or weight) of each edge in a V × V matrix. | 5 · Graph Traversal |
| admissible heuristic | A heuristic that never overestimates the true remaining cost to the goal. | 6 · Shortest Paths |
| Aho–Corasick algorithm | An algorithm that finds many patterns in a text in a single pass, using a trie of the patterns and failure links. | 11 · Tries |
| algorithm | A method that solves a problem in a finite number of clearly defined steps. | 1 · Introduction |
| algorithm analysis | The study of an algorithm's running time and memory requirements as a function of the input size. | 1 · Introduction |
| all-pairs shortest paths | The shortest paths between every pair of vertices (Floyd-Warshall). | 6 · Shortest Paths |
| alphabet | The set of characters that can appear in strings (Σ). | 9 · String Matching and Compression |
| amortized analysis | Finding the cost per operation by dividing the total cost of a sequence of operations by the number of operations. | 2 · Algorithm Complexity |
| ancestor | Any node on the path from a given node up to the root of a tree: its parent, its parent's parent, and so on. | 5 · Graph Traversal |
| articulation point | A vertex whose removal disconnects a connected undirected graph. | 5 · Graph Traversal |
| asymptotic notation | The notations O, Ω and Θ, which describe growth for large n by discarding constant factors and lower-order terms. | 2 · Algorithm Complexity |
| augmenting path | A path from the source to the sink in the residual network along which the flow can be increased. | 8 · Network Flow |
| autocomplete | Suggesting likely words from the prefix typed so far, a typical use of a trie. | 11 · Tries |
| auxiliary space | The memory an algorithm needs in addition to the memory that holds its input; space complexity is usually stated for this. | 2 · Algorithm Complexity |
| average case | The expected number of operations over a given distribution of inputs. | 2 · Algorithm Complexity |
| back edge | In a DFS, an edge to an ancestor that is still on the stack; it signals a cycle. | 5 · Graph Traversal |
| bad character rule | A shifting rule that aligns the mismatched text character with its last occurrence in the pattern. | 9 · String Matching and Compression |
| base case | The smallest case that a recursion solves directly, without calling itself. | 2 · Algorithm Complexity |
| Bellman-Ford algorithm | An algorithm that relaxes all edges V − 1 times and allows negative edge weights. | 6 · Shortest Paths |
| best case | The input of a given size that requires the fewest operations. | 2 · Algorithm Complexity |
| bidirectional search | A search that runs BFS from the source and from the target at the same time and stops when the two waves meet. | 6 · Shortest Paths |
| Big O notation | f(n) = O(g(n)): for large enough n, f is bounded above by a constant multiple of g. | 2 · Algorithm Complexity |
| Big Omega (Ω) | f(n) = Ω(g(n)): for large enough n, f is bounded below by a constant multiple of g. | 2 · Algorithm Complexity |
| Big Theta (Θ) | f(n) = Θ(g(n)): f is both O(g(n)) and Ω(g(n)), so the two grow at the same rate. | 2 · Algorithm Complexity |
| binary search | A search on a sorted array that compares with the middle element and halves the range at each step: O(log n). | 4 · Searching Algorithms |
| binary trie | A trie over the alphabet {0, 1} that stores keys bit by bit. | 11 · Tries |
| bipartite graph | A graph whose vertices can be split into two groups so that every edge joins the two groups. | 5 · Graph Traversal |
| bipartite matching | A set of edges in a bipartite graph with no common endpoints; it can be found with maximum flow. | 8 · Network Flow |
| blocking flow | A flow that blocks every path in the level graph by saturating at least one of its edges. | 8 · Network Flow |
| Borůvka's algorithm | An MST algorithm that adds the lightest outgoing edge of every component in each round. | 7 · Minimum Spanning Trees |
| bottleneck | The smallest residual capacity on an augmenting path, which is the amount of flow added in that round. | 8 · Network Flow |
| Boyer-Moore algorithm | A search that compares the pattern from right to left and makes large shifts. | 9 · String Matching and Compression |
| breadth-first search (BFS) | A traversal that visits vertices layer by layer in order of distance from the start, using a queue. | 5 · Graph Traversal |
| bridge | An edge whose removal splits the graph into more components. | 7 · Minimum Spanning Trees |
| brute force (naive) | An approach that tries every possibility one by one. | 9 · String Matching and Compression |
| bubble sort | A sort that compares neighboring items and swaps them when out of order; each pass moves the largest item to the end. | 3 · Sorting Algorithms |
| bucket | Each cell of the array in a hash table. | 4 · Searching Algorithms |
| bucket sort | A sort that distributes items into buckets by value range and then sorts each bucket. | 3 · Sorting Algorithms |
| Burrows–Wheeler transform (BWT) | A reversible transform that takes the last column of the sorted rotations of a string and makes compression easier. | 10 · Advanced String Algorithms |
| call stack | The stack of frames that holds the parameters, local variables and return address of each method call. | 2 · Algorithm Complexity |
| capacity | The largest amount of flow that can pass through an edge. | 8 · Network Flow |
| catastrophic backtracking | When a backtracking regular-expression engine tries exponentially many alternatives because of nested quantifiers and appears to hang. | 10 · Advanced String Algorithms |
| collision | Two different keys hashing to the same value. | 4 · Searching Algorithms |
| comparison sort lower bound | Every comparison-based sort needs Ω(n log n) comparisons in the worst case. | 3 · Sorting Algorithms |
| 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. | 5 · Graph Traversal |
| complexity class | A group of algorithms with the same growth rate (constant, logarithmic, linear, and so on). | 2 · Algorithm Complexity |
| complexity theory | The field that studies the resources an algorithm uses, such as time and memory, as a function of the input size. | 2 · Algorithm Complexity |
| compressed trie (radix tree) | A trie that merges chains of single-child nodes into a single edge. | 11 · Tries |
| compression | Representing data with fewer bits. | 9 · String Matching and Compression |
| compression ratio | The compressed size divided by the original size; the smaller it is, the better the compression. | 9 · String Matching and Compression |
| connected component | A maximal set of vertices that are joined to one another by paths. | 7 · Minimum Spanning Trees |
| consistent heuristic | A heuristic that satisfies h(u) ≤ w(u, v) + h(v) for every edge (u, v) and h(goal) = 0. | 6 · Shortest Paths |
| constant time | A running time that does not depend on the input size: O(1). | 1 · Introduction |
| correctness | The property that an algorithm produces the correct output for every valid input. | 1 · Introduction |
| counting sort | A non-comparison sort that counts small integer keys and places them using prefix sums. | 3 · Sorting Algorithms |
| cubic | O(n³) growth; for example, straightforward matrix multiplication. | 1 · Introduction |
| cut (s-t cut) | A split of the vertices into an s side and a t side; its capacity is the sum of the capacities of the edges going from the s side to the t side. | 8 · Network Flow |
| cut property | The lightest edge crossing a cut belongs to some MST. | 7 · Minimum Spanning Trees |
| cycle | A closed path that returns to its starting vertex without repeating an edge. | 5 · Graph Traversal |
| cycle property | The heaviest edge of a cycle (if it is unique) belongs to no MST. | 7 · Minimum Spanning Trees |
| decision tree | A tree that models a comparison-based algorithm: internal nodes are comparisons and leaves are the resulting orderings. | 3 · Sorting Algorithms |
| decrease and conquer | An approach that solves a problem by reducing it to a single smaller subproblem (for example, binary search). | 4 · Searching Algorithms |
| definiteness | The property that every step is defined precisely and unambiguously. | 1 · Introduction |
| degree | The number of edges attached to a vertex; in a directed graph, in-degree and out-degree are counted separately. | 5 · Graph Traversal |
| depth-first search (DFS) | A traversal that goes as deep as possible along one branch and then backtracks (using a stack or recursion). | 5 · Graph Traversal |
| deterministic algorithm | An algorithm that follows the same steps and gives the same output every time it runs on the same input. | 1 · Introduction |
| deterministic finite automaton (DFA) | A finite state machine with exactly one transition for every (state, symbol) pair. | 10 · Advanced String Algorithms |
| Dijkstra's algorithm | A shortest-path algorithm for non-negative weights that repeatedly picks the vertex with the smallest distance and relaxes its edges. | 6 · Shortest Paths |
| Dinic's algorithm | A maximum-flow algorithm that finds blocking flows in level graphs: O(V²·E). | 8 · Network Flow |
| directed acyclic graph (DAG) | A directed graph with no cycles; it plays a special role in task scheduling. | 5 · Graph Traversal |
| directed graph | A graph whose edges have a direction. | 5 · Graph Traversal |
| distance | The length of a shortest path to a vertex; for strings, a measure of the difference between two strings. | 6 · Shortest Paths |
| dynamic array | An array that grows by copying its contents into a larger array when it becomes full (for example, Java's ArrayList). | 2 · Algorithm Complexity |
| edge | A connection between two vertices; it may be directed and may carry a weight. | 5 · Graph Traversal |
| edit distance | The minimum number of insertions, deletions and substitutions needed to turn one string into another. | 10 · Advanced String Algorithms |
| Edmonds-Karp algorithm | Ford-Fulkerson with augmenting paths chosen by BFS (fewest edges): O(V·E²). | 8 · Network Flow |
| effectiveness | The property that every step is basic enough to be carried out in finite time with pencil and paper. | 1 · Introduction |
| end-of-word marker | A mark on a trie node showing that the path from the root to that node spells a word. | 11 · Tries |
| Euclid's algorithm | An algorithm that finds the greatest common divisor of two numbers by repeated division with remainder. | 1 · Introduction |
| excess flow | The amount by which the flow entering a vertex exceeds the flow leaving it. | 8 · Network Flow |
| exponential | Growth such as O(2ⁿ), where the running time doubles each time n increases by one. | 1 · Introduction |
| exponential search | A method that grows the range as 1, 2, 4, … and then applies binary search. | 4 · Searching Algorithms |
| factorial | O(n!) growth, such as trying all permutations. | 1 · Introduction |
| failure link | In Aho–Corasick, a link from a node to the node for the longest proper suffix of its string that is present in the trie. | 11 · Tries |
| finite state machine (FSM) | A model of computation made up of a finite number of states and transitions that depend on the input. | 10 · Advanced String Algorithms |
| finiteness | The property that an algorithm terminates after a finite number of steps for every input. | 1 · Introduction |
| flow conservation | At every vertex other than the source and the sink, the incoming flow equals the outgoing flow. | 8 · Network Flow |
| flow network | A directed graph whose edges have capacities and which carries flow from a source to a sink. | 8 · Network Flow |
| Floyd-Warshall algorithm | A dynamic-programming algorithm that finds all-pairs shortest paths by adding intermediate vertices one at a time: O(V³). | 6 · Shortest Paths |
| Ford-Fulkerson method | A general method that keeps increasing the flow until no augmenting path remains. | 8 · Network Flow |
| good suffix rule | A shifting rule based on another occurrence in the pattern of the suffix that has just matched. | 9 · String Matching and Compression |
| graph | A structure made of vertices and the edges that connect them: G = (V, E). | 5 · Graph Traversal |
| graph traversal | Systematically visiting all reachable vertices of a graph. | 5 · Graph Traversal |
| greedy best-first search | A search that looks only at the estimated remaining cost to the goal; it rushes toward the goal but ignores the cost of the path so far. | 6 · Shortest Paths |
| growth rate | How fast a function grows as n grows; the basis for comparing algorithms. | 2 · Algorithm Complexity |
| hash function | A function that maps a key to a table index. | 4 · Searching Algorithms |
| hash table | A table that stores keys at positions given by a hash function, with O(1) search on average. | 4 · Searching Algorithms |
| heap | A complete binary tree in which every node is greater than its children (max-heap) or smaller than its children (min-heap). | 3 · Sorting Algorithms |
| heap sort | A sort that builds a max-heap from the array and then repeatedly moves the root to the end. | 3 · Sorting Algorithms |
| heuristic | A rule or function that gives a good result or estimate without any guarantee of exactness. | 6 · Shortest Paths |
| in-place | Using only O(1) (or very little) extra memory besides the input. | 3 · Sorting Algorithms |
| input | The values, drawn from a specified set, that an algorithm receives at the start. | 1 · Introduction |
| input size | The value n that measures the size of a problem (array length, number of vertices, and so on). | 1 · Introduction |
| insertion sort | A sort that inserts each item into its correct place in the sorted part. | 3 · Sorting Algorithms |
| interpolation search | A search that estimates the position of the target from the end values; O(log log n) on uniformly distributed data. | 4 · Searching Algorithms |
| inversion | A pair of indices with i < j and a[i] > a[j]. | 3 · Sorting Algorithms |
| iterated logarithm | log* n: the number of times log₂ must be applied to n before the result is 1 or less. | 2 · Algorithm Complexity |
| iterative deepening DFS (IDDFS) | A series of DFS runs with the depth limit raised to 0, 1, 2, and so on; it combines DFS's small memory use with BFS's guarantee of finding the shallowest solution. | 5 · Graph Traversal |
| jump search | A method that jumps ahead in steps of √n in a sorted array and then searches linearly within the block. | 4 · Searching Algorithms |
| Knuth-Morris-Pratt (KMP) | An algorithm that searches in O(n + m) without moving backward in the text, using the LPS table. | 9 · String Matching and Compression |
| Kruskal's algorithm | An MST algorithm that scans edges in order of weight and adds those that do not form a cycle. | 7 · Minimum Spanning Trees |
| Lempel-Ziv-Welch (LZW) | A compression method that adds seen strings to a dictionary and encodes them as dictionary indices. | 9 · String Matching and Compression |
| level graph | The subgraph made of the edges that go from one BFS level to the next. | 8 · Network Flow |
| Levenshtein distance | The edit distance in which each insertion, deletion and substitution costs 1. | 10 · Advanced String Algorithms |
| lexicographic order | Comparing strings character by character in alphabetical order. | 10 · Advanced String Algorithms |
| linear | Growing in proportion to n: O(n). | 1 · Introduction |
| linear probing | Resolving a collision by searching for the next empty cell and placing the key there. | 4 · Searching Algorithms |
| linear search | A search that examines the items one by one from the beginning: O(n). | 4 · Searching Algorithms |
| linearithmic | O(n log n) growth; the class of efficient comparison-based sorts. | 2 · Algorithm Complexity |
| load factor | The ratio of the number of keys in the table to the number of cells (α = n/m). | 4 · Searching Algorithms |
| logarithmic | Growing in proportion to log n; for example, binary search. | 4 · Searching Algorithms |
| longest common prefix | The longest beginning shared by all strings in a set of strings. | 11 · Tries |
| longest prefix match | Choosing the longest of the prefixes that match an address; the basic rule of IP routing. | 11 · Tries |
| lookahead / lookbehind | A regular-expression construct that tests whether the text to the right or left matches a pattern without advancing the position. | 10 · Advanced String Algorithms |
| loop invariant | A statement that is true at the start of every iteration of a loop and is used to show that an algorithm is correct. | 3 · Sorting Algorithms |
| lossless / lossy compression | With lossless compression the decompressed data is bit-for-bit identical to the original; with lossy compression perceptually unimportant detail is discarded and the result is only close to the original. | 9 · String Matching and Compression |
| lower bound | A limit that a value cannot go below; Ω notation gives a lower bound. | 2 · Algorithm Complexity |
| LPS table | For each position, the length of the longest proper prefix that is also a suffix. | 9 · String Matching and Compression |
| LSD / MSD radix sort | Radix sort that starts from the least significant digit (right) or the most significant digit (left). | 3 · Sorting Algorithms |
| master theorem | A rule that solves recurrences of the form T(n) = aT(n/b) + f(n) in three cases. | 2 · Algorithm Complexity |
| max-flow min-cut theorem | The value of a maximum flow equals the capacity of a minimum cut. | 8 · Network Flow |
| maximum flow | The largest total flow that can be sent from the source to the sink. | 8 · Network Flow |
| median-of-three | A rule that picks the median of the first, middle and last items as the pivot. | 3 · Sorting Algorithms |
| merge | The operation that combines two sorted arrays into one sorted array. | 3 · Sorting Algorithms |
| merge sort | A sort that splits the array in half, sorts each half and then merges the sorted halves. | 3 · Sorting Algorithms |
| minimum spanning forest | A minimum spanning tree for each component of a graph that is not connected. | 7 · Minimum Spanning Trees |
| minimum spanning tree (MST) | A spanning tree with the smallest possible total edge weight. | 7 · Minimum Spanning Trees |
| negative cycle | A cycle whose weights add up to a negative number; if one exists, shortest paths are undefined. | 6 · Shortest Paths |
| nondeterministic finite automaton (NFA) | A finite state machine that allows zero, one or several transitions for a (state, symbol) pair. | 10 · Advanced String Algorithms |
| open addressing | A hashing method in which a colliding key is placed in another empty cell of the table. | 4 · Searching Algorithms |
| output | The result an algorithm produces, which has a specified relationship to the input. | 1 · Introduction |
| parent | The node directly above a node in a tree; BFS and DFS trees, Prim's algorithm and union-find store it in a parent array. | 5 · Graph Traversal |
| partition | Splitting an array into items smaller than the pivot and items larger than it (Lomuto, Hoare). | 3 · Sorting Algorithms |
| path | A sequence of vertices obtained by moving along one edge at a time from vertex to neighbor; its length is the number of edges it contains. | 5 · Graph Traversal |
| path compression | Linking the nodes visited during a find operation directly to the root. | 7 · Minimum Spanning Trees |
| pattern | The string being searched for in the text (P). | 9 · String Matching and Compression |
| prefix | A part taken from the beginning of a string. | 9 · String Matching and Compression |
| prefix doubling | Building a suffix array by doubling the length of the sorted prefixes in each round. | 10 · Advanced String Algorithms |
| prefix function | In KMP, a table that depends only on the pattern and gives the shift for each possible match length; another name for the LPS table, also written π. | 9 · String Matching and Compression |
| prefix query | Finding all keys that start with a given prefix. | 11 · Tries |
| preflow | A flow that respects the capacity constraints but allows excess flow at vertices other than the source instead of conservation; push-relabel works with it. | 8 · Network Flow |
| Prim's algorithm | An MST algorithm that grows a tree from one vertex by adding the lightest outgoing edge. | 7 · Minimum Spanning Trees |
| primary clustering | In linear probing, the tendency of occupied cells to form long consecutive blocks. | 4 · Searching Algorithms |
| priority queue | A structure that quickly returns the item with the smallest (or largest) key, usually implemented with a heap. | 6 · Shortest Paths |
| probe | The operation of looking at an array cell and comparing it with the value being searched for. | 4 · Searching Algorithms |
| proper prefix | A prefix that is not equal to the string itself; likewise, a proper suffix is a suffix not equal to the string itself. | 9 · String Matching and Compression |
| pseudocode | A way of describing an algorithm step by step without depending on a programming language. | 5 · Graph Traversal |
| push-relabel | A method that finds a maximum flow by pushing excess flow at vertices according to their heights. | 8 · Network Flow |
| quadratic | O(n²) growth; typically two nested loops. | 3 · Sorting Algorithms |
| quantifier | An element of a regular expression (*, +, ?, {m,n}) that says how many times an item may repeat. | 10 · Advanced String Algorithms |
| quick sort | An algorithm that partitions around a pivot and sorts both sides recursively. | 3 · Sorting Algorithms |
| Rabin-Karp algorithm | A search algorithm that compares the hash values of windows. | 9 · String Matching and Compression |
| radix sort | A method that sorts keys digit by digit using a stable sort (LSD, MSD). | 3 · Sorting Algorithms |
| random-access machine (RAM) | An abstract model of computation in which every basic operation and every memory access takes one unit of time. | 2 · Algorithm Complexity |
| recurrence (relation) | An equation that defines T(n) in terms of the values of T on smaller inputs. | 2 · Algorithm Complexity |
| recursion | A function calling itself to solve a smaller instance of the problem. | 2 · Algorithm Complexity |
| recursion tree | A tree that shows the recursive calls and the work done at each level; used to solve recurrences. | 2 · Algorithm Complexity |
| reference (child pointer) | A link from a node to one of its children. | 11 · Tries |
| regular expression | A formal expression that describes a set of strings (a search pattern). | 10 · Advanced String Algorithms |
| regularity condition | The condition a · f(n/b) ≤ k · f(n) (k < 1) required for case 3 of the master theorem. | 2 · Algorithm Complexity |
| relaxation | If d[u] + w(u, v) < d[v], updating the distance estimate and the parent of v. | 6 · Shortest Paths |
| residual capacity | The amount of flow that can still be sent through an edge: c − f. | 8 · Network Flow |
| residual network | A network that shows the remaining capacity on each edge and the flow that can be undone (the reverse edge). | 8 · Network Flow |
| reverse-delete algorithm | An MST algorithm that examines edges from heaviest to lightest and deletes those whose removal does not disconnect the graph. | 7 · Minimum Spanning Trees |
| rolling hash | A hash that can be updated in O(1) when the window slides by one position. | 9 · String Matching and Compression |
| run-length encoding (RLE) | A compression method that writes consecutive repeats as (value, count) pairs. | 9 · String Matching and Compression |
| running time | The number of basic operations an algorithm performs, or the time it takes, on a particular input. | 2 · Algorithm Complexity |
| saturated edge | An edge whose flow equals its capacity, that is, f(u, v) = c(u, v); no more flow can be sent through it. | 8 · Network Flow |
| search problem | Finding whether a value occurs in a data set and, if so, where. | 4 · Searching Algorithms |
| selection sort | A sort that selects the smallest item of the unsorted part in each pass and moves it to the front. | 3 · Sorting Algorithms |
| sentinel | A special value placed at the end to remove the bounds check from a loop. | 4 · Searching Algorithms |
| (separate) chaining | Resolving collisions by keeping the keys that fall in the same cell in a list. | 4 · Searching Algorithms |
| shell sort | An insertion sort with a gradually shrinking gap (Donald Shell). | 3 · Sorting Algorithms |
| shortest path | A path between two vertices whose edge weights have the smallest sum. | 6 · Shortest Paths |
| shortest-path tree | A tree rooted at the source in which the only path from the root to each vertex is a shortest path to that vertex. | 6 · Shortest Paths |
| single-source shortest paths | Shortest paths from one source to all vertices (Dijkstra, Bellman-Ford). | 6 · Shortest Paths |
| sorting | Putting items into ascending or descending order by a key. | 3 · Sorting Algorithms |
| source / sink | The vertices where the flow starts (s) and ends (t). | 8 · Network Flow |
| space complexity | How the extra memory an algorithm uses beyond its input grows with the input size. | 2 · Algorithm Complexity |
| spanning tree | An acyclic subgraph of a connected graph that contains all of its vertices (V − 1 edges). | 7 · Minimum Spanning Trees |
| sparse / dense graph | A graph is sparse if its number of edges is far below the maximum V(V − 1)/2 and dense if it is close to that value. | 5 · Graph Traversal |
| spurious hit | In Rabin-Karp, a window whose hash equals the pattern's hash although the characters differ; the verification is wasted. | 9 · String Matching and Compression |
| stable (sort) | Describes a sort that preserves the relative order of items with equal keys. | 3 · Sorting Algorithms |
| stack frame | The space opened on the call stack for the parameters, local variables and return address when a method is called; it is removed when the method returns. | 2 · Algorithm Complexity |
| string | A finite sequence of characters from an alphabet. | 9 · String Matching and Compression |
| string matching | The problem of finding all occurrences of a pattern in a text. | 9 · String Matching and Compression |
| strongly connected component (SCC) | A maximal set of vertices in a directed graph in which there is a path from every vertex to every other vertex. | 5 · Graph Traversal |
| subset construction | A method that converts an NFA into a DFA that recognizes the same language; the DFA states are sets of NFA states. | 10 · Advanced String Algorithms |
| substring | A part of a string made of consecutive characters. | 9 · String Matching and Compression |
| suffix | A part taken from the end of a string. | 9 · String Matching and Compression |
| suffix array | The starting indices of all suffixes of a string, listed in lexicographic order of the suffixes. | 10 · Advanced String Algorithms |
| suffix trie / suffix tree | A trie containing all suffixes of a string; its compressed form is the suffix tree. | 11 · Tries |
| swap | Exchanging the positions of two items. | 3 · Sorting Algorithms |
| ternary search trie (TST) | A kind of trie whose nodes each hold one character together with less-than, equal and greater-than links. | 11 · Tries |
| tight bound | A bound that is both a lower and an upper bound and so gives the growth exactly (Θ). | 2 · Algorithm Complexity |
| time complexity | How the number of basic operations grows with the input size. | 1 · Introduction |
| Timsort | A hybrid sort that processes naturally sorted runs using insertion sort and merging. | 3 · Sorting Algorithms |
| topological sort | An ordering of the vertices of a directed acyclic graph in which every edge goes from left to right. | 5 · Graph Traversal |
| transitive closure | A table that tells, for every pair i, j, whether there is a path from i to j; computed with the Boolean (and/or) version of Floyd-Warshall. | 6 · Shortest Paths |
| trap state | A non-accepting state of an automaton that cannot be left once entered, whatever the input. | 10 · Advanced String Algorithms |
| trie (prefix tree) | A structure that stores strings in a tree whose character-labeled edges are shared by strings with a common prefix. | 11 · Tries |
| undirected graph | A graph whose edges can be traversed in both directions. | 5 · Graph Traversal |
| union by rank | A merging method that attaches the root of the shorter tree to the root of the taller tree. | 7 · Minimum Spanning Trees |
| union-find (disjoint sets) | A structure that manages disjoint sets with find and union operations. | 7 · Minimum Spanning Trees |
| upper bound | A limit that a value cannot exceed; O notation gives an upper bound. | 2 · Algorithm Complexity |
| vertex / node | A point of a graph. | 5 · Graph Traversal |
| weighted graph | A graph in which every edge is assigned a number (a weight or cost). | 5 · Graph Traversal |
| wildcard search | A search in which a wildcard character (.) in the pattern matches any letter. | 11 · Tries |
| worst case | The input of a given size that requires the most operations. | 2 · Algorithm Complexity |
No terms match your search.
Course page: Algorithms · © Sercan Külcü. All rights reserved.