.. Copyright (C) Dave Parillo, Brad Miller, David Ranum, Jeffrey Elkner, Peter Wentworth, Allen B. Downey, Chris Meyers, and Dario Mitchell. Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.3 or any later version published by the Free Software Foundation; with Invariant Sections being Forward, Prefaces, and Contributor List, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free Documentation License". .. Some content from the OpenDSA eTextbook project. See http://algoviz.org/OpenDSA for more details. Copyright (c) 2012-2013 by the OpenDSA Project Contributors, and distributed under an MIT open source license. .. _glossary: Glossary -------- .. glossary:: :sorted: abstraction A technique used to reduce the complexity of systems and data. An abstraction often involves a simplified model of the 'real world' for the purposes of achieving goals within a specific problem domain. Data abstraction enforces a clear separation between the abstract properties of a :term:`data type` and the concrete details of its implementation. abstract base class A class in which some functions are not implemented. Abstract bases classes cannot be instantiated --- a derived class must override the abstract virtual function with an implementation. abstract data type Abbreviated :term:`ADT`. The realization of a :term:`data type` as a software component. activation record The entity that is stored on the :term:`runtime stack` during program execution. It stores any active :term:`local variable` and the return address from which a new subroutine is being called, so that this information can be recovered when the subroutine terminates. activecode A unique interpreter environment that allows code to be executed within a web browser. adjacent Two :term:`nodes ` of a :term:`tree` or two :term:`vertices ` of a :term:`graph` are said to be adjacent if they have an :term:`edge` connecting them. If the edge is directed from :math:`a` to :math:`b`, then we say that :math:`a` is adjacent to :math:`b`, and :math:`b` is adjacent from :math:`a`. adjacency list An implementation for a :term:`graph` that uses an (array-based) :term:`list` to represent the :term:`vertices ` of the graph, and each vertex is in turn represented by a (linked) list of the vertices that are :term:`neighbors `. adjacency matrix An implementation for a :term:`graph` that uses a 2-dimensional array where each row and each column corresponds to a :term:`vertex` in the :term:`graph`. A given row and column in the matrix corresponds to an edge from the :term:`vertex` corresponding to the row to the vertex corresponding to the column. ADT Abbreviation for :term:`abstract data type`. adversary argument A type of :term:`lower bounds proof` for a problem where a (fictional) "adversary" is assumed to control access to an algorithm's input, and which yields information about that input in such a way that will drive the cost for any proposed algorithm to solve the problem as high as possible. So long as the adversary never gives an answer that conflicts with any previous answer, it is permitted to do whatever necessary to make the algorithm require as much cost as possible. address A location in memory. aggregate type A :term:`data type` whose :term:`members ` have subparts. For example, a typical database record. Another term for this is :term:`composite type`. algorithm A general step by step process for solving a :term:`problem`. algorithm analysis :to-term: growth rate :label: key concept :to-term: upper bound :label: key concept :to-term: lower bound :label: key concept :to-term: asymptotic analysis :label: synonym :to-term: asymptotic algorithm analysis :label: formal synonym A less formal version of the term :term:`asymptotic algorithm analysis`, generally used as a synonym for :term:`asymptotic analysis`. alphabet trie A :term:`trie` data structure for storing variable-length strings. Level :math:`i` of the tree corresponds to the letter in position :math:`i` of the string. The root will have potential branches on each intial letter of string. Thus, all strings starting with "a" will be stored in the "a" branch of the tree. At the second level, such strings will be separated by branching on the second letter. ancestor In a tree, for a given node :math:`A`, any node on a path from :math:`A` up to the root is an ancestor of :math:`A`. antisymmetric In set notation, relation :math:`R` is antisymmetric if whenever :math:`aRb` and :math:`bRa`, then :math:`a = b`, for all :math:`a, b \in \mathbf{S}`. anti-pattern A common response to a recurring problem that is generally ineffective. Anti-patterns represent examples that you **should not** emulate! As bad as they are, they can still be instructive. Compare to :term:`design pattern`. api API An Application Programming Interface (API) is a set of functions, or classes used by a program. Often an API provides a family of functions or classes that work together to provide a complete set of capabilities. approximation algorithm An algorthm for an :term:`optimization problem` that finds a good, but not necessarily cheapest, solution. array-based list An implementation for the :term:`list` ADT that uses an array to store the list elements. array-based stack Analogous to an :term:`array-based list`, this uses an array to store the elements when implementing the :term:`stack` ADT. array-based queue Analogous to an :term:`array-based list`, this uses an array to store the elements when implementing the :term:`queue` ADT. ASCII character coding American Standard Code for Information Interchange. A commonly used method for encoding characters using a binary code. Standard ASCII uses an 8-bit code to represent upper and lower case letters, digits, some punctuation, and some number of non-printing characters (such as carrage return). Now largely replaced by UTF-8 encoding. assembly code :to-term: intermediate code :label: form of A form of :term:`intermediate code` created by a :term:`compiler` that is easy to convert into the final form that the computer can execute. An assembly language is typically a direct mapping of one or a few instructions that the CPU can execute into a mnemonic form that is relatively easy for a human to read. assignable A :term:`type` is *assignable* if the type can be copy-assigned a new value as the left-hand side of the operation. References are not assignable because once initialized, they cannot be assigned a new value. associative container A set of sorted data structures that can be quickly searched. ``map`` and ``set`` are examples. asymptotic algorithm analysis A more formal term for :term:`asymptotic analysis`. asymptotic analysis :to-term: algorithm analysis :label: synonym :to-term: asymptotic algorithm analysis :label: formal synonym A method for estimating the efficiency of an algorithm or computer program by identifying its :term:`growth rate`. Asymptotic analysis also gives a way to define the inherent difficulty of a :term:`problem`. We frequently use the term :term:`algorithm analysis` to mean the same thing. attribute In :term:`object-oriented programming `, a synonym for :term:`data member`. average case In :term:`algorithm analysis`, the average of the costs for all :term:`problem instances ` of a given input size :math:`n`. If not all problem instances have equal probability of occurring, then average case must be calculated using a weighted average. backing storage backing store The underlying storage for an :term:`ADT`. bag In set notation, a bag is a collection of elements with no order (like a set), but which allows for duplicate-valued elements (unlike a set). A synonym for :term:`multilist`. balanced tree A :term:`tree` where the :term:`subtrees ` meet some criteria for being balanced. Two possibilities are that the tree is :term:`height balanced`, or that the tree has a roughly equal number of :term:`nodes ` in each subtree. base Synonym for :term:`radix`. base case In :term:`recursion`, the base case is the termination condition. This is a simple input or value that can be solved without resorting to a recursive call. base class In :term:`object-oriented programming `, a class from which another class :term:`inherits `. The class that inherits is called a :term:`subclass` or :term:`derived class`. base type The :term:`data type` for the elements in a set. For example, the set might consist of the integer values 3, 5, and 7. In this example, the base type is integers. best case In algorithm analysis, the :term:`problem instance` from among all problem instances for a given input size :math:`n` that has least cost. Note that the best case is **not** when :math:`n` is small, since we are referring to the best from a class of inputs (i.e, we want the best of those inputs of size :math:`n`). big-O notation big-Oh notation In algorithm analysis, a shorthand notation for describing the upper bound for an algorithm or problem. binary search A standard :term:`recursive ` algorithm for finding the :term:`record` with a given :term:`key` within a sorted list. It runs in :math:`O(\log n)` time. At each step, look at the middle of the current sublist, and throw away the half of the records whose keys are either too small or too large. binary tree A non-linear data structure with a set of nodes which is either empty, or else has a root node together two binary trees, called the left and right :term:`subtrees `, which are disjoint from each other and from the :term:`root`. binary trie A :term:`binary tree` whose structure is that of a :term:`trie`. Generally this is an implementation for a :term:`search tree`. This means that the :term:`search key` values are thought of a binary digits, with the digit in the position corresponding to this a node's :term:`level` in the tree indicating a left branch if it is "0", or a right branch if it is "1". Examples include the :term:`Huffman coding tree` and the :term:`bintree`. binning In :term:`hashing`, binning is a type of :term:`hash function`. Say we are given keys in the range 0 to 999, and have a hash table of size 10. In this case, a possible hash function might simply divide the key value by 100. Thus, all keys in the range 0 to 99 would hash to slot 0, keys 100 to 199 would hash to slot 1, and so on. In other words, this hash function "bins" the first 100 keys to the first slot, the next 100 keys to the second slot, and so on. This approach tends to make the hash function dependent on the distribution of the high-order bits of the keys. bintree :to-term: flyweight :label: uses A :term:`spatial data structure` in the form of binary :term:`trie`, typically used to store point data in two or more dimensions. Similar to a :term:`PR quadtree` except that at each level, it splits one dimension in half. Since many leaf nodes of the PR quadtree will contain no data points, implementation often makes use of the :term:`flyweight` :term:`design pattern`. block Defines a :term:`scope` within a program. A synonym for :term:`code block`. boolean variable A variable that takes on one of the two values ``true`` and ``false``. bucket In :term:`bucket hashing`, a bucket is a sequence of :term:`slots ` in the :term:`hash table` that are grouped together. bucket hashing A method of :term:`hashing` where multiple :term:`slots ` of the :term:`hash table` are grouped together to form a :term:`bucket`. The :term:`hash function` then either hashes to some bucket, or else it hashes to a :term:`home slot` in the normal way, but this home slot is part of some bucket. :term:`Collision resolution ` is handled first by attempting to find a free position within the same bucket as the home slot. If the bucket if full, then the record is placed in an :term:`overflow bucket`. bug An error in a program. call stack Known also as execution stack. A stack that stores the function call sequence and the return address for each function. cartesian product For sets, this is another name for the :term:`set product`. ceiling Written :math:`\lceil x \rceil`, for real value :math:`x` the ceiling is the least integer :math:`\geq x`. child In a tree, the set of :term:`nodes ` directly pointed to by a node :math:`R` are the :term:`children ` of :math:`R`. class In the :term:`object-oriented programming paradigm` an ADT and its implementation together make up a class. An instantiation of a class within a program is termed an :term:`object`. class hierarchy In :term:`object-oriented programming `, a set of classes and their interrelationships. One of the classes is the :term:`base class`, and the others are :term:`derived classes ` that :term:`inherit` either directly or indirectly from the base class. class invariant type invariant invariants A class invariant is an assertion about conditions which must be true in order for a class to remain valid. client The user of a service. closed A set is closed over a (binary) operation if, whenever the operation is applied to two members of the set, the result is a member of the set. closed-form solution An algebraic equation with the same value as a :term:`summation` or :term:`recurrence relation`. The process of replacing the summation or recurrence with its closed-form solution is known as solving the summation or recurrence. closed hashing closed hash system A :term:`hash system` where all records are stored in slots of the :term:`hash table`. This is in contrast to an :term:`open hash system`. code block Defines a :term:`scope` within a program. A synonym for :term:`block`. code generation A phase in a :term:`compiler` that transforms :term:`intermediate code` into the final executable form of the code. More generally, this can refer to the process of turning a parse tree (that determines the correctness of the structure of the program) into actual instructions that the computer can execute. codelens An interactive environment that allows the user to control the step by step execution of a program code optimization :to-term: assembly code :label: changes A phase in a :term:`compiler` that makes changes in the code (typically :term:`assembly code`) with the goal of replacing it with a version of the code that will run faster while performing the same computation. cohesion In :term:`object-oriented programming `, a term that refers to the degree to which a class has a single well-defined role or responsibility. collision In a :term:`hash system`, this refers to the case where two search :term:`keys ` are mapped by the :term:`hash function` to the same slot in the :term:`hash table`. This can happen on insertion or search when another record has already been hashed to that slot. In this case, a :term:`closed hash system` will require a process known as :term:`collision resolution` to find the location of the desired record. collision resolution The outcome of a :term:`collision resolution policy`. collision resolution policy In :term:`hashing`, the process of resolving a :term:`collision`. Specifically in a :term:`closed hash system`, this is the process of finding the proper position in a :term:`hash table` that contains the desired record if the :term:`hash function` did not return the correct position for that record due to a :term:`collision` with another record. comment Information in a program that is meant for other programmers (or anyone reading the source code) and has no effect on the execution of the program. comparable The concept that two objects can be compared to determine if they are equal or not, or to determine which one is greater than the other. In set notation, elements :math:`x` and :math:`y` of a set are comparable under a given relation :math:`R` if either :math:`xRy` or :math:`yRx`. To be reliably compared for a greater/lesser relationship, the values being compared must belong to a :term:`total order`. In programming, the property of a data type such that two elements of the type can be compared to determine if they the same (a weaker version), or which of the two is larger (a stronger version). comparator A function given as a parameter to a method of a library (or alternatively, a parameter for a C++ template or a Java generic). The comparator function concept provides a generic way encapulates the process of performing a comparison between two objects of a specific type. For example, if we want to write a generic sorting routine, that can handle any record type, we can require that the user of the sorting routine pass in a comparator function to define how records in the collection are to be compared. comparison The act of comparing two :term:`keys ` or :term:`records `. For many :term:`data types `, a comparison has constant time cost. For others, such as :term:`linked list` the cost often increases as the number of elements increases. comparison sort A class of algorithms that sort data by comparing pairs of elements to determine their relative order, using operations like "less than" or "greater than" to decide which element comes first, with examples including :ref:`sort_merge`, :ref:`sort_quick`, and :ref:`sort_insertion`, all fundamentally limited to :math:`\Omega(n \log n)` time complexity in the worst case because they rely on these pairwise comparisons. The act of comparing two :term:`keys ` or :term:`records `. For many :term:`data types `, a comparison has constant time cost. For others, such as :term:`linked list` the cost often increases as the number of elements increases. compile To translate a program written in a high-level language into a low-level language all at once, in preparation for later execution. compiler A computer program that reads computer programs and converts them into a form that can be directly excecuted by some form of computer. The major phases in a compiler include :term:`lexical analysis`, :term:`syntax analysis`, :term:`intermediate code generation`, :term:`code optimization`, and :term:`code generation`. More broadly, a compiler can be viewed as :term:`parsing ` the program to verify that it is syntactically correct, and then doing :term:`code generation` to convert the hig-level program into something that the computer can execute. compile-time error Errors detected by the compiler. Compare to :term:`runtime error`, :term:`link error`, and :term:`semantic error`. compile-time polymorphism Compile-time polymorphism A form of :term:`polymorphism` known as Overloading. Overloaded methods have the same names, but different signatures as a method available elsewhere in the class. Compare to :term:`runtime polymorphism`. complete binary tree A binary tree where the nodes are filled in row by row, with the bottom row filled in left to right. Due to this requirement, there is only one tree of :math:`n` nodes for any value of :math:`n`. Since storing the records in an array in row order leads to a simple mapping from a node's position in the array to its :term:`parent`, :term:`siblings `, and :term:`children `, the array representation is most commonly used to implement the complete binary tree. The :term:`heap` data structure is a complete binary tree with partial ordering constraints on the node values. Composite design pattern Given a class hierarchy representing a set of objects, and a container for a collection of objects, the composite :term:`design pattern` addresses the relationship between the object hierarchy and a bunch of behaviors on the objects. In the composite design, each object is required to implement the collection of behaviors. This is in contrast to the procedural approach where a behavior (such as a tree :term:`traversal`) is implemented as a method on the object collection (such as a :term:`tree`). Procedural tree traversal requires that the tree have a method that understands what to do when it encounters any of the object types (:term:`internal ` or :term:`leaf nodes `) that the tree might contain. The composite approach would have the tree call the "traversal" method on its root node, which then knows how to perform the "traversal" behavior. This might in turn require invoking the traversal method of other objects (in this case, the children of the root). composite type A type whose :term:`members ` have subparts. For example, a typical database record. Another term for this is :term:`aggregate type`. composition Relationships between classes based on usage rather than :term:`inheritance `, i.e. a **HAS-A** relationship. For example, some code in class 'A' has a reference to some other class 'B'. compound type A :term:`data type` built up from simpler parts. Compare to :term:`simple type` and :term:`composite type`. constant running time constant time The cost of a function whose running time is not related to its input size. In Theta notation, this is traditionally written as :math:`\Theta(1)`. container container class A :term:`data structure` that stores a collection of :term:`records `. Typical examples are arrays and :term:`hash tables `. cost The amount of resources that the solution consumes. cost model In :term:`algorithm analysis`, a definition for the cost of each basic operation performed by the algorithm, along with a definition for the size of the input. Having these definitions allows us to calculate the :term:`cost` to run the algorithm on a given input, and from there determine the :term:`growth rate` of the algorithm. A cost model would be considered "good" if it yields predictions that conform to our understanding of reality. CPU Acronym for Central Processing Unit, the primary processing device for a computer. current position A property of some list ADTs, where there is maintained a "current position" state that can be referred to later. data field In :term:`object-oriented programming `, a synonym for :term:`data member`. data item A piece of information or a record whose value is drawn from a type. data member The variables that together define the space required by a data item are referred to as data members. Some of the commonly used synonyms include :term:`data field`, :term:`attribute`, and :term:`instance variable`. data structure The implementation for an :term:`ADT`. data type A type together with a collection of operations to manipulate the type. debugging The process of finding and removing any of the three kinds of programming errors. decision tree A theoretical construct for modeling the behavior of algorithms. Each point at which the algorithm makes a decision (such as an if statement) is modeled by a branch in the tree that represents the algorithms behavior. Decision trees can be used in :term:`lower bounds proofs `, such as the proof that sorting requires :math:`\Omega(n \log n)` comparisons in the :term:`worst case`. declaration A declaration introduces a new :term:`name` and :term:`type` into a :term:`scope`. depth The depth of a node :math:`M` in a tree is the length of the path from the root of the tree to :math:`M`. depth-first search :to-term: DFS :label: abbreviation :to-term: depth-first search tree :label: generates A :term:`graph` :term:`traversal` algorithm. Whenever a :math:`v` is :term:`visited ` during the traversal, DFS will :term:`recursively ` visit all of :math:`v` 's :term:`unvisited` :term:`neighbors `. depth-first search tree A :term:`tree` that can be defined by the operation of a :term:`depth-first search` (DFS) on a :term:`graph`. This tree would consist of the :term:`nodes ` of the graph and a subset of the :term:`edges ` of the graph that was followed during the DFS. dequeue A specialized term used to indicate removing an element from a queue. derived class In :term:`object-oriented programming `, any class within a :term:`class hierarchy` that :term:`inherits ` from some other class. A synonym for :term:`derived class`. descendant In a tree, the set of all nodes that have a node :math:`A` as an :term:`ancestor` are the descendants of :math:`A`. In other words, all of the nodes that can be reached from :math:`A` by progressing downwards in tree. Another way to say it is: The :term:`children ` of :math:`A`, their children, and so on. derivation In formal languages, the process of executing a series of :term:`production rules ` from a :term:`grammar`. A typical example of a derivation would be the series of productions executed to go from the :term:`start symbol` to a given string. deserialization The process of returning a :term:`serialized ` representation for a data structure back to its original in-memory form. design pattern An abstraction for describing the design of programs, that is, the interactions of objects and classes. Experienced software designers learn and reuse patterns for combining software components, and design patterns allow this design knowledge to be passed on to new programmers more quickly. Examples are :term:`Composite design pattern`, :term:`flyweight`, :term:`iterator`, :term:`strategy`, and :term:`visitor`. dictionary An abstract data type or interface for a data structure or software subsystem that supports insertion, search, and deletion of records. discriminator A part of a :term:`multi-dimensional search key`. Certain tree data structures such as the :term:`bintree` and the :term:`kd tree` operate by making branching decisions at nodes of the tree based on a single attribute of the multi-dimensional key, with the attribute determined by the level of the node in the tree. For example, in 2 dimensions, nodes at the odd levels in the tree might branch based on the :math:`x` value of a coordinate, while at the even levels the tree would branch based on the :math:`y` value of the coordinate. Thus, the :math:`x` coordinate is the discriminator for the odd levels, while the :math:`y` coordinate is the discriminator for the even levels. disjoint Two parts of a :term:`data structure` or two collections with no objects in common are disjoint. This term is often used in conjunction with a data structure that has :term:`nodes ` (such as a :term:`tree`). Also used in the context of :term:`sets `, where two :term:`subsets ` are disjoint if they share no elements. disjoint sets A collection of :term:`sets `, any pair of which share no elements in common. A collection of disjoint sets partitions some objects such that every object is in exactly one of the disjoint sets. divide and conquer A technique for designing algorithms where a solution is found by breaking the problem into smaller (similar) subproblems, solving the subproblems, then combining the subproblem solutions to form the solution to the original problem. This process is often implemented using :term:`recursion`. divide-and-conquer recurrences A common form of :term:`recurrence relation` that have the form .. math:: {\bf T}(n) = a{\bf T}(n/b) + cn^k; \quad {\bf T}(1) = c where :math:`a`, :math:`b`, :math:`c`, and :math:`k` are constants. In general, this recurrence describes a problem of size :math:`n` divided into :math:`a` subproblems of size :math:`n/b`, while :math:`cn^k` is the amount of work necessary to combine the partial solutions. domain The set of possible inputs to a function. double hashing A :term:`collision resolution` method. A second hash function is used to generate a value :math:`c` on the key. That value is then used by this key as the step size in :term:`linear probing by steps`. Since different keys use different step sizes (as generated by the second hash function), this process avoids the clustering caused by standard linear probing by steps. doubly linked list A :term:`linked list` implementation variant where each list node contains access pointers to both the previous element and the next element on the list. dynamic array Arrays, once allocated, are of fixed size. A dynamic array puts an interface around the array so as to appear to allow the array to grow and shrink in size as necessary. Typically this is done by allocating a new copy, copying the contents of the old array, and then returning the old array to :term:`free store`. In some programming languages, the term :term:`vector` is used as a synonym for dynamic array. dynamic memory allocation A programming technique where linked objects in a data structure are created from :term:`free store` as needed. When no longer needed, the object is either returned to :term:`free store` or left as :term:`garbage`, depending on the programming language. edge The connection that links two :term:`nodes ` in a :term:`tree`, :term:`linked list`, or :term:`graph`. element One value or member in a set. empty For a :term:`container` class, the state of containing no :term:`elements `. encapsulation In programming, the concept of hiding implementation details from the user of an ADT, and protecting :term:`data members ` of an object from outside access. enqueue A specialized term used to indicate inserting an element onto a queue. enumeration The process by which a :term:`traversal` lists every object in the :term:`container` exactly once. Thus, a traversal that prints the :term:`nodes ` is said to enumerate the nodes. An enumeration can also refer to the actual listing that is produced by the traversal (as well as the process that created that listing). equivalence class An :term:`equivalence relation` can be used to partition a set into equivalence classes. equivalence relation Relation :math:`R` is an equivalence relation on set :math:`\mathbf{S}` if it is :term:`reflexive`, :term:`symmetric`, and :term:`transitive`. exception Another name for a runtime error. exchange A swap of adjacent records in an array. executable Another name for object code that is ready to be executed. exponential growth rate A :term:`growth rate` function where :math:`n` (the input size) appears in the exponent. For example, :math:`2^n`. external fragmentation A condition that arises when a series of memory requests result in lots of small :term:`free blocks `, no one of which is useful for servicing typical requests. external sort A sorting algorithm that is applied to data stored outside the program, such as a disk file. This is in contrast to an :term:`internal sort` that is meant to work on data stored in memory. FIFO Abbreviation for "first-in, first-out". This is the access paradigm for a :term:`queue`, and an old terminolgy for the queue is "FIFO list". fixed-length coding Given a collection of objects, a fixed-length coding scheme assigns a code to each object in the collection using codes that are all of the same length. Standard ASCII and Unicode representations for characters are both examples of fixed-length coding schemes. This is in contrast to :term:`variable-length coding`. floor Written :math:`\lfloor x \rfloor`, for real value :math:`x` the floor is the greatest integer :math:`\leq x`. flyweight A :term:`design pattern` that is meant to solve the following problem: You have an application with many objects. Some of these objects are identical in the information that they contain, and the role that they play. But they must be reached from various places, and conceptually they really are distinct objects. Because there is so much duplication of the same information, we want to reduce memory cost by sharing that space. For example, in document layout, the letter "C" might be represented by an object that describes that character's strokes and bounding box. However, we do not want to create a separate "C" object everywhere in the document that a "C" appears. The solution is to allocate a single copy of the shared representation for "C" objects. Then, every place in the document that needs a "C" in a given font, size, and typeface will reference this single copy. The various instances of references to a specific form of "C" are called flyweights. folding method In :term:`hashing`, an approach to implementing a :term:`hash function`. Most typically used when the key is a string, the folding method breaks the string into pieces (perhaps each letter is a piece, or a small series of letters is a piece), converts the letter(s) to an integer value (typically by using its underlying encoding value), and summing up the pieces. free block A block of unused space in a memory pool. free block list In a memory manager, the list that stores the necessary information about the current :term:`free blocks `. Generally, this is done with some sort of :term:`linked list`, where each node of the linked list indicates the start position and length of the free block in the memory pool. free store Space available to a program during runtime to be used for :term:`dynamic memory allocation` of objects. The free store is distinct from the :term:`runtime stack`. The free store is sometimes referred to as the :term:`heap`, which can be confusing because :term:`heap` more often refers to a specific data structure. Most programming languages provide functions to allocate (and maybe to deallocate) objects from the free store, such as ``new`` in C++ and Java. full tree A :term:`binary tree` is full if every :term:`node` is either a :term:`leaf node` or else it is an :term:`internal node` with two non-empty :term:`children `. function In programming, a subroutine that takes input parameters and uses them to compute and return a value. In this case, it is usually considered bad practice for a function to change any global variables (doing so is called a side effect). fundamental type One of the :term:`simple types ` provided by the language. Examples are ``bool``, ``char``, ``int``, and ``double``. Types provided by the STL, such as ``std::string`` and ``std::vector`` are not considered 'fundamental' types. garbage In memory management, any memory that was previously (dynamically) allocated by the program during runtime, but which is no longer accessible since all pointers to the memory have been deleted or overwritten. In some languages, garbage can be recovered by :term:`garbage collection`. In languages such as C and C++ that do not provide built-in garbage collection, so creating garbage is considered a :term:`memory leak`. garbage collection Languages with garbage collection such Java, JavaScript, Lisp, and Scheme will periodically reclaim :term:`garbage` and return it to :term:`free store`. general tree A tree in which any given node can have any number of :term:`children `. This is in contrast to, for example, a :term:`binary tree` where each node has a fixed number of children (some of which might be ``null``). General tree nodes tend to be harder to implement for this reason. generic programming A computer programming style in which functions are written using *placeholders for* types. In C++ this is accomplished using :term:templates