# CS221 Finals

 A data type whose properties (domain and operations) are specified independently of any particular implementation. Examples: List, Stack, Queue, Tree, Graph, Set. Abstract Data Type Tests done before a software system is delivered to the customer or placed on the market. Designed to determine if the software meets all the requirements. Acceptance Testing A way of implementing a graph in computer memory in which the nodes are stored as an array of structures, and the links are defined in a two-dimensional array. Each row of the 2-D array represents the links from one of the vertices and the columns represent the "links to" vertices. This implementation is used when the number of vertices that will be in the graph is not known prior to run time. Adjacency Matrix A way of implementing a graph in computer memory in which the nodes are stored as a linked list of structures, each of which contains a pointer to a linked list of "link" structures defining the edges from this node to others in the graph. This implementation is used when the number of vertices that will be in the graph is not known prior to run time. Adjacency Set Two vertices in a graph are said to be adjacent if there is an edge connecting the two. Adjacent Vertices An outline of the procedure for solving a problem. This includes (1) the actions which are to be taken, and (2) the order in which the actions are to be performed. Algorithm A measure of the amount of resources necessary to execute a section of code. The efficiency or running time of an algorithm stated as a function relating the input size/length to the number of steps (time complexity) or storage locations (space complexity). Analysis of Algorithms A binary tree is an AVL tree if it meets the following criteria: (1) For any node in the tree the height (longest distance from root to leaf) of its left sub-tree is the same as the height of its right sub-tree, or it differs at most by 1, (2) The height of an empty tree is defined as -1. Developed by two Russian mathematicians, Adelson-Velskii and Landis. AVL Tree A tree structure in which each node is an empty tree or a node that has left and/or right children which are binary trees. The key in the parent node is greater than the key in the left child and less than the key in the right child. Binary Tree The process of program design in which the problem is defined in terms of low level simple objects that interact in some way. Design progresses from the simple objects and how they interact upward to more complex interactions. Also called object oriented programming. Focus is on the data objects in the software system. See Top Down Program Design. Bottom Up Program Design A function calling method in which the address or reference to the actual arguments are passed to a function. In C Call By Reference can be achieved by passing the addresses of variables or the values stored in pointers. In C++ functions can be defined that are Call By Reference functions. See the page on pointers for details on how to define a Call By Reference function. See also Call By Value. Call By Reference A function calling method in which only copies of the values stored in arguments to the function are passed into the function. All functions in C are Call By Value functions. See Call By Reference. Call By Value The number of items in a set. Cardinallity A structured type in a programming language containing variables and the functions which operate on those variables. Used to represent an abstract data type. See Object Oriented Programming. Class In hashing, when two keys hash to the same index in a hash table. Collision Trees with all their leaves on one level, or two adjacent levels with the bottom most leaves as far left as possible. A full binary tree is a complete binary tree. Complete Binary Tree In a set, the data type of the items composing the set. Component (base) type In an undirected graph, a set of vertices (which may not necessarily be all the vertices in the graph) in which for any vertex there is a path to every other vertex in the set. Connected Component In an undirected graph, two vertices in which there exists, in the graph, a path between them. Connected Vertices Functions that create an abstract data type. Examples: int X or new node(). Also the "constructor" function(s) in a C++ class. Constructor function In a graph, a path greater than one that begins and ends on the same vertex. See Simple Cycle. Cycle The separation of a data type's logical properties from its' implementation. Another term for Data Encapsulation. Data Abstraction The separation of the representation of data from the applications that use the data at a logical level. A programming language feature that enhances information hiding. Another term for Data Abstraction. See Information Hiding. Data Encapsulation In a graph, the number of edges for which a given vertex is one of the end points of the edge, i.e. how many other vertices a given vertex is connected to. See also In Degree, Out Degree, Predecessors of a Vertex and Successors of a Vertex. Degree of a Vertex A binary set operation that returns a set made up of all items that are in the first set but not in the second set. Difference A graph in which the paths (edges) between vertices go in only one direction. This is indicated in diagrams by making the lines connecting vertices into arrows indicating the direction of movement. Directed Graph A special function written to use as a testing function. It passes known inputs to selected functions and reports the returned values. Drivers are used to test lower level functions. See Stub. Driver Allocating memory for a variable, structure, or class instance after a program has started running using either Malloc() (Standard C) or new (C++). See Static Memory Allocation. Dynamic Memory Allocation The connections between vertices in a graph. Edges A set with no members. Empty Set The ability to have two or more functions in a class with the same name but different number and/or types of arguments. The OS determines from the arguments in a call to one of the functions which one to execute. Function Overloading A large array of data structures in which data is stored by using a hash function to calculate in index into the array based on a data key. Hash Table A complete binary tree with values stored so that no child has a key value greater than its parent. Heap, when referring to trees Code the algorithm in C. Implementation The practice of hiding the details of a function, class, or data structure with the goal of controlling access to the details of the implementation of a class or structure. See Data Encapsulation. Information Hiding (noun) The object that is created during the process of Instantiation (v). An instance of a class. (verb) The process of dynamically allocating memory for an object. When a class object is dynamically allocated it has been instantiated. Instantiation Testing of how functions work together. Done after Unit Testing. Integration Testing A node in a binary tree that is neither the root nor a leaf. Internal Node A binary set operation that returns a set made up of only those items which are in both of the input sets. Intersection A node in a binary tree that has no children. Leaf In a hash table, the radio of the number of filled entries (N) to the number of entries in the table (M). a = N / M. Load Factor In a graph, a list of vertices indicating those that must be visited in order to get from one vertex to another. If the two vertices are adjacent then this list has only two vertices in it. Path A theoretical hash function that maps keys uniformly and randomly into a hash table without any collisions. Perfect hash function The ability of different sub-classes of a parent class to inherit functions from the parent class yet implement the functions in very different ways. Polymorphism In a directed graph, the set of vertices from which the given vertex has edges coming in to it. See also Degree of a Vertex, In Degree, Out Degree, and Successors of a Vertex. Predecessors of a Vertex Variables and functions in a structure or class which can only be accessed from within the object. Default state for member variables of classes. Private, when referring to variables and functions Program design focusing on which functions are part of a program and how the functions interact to accomplish the goals of the program. See Object Oriented Programming, Top Down Design, Bottom Up Design. Procedural Programming Variables and functions in a structure or class which may be accessed only from other functions within the class or from functions in objects that are sub-classes of the class. Protected, when referring to variables and functions Variables and functions in a structure or class which are global and may be accessed from anywhere if there is access to the object. Default state for member variables of structures. Public, when referring to variables and functions Testing done after bugs have been fixed to insure the bug fixes have now introduced other problems. Regression Testing The normal sequence of command execution. Programming commands are executed one after the other. See Flow Control and Transfer of Control. Sequential Execution In an undirected graph, a cycle that consists of three or more distinct vertices, e.g. A->B->C->A, and no vertex is visited more than once except for the starting/ending vertex which is the same. Simple Cycle The process of determining the degree to which a piece of software produces results that are accurate, i.e. does it do what it is supposed to do correctly. Software Validation The process of determining the degree to which a piece of software produces results that satisfy the original requirements, i.e. does it do what it is supposed to do. Software Verification Memory that is allocated at program start up or when a function is called. Variable declarations in a program result in static memory allocation. See Dynamic Memory Allocation. Static Memory Allocation The process in software design of starting off at a high level of abstraction and working down through an interative process to add more and more detail to the design. Step-wise Refinement A special function written to use as a testing function. A stub returns known outputs to a calling function to determine how the calling function handles the returned values. Used to test higher level functions. See Driver. Stub A set X is a subset of Y if each item in X is also in Y. Subset In a directed graph, the set of vertices to which the given vertex has edges going out from it. See also Degree of a Vertex, In Degree, Out Degree, and Predecessors of a Vertex. Successors of a Vertex An approach to structured programming which involves working from the larger problem down to the details (Top Down Design) by expanding the steps in an algorithm to add more detail at each step (Stepwise refinement). Also called functional decomposition and procedural programming. The focus is on the processes. See Bottom Up Design. Top Down Program Design, with Stepwise Refinement A binary set operation that returns a set made up of all items that are in either of the input sets. Union Testing of individual functions. Unit Testing The set containing all the values of the component type. For example, in the set of integers the Universal set consists of all whole numbers from negative infinity to positive infinity. Universal Set The nodes in a graph. Vertices A graph in which each edge has a value associated with it. For example: a graph of routes between cities on a map may have a mileage associated with the route (edge) connecting each city (node) in the graph. Weighted Graph All subtrees are kept in perfect balance. Each node may contain one or two keys and have two or three subtrees. 2-3 tree *Best-fit memory allocation Best-fit memory allocation *Binary Search Binary Search This is a special form of the 2-3 tree in which each node is allowed to have a large number of keys. B-Tree Nodes attached to the left and right of a parent node. Child Node *Cluster Cluster *Destructor function Destructor function *Double hash function Double hash function *First-fit memory allocation First-fit memory allocation *Fragmentation, when referring to the heap Fragmentation, when referring to the heap *Greedy Algorithm Greedy Algorithm The technique used to calculate a unique index into the hash table from a key. This may be a mathematical calculation based on some value of the key or it may be some data manipulation technique. Hash function The hash table is divided up into equal sized groups of locations (buckets) and hash indices are calculated for the number of buckets, thus each index in the hash table can hold several records. Hashing with buckets When collisions occur a linked list of all records is hashing to the same index are created from the first record in that index. Hashing with chaining *Heap, when referring to memory Heap, when referring to memory *Linear Probing Linear Probing A tree whose total edge weights is the minimum of all the possible spanning trees for the graph. Minimal Spanning Tree of a graph *Object oriented programming (OOP) Object oriented programming (OOP) *Open addressing Open addressing A node that has either one or two child nodes. Parent Node Is the ability of a function to be able to call itself. A technique of problem solving done by breaking a large problem down into successively smaller versions of itself. Recursion The first node in a binary tree. Root *Shortest path in a graph Shortest path in a graph *Sub-trees or branches Sub-trees or brances A binary set operation that returns a set made up of all the items that are in the first set or the second set but not in both sets. the inverse of the Intersection. Symmetrical Difference of two sets *Templates (Function and Class) Templates (Function and Class) This is a special type of tree structure. Quite simply this is a form of alphabetical organizing of node keys. Trie AuthorAnonymous ID82276 Card SetCS221 Finals DescriptionCS221 Study Terms for Finals (* are imcomplete) Updated2011-04-27T16:34:34Z Show Answers