The flashcards below were created by user
Anonymous
on FreezingBlue Flashcards.

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 twodimensional array. Each row of the 2D 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 subtree is the same as the height of its right subtree, or it differs at most by 1, (2) The height of an empty tree is defined as 1. Developed by two Russian mathematicians, AdelsonVelskii 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 subclasses 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 subclasses 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.
Stepwise 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.
23 tree

*Bestfit memory allocation
Bestfit memory allocation

*Binary Search
Binary Search

This is a special form of the 23 tree in which each node is allowed to have a large number of keys.
BTree

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


*Destructor function
Destructor function

*Double hash function
Double hash function

*Firstfit memory allocation
Firstfit 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

*Subtrees or branches
Subtrees 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

