Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
118 Cards in this Set
- Front
- Back
Five steps in software development |
1. Requirements specification 2. Analysis 3. Design 4. Implementation 5. Development |
|
5 types of software testing (in order) |
1. Statement 2. Unit 3. Integration 4. Acceptance 5. Regression |
|
Big-O Notation |
constant O(1) logarithmic O(log n) linear O(n) n log n O(n log n) quadratic O(n^2) cubic O(n^3) exponential O(2^n) exponential O(10^n) |
|
statement of work |
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 |
|
requirements definition document |
A statement of what is to be provided by a computer system or software product |
|
software requirements specification |
define in detail exactly what the software must do |
|
software design document |
a detailed plan for the organization of the software including a description of any new algorithms and a detailed description of how the code will be organized and how each unit of code will be tested |
|
software test plan |
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 |
|
abstract data type |
A data type whose properties (domain and operations) are specified independently of any particular implementation. Examples: List, Stack, Queue, Tree, Graph, Set. |
|
acceptance testing |
use the RSD to guide the testing of requirements |
|
algorithm |
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. |
|
analysis of 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) |
|
Best fit memory allocation |
makes the best use of memory space but slower in making allocation |
|
binary search |
finds the position of a target value within a sorted array |
|
bottom up program design |
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. |
|
call by reference |
A function calling method in which the address or reference to the actual arguments are passed to a function. |
|
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. |
|
data abstraction |
The separation of a data type's logical properties from its' implementation. Another term for Data Encapsulation |
|
driver function for software testing |
A special function written to use as a testing function. It passes known inputs to selected functions and reports the returned values. * used to test lower level functions |
|
dynamic memory allocation |
Allocating memory for a variable, structure, or class instance after a program has started running |
|
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 |
|
first fit memory allocation |
the operating system begins at the start of primary memory and allocates memory from the first hole it encounters large enough to satisfy the request-to reduce amt of time spent analyzing available spaces |
|
fragmentation(referring to the heap) |
memory space being wasted-to avoid heap fragmentation memory management if performed by the person versus the OS |
|
greedy algorithm |
one that attempts to find the best solution by the shortest means possible |
|
heap |
A complete binary tree with values stored so that no child has a key value greater than its parent. |
|
information hiding |
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 |
|
integration testing |
replace all stubs and drivers with the real functions |
|
object oriented programming |
"Bottom-up program design" |
|
procedural programming |
functional decomposition
|
|
recursion |
the ability of a function to call itself |
|
regression testing |
testing done after bug fixes |
|
sequential search |
each element of the array is compared to the key, in the order they occur in the array, until the first element matching the key is found |
|
software validation |
the process of determining the degree to which the software does, in fact, produce the result results that satisfy the original requirement |
|
software verification |
the process of determining the degree to which software functions correctly |
|
static memory allocation |
Memory that is allocated at program start up or when a function is called. Variable declarations in a program result in static memory allocation. |
|
stepwise refinement |
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 |
|
stub function for software testing |
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 |
|
top-down program design |
functional decomposition/procedural programming |
|
unit testing |
use separate tests for each possible path through a function |
|
2-3 tree |
each node may contain 1 or 2 keys and have 2-3 subtrees |
|
AVL tree |
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 |
|
B-tree |
each node may contain a large number of keys |
|
binary 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 |
|
child node |
node whose parent is the root |
|
complete binary tree |
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. |
|
internal node |
A node in a binary tree that is neither the root nor a leaf |
|
leaf node |
a node in a binary tree that has no children |
|
parent node |
a node having children |
|
root |
the first node of a tree |
|
sub-tree/branches |
internal nodes beneath the root |
|
trie |
ordered tree data structure |
|
adjacent vertices |
two nodes which share a common link |
|
adjacency set |
a way of implementing a graph in memory and connections between nodes are represented in a linked list of connections for each node |
|
adjacency matrix |
a way of implementing a graph in memory in which the connections between nodes are represented in a 2D array |
|
connected components |
a subset of nodes of a graph for which there is a path from any one to all others in the subset |
|
connected vertices |
when there exists a path between two vertices they are said to be this |
|
cycle |
a path that begins and ends on the same node |
|
degree of a vertex |
the number of links in a graph for which a given node is one of the endpoints |
|
directed graph |
a graph in which the links between nodes go only in one direction |
|
edges |
the connections between nodes in a graph |
|
minimal spanning tree of a graph |
determining the shortest path to visit every vertex in the graph |
|
path |
a list of nodes indicating those that must be visited in order to get from one node to another |
|
predecessors of a vertex |
all nodes in a graph from which a given node has links coming from the other nodes to the given node |
|
simple cycle |
a path of three or more nodes that starts and ends on the same node and never visits any node more than once, except the starting node |
|
successors of a vertex |
all nodes in a graph to which a given node has links going from the given node to the other nodes |
|
vertices |
the nodes in a graph which may be represented by a structure or a class object |
|
weighted graph |
a graph in which the links between nodes have some value associated with them |
|
component(base) type |
the data type of the items composing the set |
|
subset |
a set X is a subset of Y if each item of X is also in Y |
|
universal set |
the set containing all of the values of the component type |
|
empty set |
a set with no members |
|
cardinality |
number of items in a set |
|
set intersection |
returns a set made up of all of the items in both of the input sets |
|
set difference |
returns a set made up of all items that are in the first set but not the second |
|
symmetrical difference |
returns a set made up of all items that are in the first or second set but not both |
|
set union |
returns a set made up of all items that are in either of the input sets |
|
cluster |
a series of adjacent filled entries in a hash table |
|
collision |
when 2 keys hash to the same index in a hash table |
|
hash table |
an array of data structures or a large number of records stored in a file on disk. |
|
hash function |
the technique used to calculate a unique index into the hash table from a key. |
|
buckets |
hash table is divided up into equal sized groups of locations and hash indices are calculated for the number of groups, thus each index in the hash table can hold several records |
|
chaining |
a linked list of all records is hashing to the same index are created from the first record in that index |
|
linear probing |
a scheme for resolving hash collisions by sequentially searching the hash table for a free location |
|
load factor |
the ratio of the number of filled entries in a hash table to the number of entries in the table |
|
perfect hash function |
a hash function that maps keys uniformly and randomly into the table without collisions |
|
class |
A structured type in a programming language containing variables and the functions which operate on those variables. Used to represent an abstract data type. |
|
constructor function |
Functions that create an abstract data type |
|
destructor function |
called when objects are destroyed/deallocated |
|
function overloading |
The ability to have two or more functions in a class with the same name but different number and/or types of arguments |
|
implementation file |
the file that implements the class/cpp file |
|
instantiation |
The process of dynamically allocating memory for an object |
|
polymorphism |
ability to process objects differently depending on their data type or class; ability to redefine methods for derived classes |
|
private |
Variables and functions in a structure or class which can only be accessed from within the object. |
|
protected |
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. |
|
public |
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. |
|
show how to define a data structure containing an int stockNum, double price, and char array called desc of 128 characters |
struct InvItem { int stockNum; double price; char desc [128]; }; ** don't forget this semicolon! |
|
declare a pointer called sPtr to a structure called InvItem, then dynamically allocate memory for the struct and set sPtr pointing to it |
InvItem *sPtr; InvItem = new sPtr; sPtr = new InvItem(); |
|
copy the values 54321, 9.95 and "left-handed widget" into stockNum, price, and desc fields of a new data struct sPtr points to |
sPtr -> stockNum = 54321; sPtr -> price = 9.95; strcpy(sPtr ->desc, "left-handed widget"); |
|
write the setID function of the simple class InventoryItem containing the variable m_iID of type int |
void InventoryItem::setID(int x) { m_iID = x; } |
|
declare a pointer called ItmPtr to a class of type InventoryItem; dynamically instantiate an instance of the class and set the pointer ItmPtr pointing to it; call setID in the instance that ItmPtr is pointing to it and pass it the value 12345 |
InventoryItem *ItmPtr; ItmPtr = new InventoryItem; ItmPtr -> setID(12345); |
|
create a vector called strVec to hold strings add the string "testing" to the vector remove the last item from the vector |
vectorstrVec; strVec.push_back("testing"); strVec.pop_back; |
|
write a function that traverses a binary tree; call a function called doSomething(TreeNode *thisNode) for each node in the tree |
void MyTree::Traverse(TreeNode *rt) { if (rt !=Null) { traverse (rt -> left) doSomething (rt) traverse (rt -> right) } } |
|
write a recursive function called SumIt which calculates a sequence of numbers; the function takes 2 arguments which are ints and returns an int |
int SumIt(int m, int n) { if (m==n) return m+m; else return (m+m) + SumIt (m+1, n); } |
|
using set template do the following: create set of string objects called names add the name jason to the set declare an iterator called itr to items in the set names; locate the name jason in names and set the iterator itr to reference it |
setnames; names.insert ("jason"); set ::iterator itr; itr = names.find ("jason"); |
|
Bubble sort |
A type of transposition sorting; the simplest sorting method (scanning a swapping) As you repeatedly scan the array of records making comparisons, the lower key values gradually move to the start of the array |
|
Insertion sort |
type of Insert and Keep sort; Done by moving items out of a set of unsorted records into a set of sorted records; |
|
Tree sort |
type of insert and keep sort; is already in order if an in-order traversal is made; uses insertNode function and performs an in-order traversal to list records in sorted order |
|
Selection sort |
type of priority queuing sort: divides array into sorted/unsorted sections and repeatedly removes the record with the largest key from unsorted section and moves it to the front of the sorted section |
|
Heap sort |
type of priority queuing sort: repeatedly dequeuing structures from the heap and moving them into an array will give a sorted array |
|
quick sort |
type of Divide and conquer: partitions data into 2 smaller groups arbitrarily and places all keys <= "pivot key" on the left side of the array and all keys >= "pivot key" on the right side; recursively calls QuickSort() to the left and right halves then merges the two arrays |
|
merge sort |
type of divide and conquer: frequently used to sort very large collections of data; divide array into 2 parts and recursively call mergeSort() to sort the first half of the array and same to second half respectively; merge the two arrays |
|
shell sort |
type of diminishing increment sort: subdivides the array of structures into smaller pieces by selecting every nth record then sorting that group of structures |
|
proxmap sort |
type of address calculation sort; conceptually similar to hashing; uses a variation on hashing with buckets of different sizes |
|
radix sort |
type of address calculation sort; uses keys that must be integers of some standard length or keys that can be mapped to this; sort to all 0s,1s,2s etc. then arrange groups into ascending order; repeat this sorting with the 10s, 100s, 1000s etc. |
|
define how an adjacency set works |
a linked list represents vertices and another linked list represents edges |
|
define how an adjacency matrix works |
an array of structs or classes represents vertices while a 2D array of int represents edges |
|
declare static instance of a structure and declare a pointer to that structure statically then dynamically |
struct Name { int x; char c; char array[50];} //static instance Name instance1; Name *sptr; Name *sptr = &instance 1; //dynamically Name *sptr; sptr = newName; |
|
declare variables and pointers to those variables |
int iVar; double dVar; char cVar; //pointers int *iptr = &iVar; double *dptr = &dVar; char *cptr = &cVar; |