liveBookmanning.com

What you will learn in Fabulous Adventures in Data Structures and Algorithms

by Eric Lippert
Foreword by Jon Skeet

Read it on liveBook Get the book at manning.com

Chapter by chapter

Concepts explained in this book

• performancePerformance is the measured resource efficiency or execution speed of a computational system or algorithm.
• recursionA recursive algorithm solves a problem by invoking itself on smaller or simpler instances together with terminating cases.
• amortized analysisAmortized cost is the average resource cost per operation over a sequence of operations, including occasional expensive operations.
• posterior probabilityA posterior distribution is a probability distribution representing beliefs about an unknown quantity after incorporating observed evidence.
• memoizationA memoized function is a function wrapper that returns cached results for inputs previously evaluated by the original function.
• dequeA mutable double-ended queue is a double-ended queue whose contents can be changed by operations at either end.
• substitutionA substitution is an assignment of terms or values to variables or placeholders in a symbolic expression.
• worst-case performanceWorst-case performance is the resource usage or execution behavior of an algorithm or data structure on its least favorable inputs.
• lexicographic orderingLexicographic order is an ordering of sequences that compares elements from left to right according to the underlying element order.
• unificationUnification is the process of finding substitutions that make symbolic expressions or tree structures identical.
• immutable collectionAn immutable data structure is a data structure whose contents cannot be changed after it is created.
• concatenationConcatenation is the operation of joining sequences end to end into a single sequence.
• likelihoodA likelihood function expresses the plausibility of observed data as a function of a hypothesis or model parameter.
• invariantAn invariant is a property that remains true throughout the valid states or operations of a computation.
• joint probability distributionA joint probability distribution assigns probabilities to combinations of outcomes from multiple random variables.
• backtrackingA backtracking search algorithm incrementally explores candidate choices and reverses choices that cannot lead to a valid solution.
• prior probabilityA prior is a probability distribution representing beliefs about a hypothesis before incorporating new evidence.
• permutation numberA permutation number is an index identifying a particular permutation among an ordered collection of permutations.
• termA binary term is an immutable binary-tree representation whose nodes are holes, constants, or named symbols with two child terms.
• docA doc is the book's immutable pretty-printing document representation that encodes text, optional breaks, grouping, indentation, and concatenation.
• data structureA data structure is an organization of data that supports storing, accessing, and manipulating it.
• combinationA combination is a subsequence or subset selected from a sequence without changing the original element order.
• persistent data structurePersistence is a data-structure technique that preserves previous versions when updates create new versions.
• finger treeA finger tree is a functional sequence data structure that provides efficient access and updates near either end and can support monoidal aggregation.
• directed acyclic word graphA directed acyclic word graph is a directed acyclic graph representing a set of words with shared prefixes and suffixes.
• logic variableA free hole is a hole that is not a key in a substitution and has no assigned replacement term.
• Cartesian productA Cartesian product algorithm enumerates tuples by choosing one element from each of multiple input sequences.
• unnormalized distributionA non-normalized probability density function is a nonnegative function proportional to a continuous distribution's density but not necessarily integrating to one.
• graph coloringGraph coloring is the assignment of colors to graph elements subject to constraints such as adjacent vertices receiving different colors.
• bayesian statisticsBayesian inference updates probability distributions over hypotheses or parameters using observed evidence and Bayes' rule.
• Hughes listA Hughes list is a functional list representation implemented with a binary tree while exposing linked-list features.
• Markov chainA Markov process is a stochastic process in which the conditional distribution of the next state depends only on the current state.
• metropolis-hastings samplingThe Metropolis algorithm is a Markov chain Monte Carlo method that generates samples from a target distribution using proposed moves and acceptance probabilities based on relative weights.
• trieA trie, or prefix tree, is a tree-shaped data structure that stores strings by sharing nodes representing common prefixes.
• immutable queueAn immutable queue is a first-in, first-out data structure whose contents cannot be changed after creation.
• abstract data typeAn abstract data type is a specification of the values and operations of a data abstraction independent of its implementation.
• genericsA generic type is a parameterized type whose definition can operate over one or more type parameters.
• anti-unificationAnti-unification is the process of finding the most specific generalization shared by symbolic expressions or tree structures.
• categorical distributionA categorical distribution assigns probabilities to a finite set of mutually exclusive categories.
• probability densityA probability density function is a nonnegative function whose integral over a range determines the probability of a continuous random variable falling in that range.
• enumerationEnumeration is the process of traversing and producing the elements of a collection in sequence.
• transition probabilityA transition function specifies the probability rule or mechanism for producing a stochastic process's next state from its current state.
• Gosper’s HashLife algorithmHashLife is an algorithm that accelerates Conway's Game of Life by representing regions as quadtrees and reusing cached results for recurring configurations.
• algorithmAn algorithm is a finite, precise procedure for solving a problem or computing a result.
• category theoryCategory theory is a mathematical framework that studies objects and structure-preserving mappings between them.
• recursive definitionA recursive definition specifies a structure or value in terms of simpler instances of itself together with base cases.
• deque of minisA deque of minis is the recursive middle component of this deque representation whose elements are bounded mini-deques.
• combination numberA combination number is the zero-based lexicographic index assigned to a combination among combinations of fixed size.
• linked listA linked list is a sequence of nodes in which each node refers to the next node in the sequence.
• deduplicationDeduplication is the elimination of duplicate representations by sharing one representation for identical data.
• change ringing algorithmA change-ringing algorithm enumerates permutations so that each successive permutation differs by one swap of adjacent elements.
• reversingReverse is a method that constructs a new immutable linked list containing the input list's items in reverse order.
• weightAn integer weight is a whole-number quantity representing the relative contribution of an outcome to a weighted distribution.
• immutable stackAn immutable stack is a last-in, first-out data structure whose contents cannot be changed after creation.
• mini-dequeA mini-deque is a nonempty double-ended sequence structure restricted to one through four items and supporting insertion and removal at either end.
• bindBind is an operation that chains a context-producing function to a contextual value while flattening the resulting nested context.
• reference equalityReference equality determines whether two references identify the same object rather than whether their contained values are equal.
• stackA stack is a last-in, first-out data structure supporting insertion and removal at one end.
• visitor design patternThe visitor pattern separates operations on a structure from the classes representing that structure by dispatching operations through visitor objects.
• constant timeConstant-time complexity is computational complexity in which an operation takes a bounded amount of time independent of input size.
• next lexicographic permutation algorithmPandita's algorithm is an in-place algorithm that transforms a permutation into its next lexicographically ordered permutation when one exists.
• initial state distributionAn initial distribution is the probability distribution from which a stochastic sampling process draws its starting state.
• permutationA permutation is an ordering of all elements of a sequence or set.
• endofunctorAn endofunctor is a functor that maps a category to itself.
• queueA queue is a first-in, first-out data structure supporting insertion at one end and removal at the other.
• conditional probabilityConditional probability is the probability of an event given that another event or condition is known to hold.
• evidenceEvidence is an observed fact or data value that changes the probability assigned to a hypothesis or event.
• rejection samplingThe rejection algorithm samples candidate outcomes and discards candidates that fail a probabilistic acceptance test.
• covarianceCovariance is a type-system property that permits a generic type instantiated with a derived reference type to be treated as the same generic type instantiated with a base reference type.
• assignment compatibilityAssignment compatibility is the C# type-system rule determining whether an expression of one type may be assigned to a variable of another type.
• occurs checkAn occurs check is a unification test that rejects binding a hole or variable to a term in which it occurs, preventing cyclic substitutions.
• Bayes' theoremBayes' theorem is a probability rule that computes a conditional probability by combining prior probabilities with the likelihood of observed evidence.
• two-stack queueA two-stack queue is a queue implementation that stores newly added and removable items in separate stacks.
• covariant generic interfaceA covariant generic type is a generic type whose type-parameter relationship preserves the direction of assignment compatibility.
• IDiscreteDistribution<T>IDiscreteDistribution<T> is a generic interface for discrete probability distributions that exposes sampling, support enumeration, and element probabilities.
• interfaceAn interface is a C# contract that specifies members a type can implement.
• categoryA category is a mathematical structure consisting of objects and composable morphisms between them.
• morphismA morphism is a structure-preserving mapping from one object in a category to another.
• undo-redo logicUndo-redo logic is application behavior that records state changes so earlier states can be restored and subsequently reapplied.
• binary searchBinary search locates an ordered value by repeatedly comparing it with the middle element of a sorted collection and discarding half of the remaining search range.
• monadA monad is an abstraction that pairs a type with operations for lifting values and chaining context-aware computations while preserving the structure of composition.
• sequenceA sequence is an ordered abstraction representing elements that can be processed in a defined order.
• pushPush is a linked-list operation that adds a value to the front of a list and returns the resulting list.
• pretty printingPretty printing is the automated formatting of source code to produce a readable layout under spacing and indentation constraints.
• mathematical constantA constant is a fixed symbolic term that represents a particular value or atom and cannot be bound by substitution.
• discrete distributionA discrete probability distribution assigns probabilities to outcomes in a finite or countably infinite set.
• extensionAn extension method is a statically declared method that can be invoked with instance-method syntax on a type without modifying that type.
• first-order binary term unificationA first-order unification algorithm computes substitutions that make first-order terms identical when such substitutions exist.
• suffix deduplicationSuffix deduplication is the technique of representing identical word suffixes only once when storing a word collection.
• DAWG-building algorithmThe DAWG-building algorithm incrementally constructs a minimal directed acyclic word graph from words in sorted order by minimizing completed suffix paths.
• StringBuilderStringBuilder is a .NET mutable character sequence type designed for efficient repeated string construction and modification.
• covariant functorA covariant functor maps objects between categories and maps morphisms in the same direction while preserving their structure.
• medical testA medical test is a procedure that provides evidence about whether a health condition is present.
• query expressionA query expression is a declarative syntax for describing sequence or collection transformations that a compiler or runtime translates into executable operations.
• samplingSampling is the process of generating a random outcome according to a probability distribution.
• stack spaceStack space is memory consumed by activation records of active function calls during execution.
• quadratic time complexityQuadratic cost is a resource cost that grows proportionally to the square of an input's length.
• probability distributionA probability distribution specifies the probabilities assigned to the possible values of a random quantity.
• type-lifting functionUnit is the conventional monadic operation that wraps a value of type T into the corresponding monadic type M<T>.
• uniform distributionA continuous uniform distribution assigns constant density across a continuous interval and zero density outside it.
• binomial coefficientA binomial coefficient is the number of ways to choose a specified number of elements from a set of a given size.
• posetA posetal category is a category whose morphisms are determined by a partial-order relation on its objects.
• FitsFits is the book-specific method that determines whether a Doc can be rendered within a remaining line width without turning descendant optional breaks into line breaks.
• continuous distributionA continuous distribution assigns probabilities over values in a continuous range.
• quadtreeA quadtree is a hierarchical spatial data structure that recursively partitions a two-dimensional region into four subregions.
• memoryMemory is computer storage capacity available to hold program data during execution.
• additive monadAn additive monad is a monad equipped with an operation for combining computations or values according to an additive structure.
• hashsetHashSet<T> is a .NET collection type that stores unique values and supports hash-based membership and lookup operations.
• ConcatDocConcatDoc is the book's Doc variant that combines left and right child documents in output order.
• IndentDocIndentDoc is the book's Doc variant that associates an indentation amount with a child document's line breaks.
• TextDocTextDoc is the book's Doc variant that holds text with no line-break characters to append directly to formatted output.
• threeA Three is a mini-deque containing exactly three items.
• mutable-over-immutable wrapperA mutable wrapper is a mutable object that forwards operations to and replaces its reference to an underlying immutable data structure.
• base ratePrevalence is the proportion of a population that has a specified disease or condition at a given time.
• alias methodThe alias algorithm is a discrete weighted-sampling technique that preprocesses outcomes into uniform-indexed rows containing at most two possible values.
• flatmapFlatMap is an operation that maps each element to a sequence and concatenates the resulting sequences into one sequence.
• multiword stateA multiword state is a Markov-model state composed of two or more consecutive words to condition the next-word distribution on additional context.
• greedy pretty-printing algorithmA greedy pretty-printing algorithm formats structured source text by fitting as much content as possible onto the current line before continuing on later lines.
• supportThe support of a probability distribution is the set of values that can occur with positive probability.
• projectionA projection is a mapping or function that selects or derives specified components or values from a structured input.
• pure functionA pure function is a function whose result depends only on its input values and that has no observable interaction with global state.
• Bernoulli distributionA Bernoulli distribution is a probability distribution over two outcomes, conventionally represented by 0 and 1, with an arbitrary probability for one outcome.
• SubstituteSubstitute is the example term operation that recursively replaces bound holes with their corresponding substitution terms.
• out positionAn output position is a type-parameter occurrence where values of the parameterized type are produced or returned rather than consumed.
• immutable linked listAn immutable linked list is a linked-list data structure whose nodes and links cannot be modified after construction.
• sorted listA sorted word list is a word collection stored in lexicographic order for ordered searching and prefix matching.
• category of typesThe category of types is a category whose objects are types and whose morphisms express assignment compatibility.
• generic interfaceA generic interface is an interface parameterized by one or more type parameters.
• graphA graph is a data structure consisting of vertices connected by directed or undirected edges.
• indentationIndentation is horizontal whitespace used to indicate nesting or structural level in formatted source code.
• total weightTotal weight is the sum of the weights assigned to all outcomes in a weighted distribution.
• minimal directed acyclic word graphA minimal directed acyclic word graph is a DAWG with the fewest states possible for recognizing its represented word set.
• immutable graphAn immutable graph is a graph representation whose nodes and edges cannot be changed after creation.
• type inferenceType inference is the deduction of expression or variable types from program context and constraints without requiring every type to be written explicitly.
• sequence monadA sequence monad is the monadic structure whose context represents zero or more values in an ordered sequence.
• marginal tableA marginal table is a tabular summary whose row and column margins show aggregate totals for the variables being analyzed.
• Macaulay representationMacaulay representation is a unique decomposition of a nonnegative integer as a sum of binomial coefficients with increasing lower indices.
• probability distribution monadA probability distribution monad is a monadic structure whose context represents uncertainty over outcomes and whose chaining operation combines distributions according to conditional probabilities.
• joinJoin is a monadic operation that removes one level of nesting from a nested monad.
• reducerReducer is the book's one-member interface for transforming an attempt by eliminating possible values without guessing.
• recursive combination enumerationRecursive combination generation enumerates combinations by recursively separating those that exclude a final element from those that include it.
• IE<T>IE<T> is a simplified generic interface whose type parameter T occurs only in output positions.
• hash valueA hash code is an integer value computed from data to support its placement and lookup in a hash-based data structure.
• base caseA base case is a terminating condition in a recursive procedure that can be solved without another recursive expansion.
• type safetyType safety is the property that a program's operations respect the constraints imposed by its types.
• constant factorA constant factor is a multiplicative coefficient in an algorithm's resource cost that does not vary with input size.
• optimizationAn optimization is a change to an implementation intended to reduce resource usage or improve performance while preserving its result.
• greedy algorithmA greedy algorithm constructs a solution by repeatedly choosing the locally best available option without generally reconsidering earlier choices.
• Even's change ringing algorithmEven's change-ringing algorithm enumerates permutations by repeatedly swapping the largest mobile element with its adjacent neighbor and reversing directions of larger elements.
• bound holeA bound hole is a hole that appears as a key in a substitution and therefore has an assigned replacement term.
• probability theoryProbability is the mathematical theory of quantifying uncertainty about possible outcomes.
• listA list is an ordered collection of elements that supports sequence-oriented operations.
• functorA functor is a mapping between categories that preserves their objects, morphisms, and composition.
• contravarianceContravariance is a type-system relationship in which a more-derived type parameter can substitute for a less-derived type parameter in input positions.
• finite-state machineA finite state automaton, or finite state machine, is a computational model with finitely many states and transitions governed by input-dependent rules.
• Lazy<T>Lazy<T> is a .NET generic type that defers computation of a value until the value is first requested and then caches it.
• factoryA factory is a construction pattern that centralizes creation of objects or data-structure instances.
• persistent mapImmutableDictionary is a .NET immutable key-value collection type that preserves prior versions when updated.
• embiggeningEmbiggening is the operation of embedding an n-quad in the center of an otherwise empty (n+1)-quad.
• false positiveA false positive is a positive test result produced when the tested condition is absent.
• partial applicationPartial application is the creation of a function by binding one or more arguments of another function to particular values.
• Game of LifeLife is Conway's Game of Life, a two-dimensional cellular automaton whose cell states evolve according to neighboring-cell rules.
• equalityTerm equality is structural equality in which constants have equal values, holes have equal names, and symbols have equal names and equal corresponding children.
• inverse cumulative distribution function methodThe inverse transform method generates samples by applying the inverse cumulative distribution function to a uniform random value.
• explicit stack techniqueAn explicit stack technique simulates recursive traversal by storing pending work items in a programmer-managed stack.
• proposal distributionA proposal distribution is a probability distribution that generates a candidate next state conditional on a Markov chain's current state.
• node equivalenceNode equivalence is equality of graph nodes determined by matching terminal status, outgoing-edge labels, and reference-identical successor nodes.
• filteringCategorical distribution filtering removes one or more outcomes from a categorical distribution and adjusts the remaining distribution accordingly.
• contravariant functorA contravariant functor is a mapping between categories that preserves the existence of morphisms while reversing their directions.
• DocumentA document is an intermediate data structure that represents source-code layout rules and program text for pretty printing.
• mapA monadic map operation applies a function to values inside a monadic computational context while preserving that context's structure.
• mzeroMZero is the identity value for the addition-like operation of an additive monad.
• n-quadAn n-quad is a square quadtree region whose side length is 2^n cells and which recursively represents four subregions at each higher level.
• lazy evaluationLaziness is an evaluation strategy that defers computation until its result is needed.
• delegateA delegate type is a C# type that represents a callable method signature and can hold a type-safe reference to a compatible method or function.
• recallTest sensitivity is the conditional probability that a medical test is positive when the tested condition is present.
• specificityTest specificity is the conditional probability that a medical test is negative when the tested condition is absent.
• null object patternThe null object pattern represents the absence of a value with a valid object that provides appropriate behavior instead of a null reference.
• combinatorial base representationA combinatorial base representation expresses an integer as a sum of binomial coefficients with constrained upper indices.
• yieldyield return is C# iterator-block syntax that produces sequence elements on demand during enumeration.
• mutable objectA mutable data structure is a data structure whose contents can be changed after it is created.
• edgeAn edge is a graph or tree connection from one node to another that may carry a label.
• nodeA node is an element in a graph or tree data structure that stores state and connects to related nodes through edges.
• immutable quadtreeAn immutable quadtree is a quadtree representing a square array of alive or dead cells whose structure cannot be changed after creation.
• identity functionAn identity function returns its argument unchanged.
• parse treeA parse tree is a tree that represents the syntactic structure derived by parsing a source-language expression or program.
• mobile numberA mobile number is an element of a directed permutation having a smaller adjacent element in its assigned direction.
• PrologProlog is a declarative logic programming language in which programs consist of facts and rules and execution answers queries through logical resolution.
• prefixA prefix is an initial substring of a word or string.
• binomial distributionA binomial distribution gives the probabilities of obtaining each possible number of successes in a fixed number of independent trials with the same success probability.
• gridA grid is a regular two-dimensional arrangement of positions or cells addressed by spatial coordinates.
• exponential spaceExponential complexity is asymptotic resource growth proportional to an exponential function of input size.
• target distributionA target distribution is the probability distribution that a sampling procedure is intended to reproduce.
• node degreeGraph degree is the number of edges incident to a given graph node.
• cliqueA clique is a group of graph nodes in which every node is adjacent to every other node.
• in positionAn input position is a type-parameter occurrence where values of the parameterized type are accepted or consumed rather than produced.
• random sequenceA random sequence is a sequence-valued random outcome whose elements are generated according to a probability model.
• exponential time complexityAn exponential-time algorithm has a running time that grows exponentially with input size.
• Robinson's algorithmRobinson's algorithm is a unification algorithm that solves equations between first-order terms by constructing substitutions or detecting failure.

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.