CS221 Finals

A data type whose properties (domain and operations) are specified independently of any particular implementation. Examples: List, Stack, Queue, Tree, Graph, Set.

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.

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.

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.

Two vertices in a graph are said to be adjacent if there is an edge connecting the two.

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.

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).

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.

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.

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.

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.

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.

The number of items in a set.

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.

In hashing, when two keys hash to the same index in a hash table.

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.

In a set, the data type of the items composing the set.

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.

In an undirected graph, two vertices in which there exists, in the graph, a path between them.

Functions that create an abstract data type. Examples: int X or new node(). Also the "constructor" function(s) in a C++ class.

In a graph, a path greater than one that begins and ends on the same vertex. See Simple Cycle.

The separation of a data type's logical properties from its' implementation. Another term for Data Encapsulation.

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.

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.

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.

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.

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.

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.

The connections between vertices in a graph.

A set with no members.

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.

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.

A complete binary tree with values stored so that no child has a key value greater than its parent.

Code the algorithm in C.

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.

(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.

Testing of how functions work together. Done after Unit Testing.

A node in a binary tree that is neither the root nor a leaf.

A binary set operation that returns a set made up of only those items which are in both of the input sets.

A node in a binary tree that has no children.

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.

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.

A theoretical hash function that maps keys uniformly and randomly into a hash table without any collisions.

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.

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.

Variables and functions in a structure or class which can only be accessed from within the object. Default state for member variables of classes.

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.

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.

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.

Testing done after bugs have been fixed to insure the bug fixes have now introduced other problems.

The normal sequence of command execution. Programming commands are executed one after the other. See Flow Control and Transfer of Control.

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.

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.

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.

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.

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.

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.

A set X is a subset of Y if each item in X is also in Y.

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.

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.

A binary set operation that returns a set made up of all items that are in either of the input sets.

Testing of individual functions.

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.

The nodes in a graph.

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.

All subtrees are kept in perfect balance. Each node may contain one or two keys and have two or three subtrees.

*Best-fit memory allocation

*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.

Nodes attached to the left and right of a parent node.

*Cluster

*Destructor function

*Double hash function

*First-fit memory allocation

*Fragmentation, when referring to the heap

*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.

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.

When collisions occur a linked list of all records is hashing to the same index are created from the first record in that index.

*Heap, when referring to memory

*Linear Probing

A tree whose total edge weights is the minimum of all the possible spanning trees for the graph.

*Object oriented programming (OOP)

*Open addressing

A node that has either one or two child nodes.

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.

The first node in a binary tree.

*Shortest path in a graph

*Sub-trees or branches

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.

*Templates (Function and Class)

This is a special type of tree structure. Quite simply this is a form of alphabetical organizing of node keys.