# CS221 Finals

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

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.
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.
5. Two vertices in a graph are said to be adjacent if there is an edge connecting the two.
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.
Algorithm
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.
Cardinallity
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.
Class
15. In hashing, when two keys hash to the same index in a hash table.
Collision
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.
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.
Difference
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.
Driver
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.
Edges
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.
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.
Implementation
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.
Instantiation
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.
Intersection
40. A node in a binary tree that has no children.
Leaf
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.
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.
Path
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.
Polymorphism
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.
Stub
58. A set X is a subset of Y if each item in X is also in Y.
Subset
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.
Union
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.
Vertices
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.
B-Tree
70. Nodes attached to the left and right of a parent node.
Child Node
71. *Cluster
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)
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.
Recursion
87. The first node in a binary tree.
Root
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.
Trie
 Author: Anonymous ID: 82276 Card Set: CS221 Finals Updated: 2011-04-27 16:34:34 Tags: CS221 Folders: Description: CS221 Study Terms for Finals (* are imcomplete) Show Answers: