CS307 Glossary

  1. A concept, thought, or idea apart from any particular instances or material objects. In computer science an organization of data, a manipulation of data, an algorithm, etc. apart from any particular programming language implementation of that thing.
    Abstract
  2. A variable defined as static inside of a function (ex: static int x = 0;) maintains the same value it had the last time the function was called. In the example given the first time the function containing x is called the variable is created and initialized to the value of zero. If while the function is running x is incremented with x++; then the next time the function is called x will have the initial value of one.
    Static
  3. 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
  4. 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
  5. Jumping to a program statement that is not the next one in the sequence. Calling a function is an example of Transfer of Control. See Flow Control and Sequential Execution.
    Transfer of Control
  6. Functions that change the data in some way. Examples: X=3. The "equals" function set the value to store in the variable X. This may include setting values, inserting or deleting an item from an object, or combining two objects.
    Transformers
  7. A graph in which the paths (edges) between vertices go in both directions. See also Directed Graph.
    Undirected Graph
  8. A binary set operation that returns a set made up of all items that are in either of the input sets.
    Union
  9. Testing of individual functions.
    Unit Testing
  10. 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
  11. The process of determining the degree to which a piece of software produces results that satisfy the original requirements. Does it do what it is supposed to do, i.e. did you build the right software.
    Validation
  12. The process of determining the degree to which a piece of software produces results that are accurate. Does it do what it is supposed to do correctly, i.e. did you build the software right.
    Verification
  13. The nodes in a graph.
    Vertices
  14. A measure used to express the computing time (complexity) of a piece of code relative to the size of the inputs. Examples: O(1)=Constant, O(log n)=Logarithmic, O(n)=Linear, O(n log n)=n Log n, O(n2)=Quadratic, O(n3)=Cubic, O(2n)=Exponential, and O(10n)=Exponential.
    Big-O Notation
  15. 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
  16. Testing a program or function based on knowing the internal working of the program or function. Based on making sure the testing covers all possible paths through the code.
    White-box Testing
  17. 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
  18. Testing a program or function based solely on the defined inputs and expected results without considering what is happening inside the code.
    Black-box Testing
  19. 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
  20. 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
  21. 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
  22. The number of items in a set.
    Cardinallity
  23. 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
  24. In hashing, when two keys hash to the same index in a hash table.
    Collision
  25. 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
  26. A function in a class definition (.h) file declared as static (ex: static someFunction() is declared in MyClass.h) can be called without having to create an instance of the class. For example: MyClass::someFunction() would call the static function as defined above. However, if there are multiple instances of the class all will share the same instance of the static function and static functions cannot access non-static variables or functions in a class.
    Static
  27. A method for handling collisions in a hash table, e.g. open addressing with linear probing, open addressing with double hashing, chaining, and buckets.
    Collision Resolution Techniques
  28. 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
  29. In a set, the data type of the items composing the set.
    Component (base) type
  30. 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
  31. In an undirected graph, two vertices in which there exists, in the graph, a path between them.
    Connected Vertices
  32. Functions that create an abstract data type. Examples: int X or new node(). Also the "constructor" function(s) in a C++ class.
    Constructors
  33. In a graph, a path greater than one that begins and ends on the same vertex. See Simple Cycle.
    Cycle
  34. The separation of a data type's logical properties from its' implementation. Another term for Data Encapsulation.
    Data Abstraction
  35. 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
  36. 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
  37. Formation of an idea, such as the qualities or properties of a thing, separate from any particular instances of a thing or material object. In computer science, a model of a complex system that includes only the details essential to the perspective of the viewer of the system.
    Abstraction
  38. A global variable declared as static in a source code file cannot be declared as extern in another source file and accessed.
    Static
  39. 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
  40. 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
  41. The set or range of data that an abstract data type acts on. Example: the domain of int data types is all whole numbers. See Abstract Data Type.
    Domain
  42. 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
  43. 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
  44. The connections between vertices in a graph.
    Edges
  45. A set with no members.
    Empty Set
  46. A specifier used to specify access to a global variable in one source file when the actual global variable is defined in another source file. A technique that is used more in old style procedural programming in C. Rarely if ever used in object oriented programming in C++.
    extern
  47. a means of diagramming an algorithm. This also does not have a rigid formal organization. But, there are some conventions we can look at:
    Flow Chart
  48. Controlling the sequence in which program commands are executed. See Sequential Execution and Transfer of Control.
    Flow Control
  49. 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
  50. A tree in which all leaf nodes are on the same level and every non-leaf node has two children..
    Full Binary Tree
  51. 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
  52. See Top Down Program Design.
    Functional Decomposition
  53. 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
  54. A technique for creating/calculating a unique index for a node in a hash table based on its' key.
    Hashing
  55. A complete binary tree with values stored so that no child has a key value greater than its parent.
    Heap
  56. In a directed graph, the number of edges a given vertex has coming in to it. See also Degree of a Vertex, Out Degree, Predecessors of a Vertex and Successors of a Vertex.
    In Degree
  57. 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
  58. A mechanism by which one class acquires the properties (member variables and member functions) of another class.
    Inheritance
  59. See Instantiation (noun).
    Instantance
  60. 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
  61. (noun) The object that is created during the process of Instantiation (v). An instance of a class.
    Instantiation
  62. (verb) The process of dynamically allocating memory for an object. When a class object is dynamically allocated it has been instantiated.
    Instantiation
  63. Testing of how functions work together. Done after Unit Testing.
    Integration Testing
  64. Functions that perform some sequential action on all data components in an object, example: setAll(someValue);
    Iterators
  65. A node in a binary tree that is neither the root nor a leaf;
    Internal Node
  66. A binary set operation that returns a set made up of only those items which are in both of the input sets.
    Intersection
  67. A node in a binary tree that has no children.
    Leaf
  68. In a graph, the number of edges from the starting vertex to the ending vertex in a path.
    Length of a Path
  69. 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
  70. In hashing, the process of converting the full range of key values into the full range of hash table indices.
    Mapping
  71. 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
  72. All of the functions declared within a class definition.
    Member functions
  73. All of the variables declared within a class or structure definition.
    Member variables
  74. A unit of organization of a software system. In most cases a module is a single source code file containing a number of functions designed to provide a set of related services. Classes in C++ can be referred to as modules. A conceptual idea not necessarily a programming unit.
    Module
  75. The organization of a program into logical units. An important characteristic of well designed programs. The use of classes in C++ helps to enforce this.
    Modularity
  76. Functions that observe the state of one or more data values. This includes (1) Predicates--checks to see if a certain property is true or false, example: isEmpty(), (2) Accessor or Selector--returns a copy of a data object, example: getX(), (3) Summary--returns information about an object as a whole, example: getListLength().
    Observers
  77. A software "bundle", usually thought of as being a class or structure consisting of a set of variables which define the states the object can exist in and a set of functions that define the behavior of that object. Software objects are often used to model the real-world objects that you find in everyday life.
    Object
  78. The process of identifying classes of objects and their interrelationships that are needed to solve a software problem.
    Object Oriented Design
  79. The use of data abstraction, inheritance and dynamic binding (memory allocation) to construct programs that are collections of interacting objects. The process of using objects as the building blocks of a program. See Procedural Programming, Top Down Design, Bottom Up Design.
    Object Oriented Programming
  80. All the functions that act on a domain of data. Example: for the int data type the operations include +, -, *, /, %, &, |, etc. See Abstract Data Type.
    Operations
  81. In a directed graph, the number of edges a given vertex has going out from it to other vertices. See also Degree of a Vertex, In Degree, Predecessors of a Vertex and Successors of a Vertex.
    Out Degree
  82. Two vertices in a graph are said to be adjacent if there is an edge connecting the two.
    Adjacent Vertices
  83. 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
  84. A theoretical hash function that maps keys uniformly and randomly into a hash table without any collisions.
    Perfect hash function
  85. A variable whose value is the address in memory of another variable. Pointers are typed. Thus you have int pointers that hold the address of int variables, float pointers that hold the address of float variables, etc. See the page on pointers for details on how to declare and use pointers.
    Pointer
  86. 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
  87. 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
  88. 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
  89. 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
  90. 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
  91. An artificial and informal way of describing an algorithm. NOTE: There is no formal syntax or structure known as pseudocode. It is just a plain English outline of a program. The advantage is it allows you to concentrate on HOW to solve a problem without worrying about the programming language syntax at the same time.
    Pseudocode
  92. 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
  93. 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
  94. Testing done after bugs have been fixed to insure the bug fixes have now introduced other problems.
    Regression Testing
  95. A statement of what is to be provided by a compugter system or software product.
    Requirements
  96. The document, which is prepared from the Statement of Work and presented to the customer. It's primary purpose is to varify with the customer the exact scope of requirements for a piece of software. The RDD is created during the Requirements Specification phase of software engineering.
    Requirements Definition Document or Requirements Description Document (RDD)
  97. The section of code in which a variable can be accessed. For example, any variable defined inside of a function has scope only within the function. It cannot be accessed from outside the function.
    Scope
  98. The normal sequence of command execution. Programming commands are executed one after the other. See Flow Control and Transfer of Control.
    Sequential Execution
  99. An unordered collection of distinct values (items or components) chosen from the possible values of a domain. The domain may also be called the Component (base) type.
    Set
  100. 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
  101. The document which describes in detail each module of a software system, each function within the module, the function inputs and outputs, and the algorithms each function will perform. The SDD or SDP contains a description of the interface between each module and the interface with the user. The SDD or SDP is created during the Design phase of software engineering.
    Software Design Document (SDD) or Software Development Plan (SDP)
  102. A disciplined approach to the design, production, and maintenance of computer programs that are developed on time and within cost estimates, using tools to help manage the size and complexity of the resulting software products.
    Software Engineering
  103. The document which presents a thorough analysis of the requirements of a piece of software. The SRS is based on the SOW and RDD and is written in terms the software designers and programmers can use. The SRS is created during the Analysis phase of software engineering.
    Software Requirements Specification (SRS)
  104. 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
  105. A detailed description of the functions, inputs, processing, outputs, and special requirements of a software product. This provides the information needed to design and implement the program.
    Software Specification
  106. The document which is a detailed, organized plan for testing a piece of software. The STP includes a description of all tests to be performed, the procedure for performing the test, the inputs for the test, and the expected outputs. The STP is created during the Testing phase of software engineering, but the normal approach is to begin working on a rough draft of the STP during the design phase so that every part of the system included in the design has a test or tests included in the STP.
    Software Test Plan (STP)
  107. The document, usually received from a customer, that states specifically the customer's requirements for a software product. The SOW is created during the Requirements Specification phase of software engineering.
    Statement Of Work
  108. An access specifier which has a several uses.
    Static
  109. 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
  110. 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
  111. A concentrated effort throughout the programming process to produce well organized code. It usually follows 5 steps in program development: Requirements Specification, Analysis, Design, Implementation, and Verification and Testing.
    Structured Programming
  112. 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
  113. A set X is a subset of Y if each item in X is also in Y.
    Subset
  114. 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
  115. A detailed list of what the program must be able to do. In large development projects this is usually referred to as the Statement of Work.
    Requirements Specification
  116. used to indicate the flow of control in the program.
    Arrows
  117. How you plan to solve the problem. This includes: (1) identifying the problem's imputs, desired outputs, and other constraints, (2) specifying the form of the data input (units, format, order, and arrangement), and (3) specifying the form of data output.
    Analysis
  118. Develope the Algorithm, a list of steps to be taken to solve the problem.
    Design
  119. Code the algorithm in C.
    Implementation
  120. used to indicate decisions (like the if statement).
    Diamonds
  121. This is a two step process. It involves (1) determining if the program does, in fact, produce results that satisfy the original requirements (Verification), and (2) the results are accurate (Validation).
    Verification and Testing
  122. used to indicate actions to be taken.
    Rectangles
  123. used to indicate the entry and exit points to a block of code.
    Small Circles
Author
Anonymous
ID
97466
Card Set
CS307 Glossary
Description
This is a glossary of all important terms used in CS307.
Updated