liveBookmanning.com

What you will learn in Advanced Algorithms and Data Structures

by Marcello La Rocca

Read it on liveBook Get the book at manning.com

Chapter by chapter

Concepts explained in this book

• objective functionA loss function is a function that quantifies the discrepancy between model predictions and observed target values.
• k-d treeA k-d tree is a binary space-partitioning tree that organizes points in k-dimensional space by alternating coordinate-based comparisons at successive levels.
• bounding boxA bounding box is an axis-aligned region that contains a geometric object or curve section.
• embeddingA vector is a mathematical quantity with magnitude and direction that can represent a displacement or directed geometric segment.
• centroidA center of mass is the point representing the coordinate-weighted average location of a body or collection of points.
• ss-treeAn SS-tree, or similarity search tree, is a spatial index that organizes multidimensional objects using distance-based regions for approximate or exact nearest-neighbor queries.
• treapA treap is a randomized binary search tree whose nodes satisfy both binary-search-tree ordering by key and heap ordering by priority.
• simulated annealingSimulated annealing is a randomized optimization algorithm that probabilistically accepts some worsening transitions while gradually reducing that probability to escape local optima and approach a global optimum.
• fitnessFitness is a score representing the quality of a candidate solution, with larger or smaller values preferred according to the optimization objective.
• gradient descentGradient descent is an iterative optimization technique that moves a candidate solution in the direction of decreasing objective-function value using gradient information.
• genetic algorithmA genetic algorithm is an evolutionary optimization technique that improves a population of candidate solutions through selection and variation operators inspired by biological reproduction.
• heapA binary heap is a complete binary-tree-based priority queue in which each node has priority at least as high as every node in its subtree.
• chromosomeChromosome encoding is the representation of a candidate solution as a chromosome composed of genes.
• heuristicA heuristic is a problem-solving method that seeks a good or approximate solution without guaranteeing the optimum.
• trieA trie is a tree-based data structure that stores strings by sharing nodes for common prefixes and supports efficient prefix-based lookup.
• bloom filterA Bloom filter is a space-efficient probabilistic data structure for testing set membership that can report false positives but not false negatives.
• MapReduceMapReduce is a distributed-computing model that processes data by applying map operations to records and then aggregating their intermediate results with reduce operations.
• populationA population is a collection of candidate individuals maintained by a genetic algorithm during an evolutionary iteration.
• DBSCANDBSCAN is a density-based clustering algorithm that identifies dense regions and separates them from lower-density points using neighborhood and density parameters.
• crossoverCrossover is a genetic-algorithm technique that recombines genetic material from selected parent solutions to produce one or more child solutions.
• partitionA partition is a division of a set or geometric space into nonoverlapping regions that together cover the original object.
• dataset splitSharding is the technique of partitioning data, users, or transactions across different machines or clusters.
• prefixA prefix is an initial sequence of symbols in a string that can be shared by or matched against other strings.
• canopy clusteringCanopy clustering is a preprocessing technique that forms inexpensive, overlapping groups of nearby data points to reduce the comparisons required by a later clustering algorithm.
• thresholdA threshold is a fixed comparison value that determines when a measured distance is sufficient to include a point in a canopy or exclude it as a future canopy center.
• mutationMutation is a genetic-algorithm variation operator that randomly modifies one or more parts of a candidate solution representation.
• deletionDelete is an operation that removes a node or element from a data structure while preserving its structural invariants.
• core pointA core point in DBSCAN is a data point whose neighborhood contains at least the required number of dataset points within the specified radius.
• optimizationOptimization is the process of improving a solution or computational procedure according to an objective such as cost, quality, or performance.
• random restartRandom restart is a technique that repeatedly begins a search or optimization process from a newly selected state to escape poor regions of the search space.
• cachingCaching is the technique of storing retrieved data or computed results in faster storage for possible reuse.
• hyperparameterA hyperparameter is a configuration value governing an algorithm's behavior that is set independently of the algorithm's learned or computed results.
• clusteringA clustering algorithm groups unlabeled data points into subsets according to relationships or similarities among them.
• K-means clusteringK-means is an iterative clustering algorithm that partitions observations into a specified number of clusters by minimizing within-cluster squared distances to cluster centroids.
• coordinateA coordinate is a numerical component that specifies a point's position along one dimension of a coordinate system.
• priority queueA priority queue is an abstract data structure in which each element has a priority and removal returns an element with the highest or lowest priority according to the queue ordering.
• disjoint setA disjoint-set data structure maintains a partition of elements into nonoverlapping sets and supports finding set representatives and merging sets.
• meanA mean is the arithmetic average obtained by summing numerical values and dividing by their count.
• planar graphGraph planarity is the property of a graph being embeddable on a surface, especially the plane, without edge crossings.
• d-ary heapA d-ary heap is a heap-ordered tree in which each internal node has at most a fixed number d greater than one of children.
• locally optimal solutionA local minimum is a point whose function value is no greater than those of sufficiently nearby points, without necessarily being the smallest value over the entire domain.
• heap invariantA heap invariant is the ordering condition requiring each node's priority to be properly ordered relative to the priorities of its parents or children.
• branching factorA branching factor is the number of child branches or children assigned to each node in a tree-based data structure.
• samplingA random sampling algorithm generates candidate solutions through random choices and selects among the sampled results without iterative optimization after initialization.
• tree rotationA tree rotation is a local restructuring operation that changes parent-child relationships while preserving the in-order sequence of a binary search tree.
• data structureA concrete implementation of an abstract data type consisting of data storage organization and algorithms that manipulate the stored data.
• geneA gene is an individual position in a genetic-algorithm chromosome that represents one optimization variable and its assigned value.
• local searchLocal search is an optimization technique that iteratively improves a candidate solution through nearby modifications.
• planarity testing algorithmA planarity testing algorithm determines whether a graph can be embedded in the plane without edge crossings and may construct such an embedding.
• performanceAn evaluation metric is a quantitative measure of the quality or performance of an algorithm's result.
• OPTICSOPTICS is a density-based clustering algorithm that orders points and computes reachability distances to expose clustering structure across density thresholds.
• curse of dimensionalityThe curse of dimensionality is the set of effects that make data analysis and algorithmic search increasingly difficult as the number of dimensions grows.
• spaceA k-dimensional space is a space in which each point is represented by k coordinates or independent dimensions.
• machine learningMachine learning is a computational technique in which mathematical models infer characteristics or patterns of a system from data.
• hypersphereA hypersphere is the set of points at a fixed distance from a center in a Euclidean space of arbitrary dimension.
• parallelismParallel computing is the execution of multiple computational operations concurrently, typically using multiple processing units.
• profilingProfiling is the measurement of a program's runtime behavior, such as execution time and resource consumption, to identify performance characteristics.
• set intersectionAn edge intersection is a geometric point or region at which two drawn graph edges meet away from their permitted common endpoint.
• elitismElitism is a genetic-algorithm strategy that copies selected high-quality individuals to the next population without alteration.
• planar embeddingA planar embedding is a representation of a graph in the plane in which vertices are distinct points and edges intersect only at shared endpoints.
• radix trieA radix trie is a compressed trie that stores strings by labeling edges with substrings rather than individual characters while sharing common prefixes.
• reachability plotA reachability plot is an ordered visualization of points and their reachability distances that exposes hierarchical density-based cluster structure.
• approximation algorithmAn approximation algorithm computes a solution that is close to an exact or optimal solution without necessarily producing that solution exactly.
• radiusA radius is the maximum distance from a center to the boundary or an included point of a geometric region.
• Euclidean distanceEuclidean distance is the straight-line distance between points in Euclidean space, computed from the square root of the sum of squared coordinate differences.
• findPartitionfindPartition is an operation that identifies the partition containing a specified element in a disjoint-set structure.
• pushdown operationA pushdown operation restores heap ordering by repeatedly moving an element toward the leaves and exchanging it with a higher-priority child when necessary.
• key nodeA key node is a trie node marked to indicate that the character path from the root to that node forms a stored key.
• individualAn organism is a genetic-algorithm candidate solution represented by a chromosome and evaluated by its fitness.
• crossing numberThe crossing number of a graph is the minimum number of edge crossings over all drawings of the graph in a specified drawing model.
• merge methodThe merge method combines the partitions containing two specified elements into a single partition.
• reachability distanceReachability distance is the directed density-based distance from one point to another, determined by the source point's core distance and their actual distance.
• gridA regular grid is a spatial partition that divides a region into equal-sized, regularly arranged cells.
• bounded priority queueA bounded priority queue is a priority queue that retains at most a specified number of elements, typically the highest- or lowest-ranked ones.
• local neighborhoodAn epsilon-neighborhood is the set of points within epsilon distance of a specified point.
• varianceVariance is the mean of the squared differences between values and their mean, measuring their dispersion.
• distanceA distance function is a function that assigns a path-cost contribution or distance value to an edge or other argument.
• amortized analysisAmortized analysis determines the average cost of operations over a sequence, allowing occasional expensive operations.
• noiseNoise consists of data points in low-density regions that are not assigned to a cluster by a density-based clustering algorithm.
• false-positive rateA false-positive rate is the proportion or probability of negative membership queries that a probabilistic test incorrectly reports as positive.
• MapA dictionary is an abstract data structure that stores key-value associations and supports operations such as lookup, insertion, and deletion.
• topThe top operation retrieves the element currently having the highest priority at the top of a priority queue or heap, optionally removing it according to the interface semantics.
• margin regionA margin region is the boundary portion of a shard retained to capture points whose neighborhoods can connect clusters across adjacent shards.
• brute-force searchBrute-force search exhaustively examines the available candidates to find results without using an indexing or pruning strategy.
• min-heapA min-heap is a heap in which each parent has priority at most as high as that of its children, placing a minimum-priority element at the root.
• natural selectionNatural selection is a process in which individuals with traits associated with greater survival or reproduction are more likely to contribute to subsequent generations.
• internal nodeAn internal node is a trie node that has one or more children.
• pointA point is a record representing a position in a multidimensional space through an ordered collection of coordinate values.
• self-balancing binary search treeA balanced tree is a tree data structure whose height is maintained within a logarithmic bound relative to the number of stored elements.
• bubble upBubble up is a heap-maintenance procedure that moves an element toward the root while its priority violates the parent ordering condition.
• binary search treeA binary search tree is a binary tree organized by an ordering relation that places smaller and larger keys in designated subtrees.
• LRUAn LRU cache is a cache that evicts the entry that has been unused for the longest time when it reaches capacity.
• false positiveA false positive is an incorrect positive result indicating that an absent key is present or has an associated value.
• graphAn abstract graph is a graph specified by its vertices and edges without a particular geometric placement.
• force-directed layoutA force-directed graph drawing algorithm positions graph vertices by modeling edges and non-adjacent vertex pairs as distance-dependent attractive and repulsive forces.
• logarithmic time complexityLogarithmic time is a running-time bound that grows proportionally to the logarithm of the input size or another stated size parameter.
• hierarchical clusteringHierarchical clustering is a clustering technique that forms nested groups by successively merging or dividing clusters.
• edgeAn edge is a connection between two vertices in a graph, represented here by an ordered pair of endpoints.
• hillclimbingHill climbing is an iterative local-search technique that moves from a candidate solution to a neighboring solution with an improved objective value.
• memory usageMemory consumption is the amount of memory occupied by a computation or program during execution.
• pruningPruning is the elimination of search-tree branches that cannot contain a valid or better candidate.
• abstract data typeAn abstract data type is a specification of a type's possible values, operations, computational complexities, outputs, and side effects without prescribing its storage representation.
• depth-first searchDepth-first search is a graph traversal algorithm that explores a path as far as possible before backtracking to explore remaining branches.
• spell-checkerA spell checker is software that examines text and identifies words that do not appear to be correctly spelled.
• task prioritizationA heap priority is a value assigned to an element that determines its ordering relative to other elements in a heap.
• Bézier curveA Bézier curve is a parametric curve defined by endpoints and one or more control points using Bernstein polynomial interpolation.
• mapperA mapper is a MapReduce worker that processes an input partition and creates intermediate results for reducers.
• reduction operationA reduce operation combines intermediate information from a homogeneous group of entries to produce a result.
• non-planar graphA non-planar graph is a graph that cannot be embedded in the plane without edge intersections away from shared endpoints.
• straight-line drawingA straight-line drawing is a graph drawing in which every edge is represented by a straight line segment between its endpoint vertices.
• Traveling Salesman problemThe travelling salesman problem asks for the shortest route that visits each specified location exactly once and returns to the starting location.
• greedy algorithmA solution method that repeatedly makes the locally best available choice according to a specified ranking or criterion.
• breadth-first searchBreadth-first search is a graph traversal algorithm that visits vertices in nondecreasing order of their distance in edges from a source vertex.
• Dijkstra's algorithmDijkstra's algorithm computes shortest paths from a source in a graph with nonnegative edge weights by repeatedly selecting the unsettled vertex with minimum tentative distance.
• rectilinear crossing numberThe rectilinear crossing number of a graph is the minimum number of edge intersections over all drawings in which every edge is a straight-line segment.
• hyperrectangleA hyperrectangle is a Cartesian product of intervals forming a multidimensional axis-aligned region defined by minimum and maximum bounds along each coordinate.
• least frequently usedA least frequently used cache is a cache that evicts the entry with the lowest access frequency, using a tie-breaking rule when frequencies are equal.
• high-dimensional dataMultidimensional data consists of points or records described by multiple independent coordinates or dimensions.
• tree heightTree height is the number of edges on the longest path from a tree's root to a leaf.
• node mergeA node merge combines an underfull tree node with one of its sibling nodes and updates their parent structure.
• generationA generation is one successive stage of a population in an evolutionary process.
• metaheuristicA metaheuristic is a general-purpose optimization strategy that guides the search for good solutions without guaranteeing an optimum.
• split heuristicA split heuristic is a rule for partitioning the entries of an overflowing tree node into separate groups.
• wheel arrayA wheel array is a cumulative-probability array whose entries represent the accumulated normalized fitness of population individuals.
• normalized fitnessNormalized fitness is an individual's fitness divided by the sum of the fitness values of the population.
• roulette-wheel selectionRoulette wheel selection is a genetic-algorithm technique that assigns each individual a selection probability proportional to its fitness.
• selectionA selection technique is a genetic-algorithm method for choosing individuals that survive or reproduce in the next generation.
• tournament selectionTournament selection is a genetic-algorithm technique that randomly samples individuals and selects the one with the best fitness from the sample.
• gradientA gradient is the vector of partial derivatives of a multivariable scalar function, indicating the direction of greatest local increase.
• partial derivativeA partial derivative is the derivative of a multivariable function with respect to one coordinate while the other coordinates are held constant.
• dimensionA dimension is an independent coordinate axis or degree of freedom needed to specify a point in a space.
• A-star algorithmThe A* algorithm is a best-first shortest-path search algorithm that prioritizes vertices using the cost already incurred plus a heuristic estimate of the remaining cost.
• complete bipartite graphA complete bipartite graph has two disjoint vertex partitions with every vertex in one partition adjacent to every vertex in the other and no edges within a partition.
• complete graphA complete graph is a simple graph in which every pair of distinct vertices is connected by an edge.
• elbow methodThe elbow method is a model-selection technique that chooses a parameter value at the point where additional complexity yields diminishing improvement in an evaluation measure.
• range queryA region query retrieves the data points within a specified radius of a given point.
• contractAn API is a defined interface through which software requests operations or data from another software component or service.
• path compressionPath compression is a disjoint-set heuristic that makes nodes on a find path point directly or more closely to the set representative.
• updateA priority update is an operation that changes an element's priority within a priority-ordered data structure.
• max heapA max-heap is a heap-ordered tree in which every parent has a key greater than or equal to those of its children, making the maximum element accessible at the root.
• distributed systemA distributed system is a system whose components execute across multiple networked computers and communicate by exchanging messages.
• eviction policyAn eviction policy is a rule for selecting an element to remove from a full cache when space is needed for a new entry.
• Kuratowski's theoremKuratowski's theorem states that a finite graph is planar exactly when it contains neither a subdivision of the complete graph K5 nor a subdivision of the complete bipartite graph K3,3.
• average-case hardnessAverage-case hardness is the difficulty of solving problem instances according to a specified typical or practical input distribution.
• lockingA lock is a synchronization primitive that coordinates access to shared resources by allowing mutually exclusive ownership.
• approximate search algorithmApproximate similarity search retrieves near-neighbor results while allowing bounded or practical deviations from the exact nearest results to improve performance.
• projectionA projection maps points onto a selected axis or lower-dimensional subspace by retaining their coordinates in that direction.
• edge weightA weight is a numerical value associated with a graph edge to represent its cost, distance, or other measure.
• biconnected componentA biconnected component is a maximal graph substructure that remains connected after the removal of any single vertex, subject to standard block decomposition conventions.
• heapifyHeapify is a bottom-up procedure that transforms an arbitrary collection represented as a heap array into a valid heap.
• race conditionA race condition is a concurrency error in which program behavior depends on the timing or interleaving of operations.
• substringA substring is a contiguous sequence of characters contained within a string.
• control pointA control point is a point that determines the shape and direction of a Bézier curve without generally lying on the curve.
• bounding-envelope overlapBounding-envelope overlap is the spatial intersection between the regions enclosing different indexed nodes or objects.
• permutationA permutation is an arrangement of the elements of a sequence in which each element occurs exactly once.
• keyA dictionary key is a value that identifies an associated entry in a dictionary.
• connected graphA connected graph is a graph in which every pair of vertices is joined by a sequence of edges.
• symmetric quadratic Bézier curveA symmetric quadratic Bézier curve is a quadratic Bézier curve whose control point is equidistant from its two endpoints.
• intra-cluster distanceIntra-cluster average distance is the average pairwise distance between points within the same cluster.
• constant timeConstant time is a running-time bound independent of the input size, up to a fixed bound.
• convergenceConvergence is the condition in an iterative computation where successive updates no longer change the solution or assignment.
• knapsack problemAn optimization problem that selects each item at most once to maximize total value subject to a capacity constraint.
• compression tableA compression table is a mapping from characters to the bit sequences assigned by a compression code.
• Huffman encodingHuffman coding is a lossless compression technique that represents symbols with variable-length prefix codes based on their frequencies.
• prefix codeA prefix code is a code in which no valid code sequence is a prefix of another valid code sequence.
• precisionPrecision is the proportion of positive membership-test results that correspond to elements actually present in the represented set.
• vertex coverThe minimum vertex cover is the smallest subset of vertices in a graph such that every edge has at least one endpoint in the subset.
• pivotA pivot is a selected element whose value determines how a collection is divided during a partitioning procedure.
• binary stringA bit string is a finite sequence of binary digits used to represent information or a candidate solution.
• reachabilityA density-reachable point is a point connected to another point through a chain of core points satisfying the neighborhood-radius condition.
• genotypeA genotype is the chromosome-based encoding of an organism in a genetic or evolutionary model.
• phenotypeA phenotype is the expressed candidate solution or observable outcome associated with an organism in an evolutionary model.
• K3,3K3,3 is the complete bipartite graph whose two vertex partitions each contain three vertices.
• K5K5 is the complete graph on five vertices, with one edge connecting every pair of distinct vertices.
• treeA tree is a hierarchical data structure composed of nodes connected by parent-child relationships without cycles.
• hyperparameter tuningParameter fine-tuning is the systematic refinement of tested parameter values around the most promising settings.
• adjacent swap mutationAdjacent swap mutation modifies a tour by swapping vertices that are adjacent in the representation.
• random swap mutationRandom swap mutation modifies a tour by swapping vertices selected from arbitrary pairs rather than only adjacent pairs.
• induced subgraphAn induced subgraph is the graph formed by selecting a subset of vertices and retaining every original edge whose endpoints are both selected.
• spanning subgraphA spanning subgraph is a subgraph that contains every vertex of its original graph and a subset of its edges.
• deadlockA deadlock is a state in which concurrent execution cannot proceed because threads wait indefinitely for resources held by one another or for unreleased locks.
• prefix searchPrefix search is an operation that retrieves all stored strings beginning with a specified prefix.
• longest prefix lookupA longest prefix lookup finds the longest stored key that is a prefix of a specified input string.
• balanced k-d treeA balanced k-d tree is a k-d tree whose recursive partitions keep its height bounded relative to the number of stored points.
• crossing edgeAn edge crossing is a geometric intersection between two graph edges at a point that is not a shared endpoint.
• edit distanceEdit distance is the minimum number of character insertions, deletions, or substitutions needed to transform one string into another.
• z-score normalizationZ-score normalization transforms each feature by subtracting its mean and dividing by its standard deviation.
• bipartite graphA bipartite graph is a graph whose vertices can be partitioned into two groups with edges only between the groups; in this section the graph is also required to be connected.
• binary searchBinary search is a search algorithm that repeatedly halves an ordered search range to locate a target or its insertion position.
• arrayAn array is a data structure that stores elements associated with positions, typically supporting access to an element by its index.
• transition operatorA transition operator is a rule that generates a new candidate solution from the current solution.
• source pointA source is the distinguished network vertex through which flow originates and which has no inbound flow.
• subgraphA subgraph is a graph formed from a subset of the vertices and edges of another graph.
• admissible heuristicAn admissible heuristic is a heuristic that never overestimates the cost of reaching a goal from a given state.
• consistent heuristicA consistent heuristic is a heuristic whose estimate at a successor is no greater than the estimate at its predecessor plus the transition cost between them.
• tourA tour is a closed sequence of locations that visits the required locations and returns to its starting location.
• linear time complexityLinear time is a running-time bound proportional to the number of vertices and edges or other input elements being processed.
• array partitionArray partition rearranges or separates an array around a pivot so that elements on opposite sides satisfy the required ordering relation.
• balanced k-d tree constructionBalanced k-d tree construction is a recursive algorithm that selects coordinate-wise medians as pivots to build a balanced k-d tree.
• linearithmic functionLinearithmic time is a running-time complexity proportional to the product of the input size and its logarithm.
• medianA median is a middle-ranked value that divides an ordered collection into lower and higher portions.
• shortest pathA shortest path is a path between graph vertices having minimum total edge distance or cost.
• recenteringRecentering is the replacement of each cluster centroid with the center of mass of its assigned points.
• invariantAn invariant is an internal property of a data structure or mathematical object that remains true throughout a process or across permitted transformations.
• near-optimal solutionA near-optimal solution is a feasible solution whose objective value is close to the best possible value without necessarily being optimal.
• search spaceA problem space is the set of candidate solutions and their possible transformations for an optimization problem.
• linear regressionLinear regression is a supervised-learning technique that models the relationship between input variables and a real-valued dependent variable using a parameterized function.
• acceptance probabilityAcceptance probability is the probability that an optimization algorithm accepts a proposed transition, particularly one that increases the cost.
• Iterative MapReduceIterative MapReduce is a MapReduce execution model that reuses workers and data partitions across repeated computation cycles.
• array representationAn array representation stores a tree's nodes in index order so that parent and child relationships can be computed without explicit pointers.
• dendrogramA dendrogram is a tree diagram that represents the hierarchical arrangement of clusters.
• maximum edit distanceMaximum tolerance is the largest permitted difference between two strings for a similarity search.
• atomicityAn atomic operation is an operation that appears indivisible to concurrent observers, with no visible intermediate state.
• split indexA split index is a position in an ordered sequence that separates its entries into two partitions.
• plateauA plateau is a region of a function over which the objective value remains constant or changes too little to distinguish nearby positions.
• approximation errorApproximation error is a nonnegative factor that bounds how far an approximate nearest-neighbor result may be from the corresponding exact result.
• pruning criterionA pruning criterion is a rule that compares a branch's possible distance with the current nearest-neighbor distance to decide whether to skip the branch.
• edge labelAn edge label is the string or character stored on a tree edge to identify the portion of a key represented by that edge.
• stackA stack is a container abstraction in which removal returns the most recently inserted element that remains, following last-in-first-out order.
• hard clusteringA flat hard-clustering algorithm assigns each point to at most one cluster and represents all clusters at the same hierarchy level.
• cache hitA cache hit occurs when a requested data item is present in the cache and can be accessed there.
• doubly linked listA doubly-linked list is a linked list whose nodes contain links to both their predecessors and successors.
• regionA region is a subset of the search space associated with the points reachable through a particular tree node.
• maximum flowMaximum flow is the problem of sending the greatest possible amount through a capacitated network from a source to a sink while respecting edge capacities and flow conservation.
• distributed cachingA distributed cache is a cache partitioned across multiple processes or nodes that coordinate request routing and data storage.
• edge pointAn edge point is a non-core point that is reachable from at least two different core points or clusters.
• dynamic programmingDynamic programming is an algorithmic technique that solves overlapping subproblems once, stores their results, and combines them to solve the original problem.
• pass-through nodeA pass-through node is a non-key tree node with one outgoing edge whose parent also has one outgoing edge, allowing the path through both nodes to be compressed.
• partial orderA partial ordering is a relation in which only some pairs of elements are required to be comparable, while the relation remains reflexive, antisymmetric, and transitive.
• metricA metric is a nonnegative function on pairs of points that is zero only for identical points, symmetric, and satisfies the triangle inequality.
• edge capacityEdge capacity is the maximum amount of flow that a network edge can carry.
• information flowFlow is an assignment of real-valued amounts to network edges that respects edge capacities and conserves flow at intermediate vertices.
• Bézier subdivisionBézier subdivision is a technique that recursively splits Bézier curves into smaller curve sections for geometric analysis.
• convex hullA convex hull is the smallest convex set containing a given set or geometric shape.
• interval subdivisionInterval subdivision is a curve-intersection technique that splits a curve into monotone sections and refines their parameter intervals.
• tangentA tangent is a line that touches a curve at a point and represents its instantaneous direction there.
• double hashingA double hashing function derives multiple hash values or positions from two base hash results.
• epistasisEpistasis is the degree to which variables in an optimization problem interact so that changing one variable affects the values or constraints of others.
• region searchRegion search is the operation of finding dataset points that lie within a specified region of a multidimensional space.
• dynamic setA dynamic dataset is a dataset whose contents can change through insertions and removals while it is indexed.
• supervised learningSupervised learning is machine learning in which a model is trained from examples paired with labels or target values.
• right rotationA right rotation is a binary-search-tree rotation in which a node's left child becomes the root of the rotated subtree.
• adjacency listAn adjacency list is a graph representation that stores, for each vertex, a list of its incident or outgoing edges and neighboring vertices.
• inner productThe dot product is a scalar operation on vectors equal to the sum of the products of corresponding coordinates and related to their angle.
• vector-to-vector productThe cross product is a vector operation in three-dimensional space whose result is perpendicular to its two operand vectors and whose magnitude depends on their sine-separated area.
• associativityAn associative operation gives the same result regardless of how operands are parenthesized, so regrouping intermediate results does not change the outcome.
• data transformationA map operation transforms each input record or partition into intermediate information relevant to a later computation.
• k-ary treeA k-ary tree is a tree in which each node has at most k children, with child links distinguished by symbols from an alphabet.
• synchronizationSynchronization is the coordination of concurrent operations to control access to shared state and preserve required execution properties.
• np-complete problemA decision problem that belongs to NP and is at least as hard as every problem in NP under polynomial-time reductions.
• determinismA deterministic algorithm produces the same processing sequence and results for the same input and starting conditions, apart from unspecified tie handling.
• graph coloringGraph coloring is the assignment of colors to graph vertices subject to specified restrictions on the colors of adjacent vertices.
• immutable collectionImmutability is the property that an existing object or data structure cannot be changed after creation, so updates produce a new structure or version.
• cache entryA cache entry is one stored key-associated item or computed result contained in a cache.
• binary partitioningBinary partitioning divides a collection or spatial region into two subregions according to a selected dividing value.
• hyperplaneA hyperplane is a flat affine subspace of one dimension less than its surrounding space that divides the space into two half-spaces.
• nodeA vertex is a node in a graph that may be connected to other vertices by edges.
• remote procedure callA remote call is an invocation of an operation provided by a component running outside the caller's local process or machine.
• box-and-whisker plotA boxplot is a statistical visualization that summarizes a distribution using quartiles, a median, and selected extreme-value markers.
• data frameA DataFrame is a two-dimensional labeled tabular data structure whose columns can have different types.
• trainingTraining is the process of fitting a model's parameters from data so that the model approximates the desired relation.
• refresh-ahead cachingRefresh-ahead is a caching policy that proactively refreshes frequently requested entries before they expire.
• write-behind cachingWrite-behind is a storage policy that writes changes to a cache immediately and propagates them to backing storage later under specified conditions.
• write-through cachingWrite-ahead caching writes data to a cache before writing it to the underlying storage system.
• hyper-spherical regionA hyper-spherical region is the set of points within a specified radius of a center point in multidimensional space.
• sorted listA sorted list is a sequence of elements maintained in an order that supports locating an element's position by comparison.
• intermediate levelAn intermediate level is a workflow stage that receives grouped partial results and processes them before a final aggregation stage.
• memory boundA bottleneck is a component or operation that limits the overall throughput or performance of a system.
• adjacency matrixAn adjacency matrix is a matrix representation of a graph in which entries indicate whether pairs of vertices are connected, and may encode edge information.
• curve-line drawingA curve-line drawing represents graph edges as curves rather than restricting them to straight-line segments.
• labelA label is the target category or value associated with an example in supervised learning.
• total cohesionTotal cohesion is a measure of how closely points are grouped within their clusters, here based on cosine distance to a cluster center.
• unsupervised learningUnsupervised learning is machine learning that analyzes unlabeled data to discover structure or patterns without predefined categories.
• exponential time complexityAn exponential-time algorithm has a running time that grows exponentially with the size of its input in the worst case.
• memoizationMemoization is a technique that caches the results of computations so repeated calls with the same inputs can reuse them.
• recurrenceA recurrence relation is an equation that defines a sequence or function in terms of values for preceding or smaller instances.
• overlap checkAn overlap check is a geometric test that determines whether node bounding regions intersect substantially or one is contained in another.
• reorganization heuristicA reorganization heuristic reclusters the grandchildren of a node to replace its children with a configuration having less overlap and lower variance.
• frontierA frontier is the queue of graph vertices discovered but not yet visited during a breadth-first search.
• reentrant lockA reentrant lock is a lock that allows the thread holding it to acquire it repeatedly, tracking nested acquisitions with a counter until matching releases occur.
• meta-algorithmA meta-algorithm is a general algorithmic template whose problem-specific components are supplied to solve different instances.
• variable interactionVariable interaction is the dependence in an optimization problem whereby the value or constraints of one variable are affected by another variable.
• simulated annealing with restartSimulated annealing with restart is a simulated-annealing variant that returns to one of several previously found high-quality states when progress becomes stuck.
• continuous improvementAn iteration is one repetition of an algorithmic cycle or update sequence.
• confidenceConfidence is the conditional frequency with which one product is purchased when another product is purchased.
• disjoint setA disjoint group is a collection of elements that shares no elements with another group in the same partition.
• Monte Carlo simulationA Monte Carlo algorithm is a randomized algorithm that permits a bounded probability of an incorrect result in exchange for controlled resource usage.
• non-personalized recommendationA non-personalized recommendation is a product suggestion presented without targeting it to an individual customer's profile or history.
• RectangleA rectangle is a planar quadrilateral with four right angles used here as the spatial region associated with an R-tree node.
• treap removalTreap removal deletes a key by pushing its node down to a leaf and disconnecting it from the tree.
• backtrackingBacktracking is a technique that reverses or revisits decisions along a path when processing cannot be completed from the current choice.
• bitmap imageAn RGB bitmap image is a raster image whose pixels represent color through red, green, and blue channels.
• pixelA pixel is the smallest addressable element of a raster image, carrying a color or intensity representation.
• derivativeA derivative measures the instantaneous rate at which a function changes with respect to its input.
• global optimumA minimum is a point or value at which a function is no greater than the function values in the relevant neighborhood or domain.
• Jordan curveA Jordan curve is a simple closed continuous curve in the plane that does not intersect itself.
• cProfilecProfile is Python's deterministic profiler for recording execution-time statistics for function and method calls.

These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.