Shared Flashcard Set

Details

cs315 vocab
vocabulator for a cs315 test
81
Computer Science
Undergraduate 2
10/11/2009

Additional Computer Science Flashcards

 


 

Cards

Term
Abstract Data Type
Definition
A description of operations on a data type that could have multiple possible implementations.
Term
ancestors
Definition
in a tree, the union of a node's parent and the parent's ancestors.
Term
Array
Definition
A contiguous block of memory containing elements of the same type, accessed by a numeric index.
Term
Association List
Definition
a list of pairs, where each pair has a key and a value associated with the key.
Term
backtrack
Definition
in a tree search, to move back from the node currently being examined to its parent.
Term
base case
Definition
a simple case that can be solved easily, without recursion.
Term
Big O
Definition
an abstracted function that describes the amount of computer time or memory space rquired by an algorithm, as a function of problem size. For problems larger than a certain size, the actual time or space required will be less than the Big O multiplied by some constant.
Term
Binary Tree
Definition
A tree in which each node has at most two children.
Term
Binary Search
Definition
Search of a binary tree or other structure, in which the size of the set to be searched is cut in half at each step.
Term
Boxed Number
Definition
a number that is defined as an object, so that it has a runtime type and meethods that can be used, e.g. Integer in Java.
Term
Branching Factor
Definition
in a search tree, the number of children of a given node. Often, the branching factors of individual nodes will vary, so an average value may be used.
Term
Child
Definition
in a tree, a node pointed to by a parent node.
Term
Circularly Linked List
Definition
a linked list in which the last element points back to the first element.
Term
Circular Queue
Definition
a queue implemented within an array, where the first element of the array logically follows the last element.
Term
Class
Definition
In object-oriented programming, a description of a set of similar objects.
Term
Cons
Definition
in Lisp, the function that constructs a pair of pointers, or basic element of a list structure. 2. to make a cons data structure. 3. a cons data structure.
Term
Constructive
Definition
describes a function that makes a new data structure but does not modify its arguments.
Term
Depth
Definition
the number of links between the root of a tree and the leaves.
Term
Depth-First-Search
Definition
a search in which children of a node are considered (recursively) before siblings are considered.
Term
Dereference
Definition
to convert from a pointer (address) to the data that it is pointing to.
Term
Descendants
Definition
All nodes below a given node in a tree.
Term
Design Pattern
Definition
A pattern that describes a set of similar programs.
Term
Destructive
Definition
Describes a function that modifies its arguments.
Term
DFS
Definition
Depth-First search
Term
Divide and Conquer
Definition
a problem-solving strategy in which a problem is broken down into sub-problems, until simple subproblems are reached.
Term
Doubly Linked List
Definition
a linked list in which each element has both forward and backward pointers.
Term
Fair
Definition
describes a process in which every arriving customer will eventually be served.
Term
FIFO
Definition
first-in, first-out: describes the ordering of a queue.
Term
Filter
Definition
a process that removes unwanted elements from a collection.
Term
first-child/next-sibling
Definition
a way of implementing trees that uses two pointers per node but can represent an arbitrary number of children of a node.
Term
Garbage
Definition
storage that is no longer pointed to by any variable and therefore can no longer be accessed.
Term
garbage collection
Definition
the process of collecting garbage for recycling.
Term
Gedanken
Definition
describes a thought experiment or view of an entity.
Term
Goal
Definition
an item (or description of items) being sought in a search.
Term
Grammar
Definition
a formal description of a language in terms of vocabulary and rules for writing phrases and sentences.
Term
Immutable
Definition
describes a data structure that cannot be changed once it has been created, such as Integer or String in Java.
Term
Inorder
Definition
an order of processing a tree in which the parent node is processed in between its children.
Term
interior node
Definition
a node of a tree that has children.
Term
intersection
Definition
given two sets, the intersection is the set of elements that are members of both sets.
Term
intractable
Definition
a problem that is so hard (typically exponential) that it cannot be solved unless the problem is small.
Term
leaf
Definition
a tree node containing a contents value but with no children.
Term
LIFO
Definition
last-in, first out: describes the order of a stack.
Term
Linear
Definition
O(N), a problem whose solution requires a linear amount of time or space if the problem is of size N.
Term
Link
Definition
a pointer to the next element in a linked list.
Term
Linked List
Definition
a sequence of records, where each reqcord contains a link to the next one.
Term
Merge
Definition
in MapReduce, a program that proces an element of the input and emits one or more (key,value) pairs.
Term
Node
Definition
an element of a linked list, tree, or graph, often represented by a data structure.
Term
Null Dereference
Definition
a runtime error that occurs when an operation such as a method call is attempted on a null pointer.
Term
Object
Definition
a data structure that can be identified at runtime as being a member of a class.
Term
ontology
Definition
a description of the kinds of objects that exist in computer programs, e.g. a Java class hierarchy.
Term
Operator
Definition
in a search tree, a program that changes a state into a child state, e.g. a move in a game.
Term
Parent
Definition
in a tere, a node that points to a given node.
Term
Pointer
Definition
a variable containing the address of other data.
Term
Postorder
Definition
an order of processing a tree in which the parent node is processed after its children.
Term
pre-Order
Definition
an order of processing a tree in which the parent node is processed before its children.
Term
Quadratic
Definition
O(N^2), a problem whose solution requires a quadratic amount of time or space if the problem is of size n.
Term
Queue
Definition
a data structure representing a sequence of items, which are removed in the same order as they were inserted.
Term
Random Access
Definition
describes a data structure or device in which all accesses have the same cost, O(1)
Term
Recursion
Definition
a case where a program calls itself.
Term
Recursive Case
Definition
a condition of the input data where the data will be handled by call(s) to the same program.
Term
Reference
Definition
a pointer to data.
Term
Reference Type
Definition
a type in which variables of that type are pointers to objects.
Term
Root
Definition
the top node of a tree, from which all other nodes can be reached.
Term
Runtime Stack
Definition
a stack containing a stack frame of variable values for each active invocation of a procedure.
Term
Scope
Definition
is an enclosing context where values and expressions are associated.
Term
search
Definition
to look through a data structure until a goal object is found.
Term
Sentinel
Definition
an extra record at the start or end of a data structure such as a linked list, to simplify the processing.
Term
Set Difference
Definition
given two sets, the set difference is the set of elements of the first set that are not members of the second set.
Term
shadow
Definition
to hide similar items with the same name.
Term
Side-effect
Definition
any effect of a procedure other than returning a value, e.g. printing or modifying a data structure.
Term
Sort
Definition
to modify the order of a set of elements sot htat a desired ordering holds between them, e.g. alphabetic order.
Term
Stack Frame
Definition
a section of the runtime stack holding the values of all variables for one invocation of a procedure.
Term
Stack Space
Definition
the mount of space on the runtime stack required for execution of a program.
Term
State
Definition
a description of the state of a process, such as a board game.
Term
Structure sharing
Definition
a case where tow data structures share some elements.
Term
Successor
Definition
the next element in a linked list.
Term
tail recursive
Definition
a function whose value either does not involve a recursive call, or is exactly the value of a recursive call.
Term
Taxonomy
Definition
a classification of objects into a tree structure that groups related objects.
Term
Union
Definition
Given two sets, the union is the set of elements that are members of either set.
Term
Well-Founded Ordering
Definition
an ordering that can be guaranteed to terminate, e.g. starting at a positive integer and counting down to 0.
Term
XML
Definition
Extensible Markup Language, a way of writing data in a tree-structured form by enclosing it in tags.
Supporting users have an ad free experience!