CS221 Finals

Card Set Information

CS221 Finals
2011-04-27 12:34:34

CS221 Study Terms for Finals (* are imcomplete)
Show Answers:

  1. 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
  2. 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
  3. 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
  4. 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
  5. Two vertices in a graph are said to be adjacent if there is an edge connecting the two.
    Adjacent Vertices
  6. 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.
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. The number of items in a set.
  14. 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.
  15. In hashing, when two keys hash to the same index in a hash table.
  16. 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
  17. In a set, the data type of the items composing the set.
    Component (base) type
  18. 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
  19. In an undirected graph, two vertices in which there exists, in the graph, a path between them.
    Connected Vertices
  20. Functions that create an abstract data type. Examples: int X or new node(). Also the "constructor" function(s) in a C++ class.
    Constructor function
  21. In a graph, a path greater than one that begins and ends on the same vertex. See Simple Cycle.
  22. The separation of a data type's logical properties from its' implementation. Another term for Data Encapsulation.
    Data Abstraction
  23. 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
  24. 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
  25. 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.
  26. 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
  27. 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.
  28. 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
  29. The connections between vertices in a graph.
  30. A set with no members.
    Empty Set
  31. 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
  32. 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
  33. A complete binary tree with values stored so that no child has a key value greater than its parent.
    Heap, when referring to trees
  34. Code the algorithm in C.
  35. 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
  36. (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.
  37. Testing of how functions work together. Done after Unit Testing.
    Integration Testing
  38. A node in a binary tree that is neither the root nor a leaf.
    Internal Node
  39. A binary set operation that returns a set made up of only those items which are in both of the input sets.
  40. A node in a binary tree that has no children.
  41. 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
  42. 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.
  43. A theoretical hash function that maps keys uniformly and randomly into a hash table without any collisions.
    Perfect hash function
  44. 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.
  45. 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
  46. 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
  47. 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
  48. 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
  49. 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
  50. Testing done after bugs have been fixed to insure the bug fixes have now introduced other problems.
    Regression Testing
  51. The normal sequence of command execution. Programming commands are executed one after the other. See Flow Control and Transfer of Control.
    Sequential Execution
  52. 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
  53. 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
  54. 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
  55. 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
  56. 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
  57. 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.
  58. A set X is a subset of Y if each item in X is also in Y.
  59. 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
  60. 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
  61. A binary set operation that returns a set made up of all items that are in either of the input sets.
  62. Testing of individual functions.
    Unit Testing
  63. 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
  64. The nodes in a graph.
  65. 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
  66. All subtrees are kept in perfect balance. Each node may contain one or two keys and have two or three subtrees.
    2-3 tree
  67. *Best-fit memory allocation
    Best-fit memory allocation
  68. *Binary Search
    Binary Search
  69. This is a special form of the 2-3 tree in which each node is allowed to have a large number of keys.
  70. Nodes attached to the left and right of a parent node.
    Child Node
  71. *Cluster
  72. *Destructor function
    Destructor function
  73. *Double hash function
    Double hash function
  74. *First-fit memory allocation
    First-fit memory allocation
  75. *Fragmentation, when referring to the heap
    Fragmentation, when referring to the heap
  76. *Greedy Algorithm
    Greedy Algorithm
  77. 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
  78. 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
  79. 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
  80. *Heap, when referring to memory
    Heap, when referring to memory
  81. *Linear Probing
    Linear Probing
  82. A tree whose total edge weights is the minimum of all the possible spanning trees for the graph.
    Minimal Spanning Tree of a graph
  83. *Object oriented programming (OOP)
    Object oriented programming (OOP)
  84. *Open addressing
    Open addressing
  85. A node that has either one or two child nodes.
    Parent Node
  86. 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.
  87. The first node in a binary tree.
  88. *Shortest path in a graph
    Shortest path in a graph
  89. *Sub-trees or branches
    Sub-trees or brances
  90. 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
  91. *Templates (Function and Class)
    Templates (Function and Class)
  92. This is a special type of tree structure. Quite simply this is a form of alphabetical organizing of node keys.