# Shared Flashcard Set

## Details

CS315 Novak
N/A
81
Computer Science
03/10/2010

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 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 required 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 methods 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
 Circular Queue
Definition
 a queue implemented within an array, where the first element of the array logically follows the last element.
Term
Definition
 A linked list in which the last element points back to the first element.
Term
 Class
Definition
 In object-oriented programming, a description of a set of similar objects
Term
 Cons
Definition
 1. in Lisp, the function that constructs a pair of pointers, or basic element of list structure.2. to make a cons data structure3. a cons data structure
Term
 Constructive
Definition
 Describes a function that makes a new data structure but does not modify its arguments.
Term
 DFS
Definition
 Depth-first search
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 is pointed 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
 Divide and Conquer
Definition
 A problem-solving strategy in which a problem is broken down in sub-problems, until simple subproblems are reached
Term
Definition
 A linked list in which each element has both forward and backward pointers.
Term
 FIFO
Definition
 first-in, first-out: describes the ordering of a queue.
Term
 Fair
Definition
 describes a process in which every arriving customer will eventually be served
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 from recycling.
Term
 Gedanken
Definition
 Describes a thought experiment or view of an entity.
Term
 Goal
Definition
 A set of nodes and arcs connecting the nodes.
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
 Interior node
Definition
 A node of a tree that has children.
Term
 Intersection
Definition
 Given to 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
 LIFO
Definition
 last-in, first-out, describes the order of a stack
Term
 Leaf
Definition
 A tree node containing a contents value but with no children.
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
Definition
 A pointer to the next element in a linked list.
Term
Definition
 a sequence of records, where each record contains a link to the next one.
Term
 Merge
Definition
 To combine two ordered linear structures into one.
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
 Inorder
Definition
 An order of processing a tree in which the parent node is processed in between its children.
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 a computer program, e.g. a Java class hierachy.
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
 Preorder
Definition
 An order of processing a tree in which the parent node is processed before its children.
Term
 parent
Definition
 In a tree, 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
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
 The area of program text over which a variable can be referenced.
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
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 so that 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 amount 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 two 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 terminated, e.g. starting at 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!