# Shared Flashcard Set

## Details

CS315 Final Vocabulary
Final Vocabulary for The University of Texas CS315 course
170
Computer Science
12/06/2009

Term
 Balanced tree
Definition
 a tree in which the heights of subtrees are approximately equal.
Term
 AVL Tree
Definition
 a self-balancing sorted binary tree, in which the heights of subtrees differ by at most 1.
Term
 Red-Black tree
Definition
 a self-balancing binary tree in which the nodes are "colored" red or black. The longest path from the root to a leaf is no more than twice the length of the shortest path.
Term
 Splay tree
Definition
 a self=balancing binary tree that places recently accessed elements near the top of the tree for fast access.
Term
 A*
Definition
 a heuristic search algorithm that attempts to find a desired goal using a heuristic function to estimate the distance from a given node to the goal.
Term
 acyclic
Definition
 describes a graph with no cycles (circular paths)
Term
Definition
 a representation of a graph in which each node has a list of nodes that are adjacent to it, i.e. connected to it by an arc
Term
Definition
 a representation of a graph in which a boolean matrix contains a 1 at position (i, j) iff there is an arc from node i to node j.
Term
 arc
Definition
 a link between two nodes in a graph
Term
 bandwidth
Definition
 information transfer rate of a network connection, in bits/second
Term
 B-tree
Definition
 a tree with a high branching factor, to minimize the number of disk accesses required to access a desired record
Term
 bijective
Definition
 describes a relation that is both injective and surjective (one-to-one and onto)
Term
 binary heap
Definition
 a data structure that implements a complete binary tree within an array, such that every parent node has a value that is less than the value of either of its children
Term
 binding
Definition
 an association of a name with a value
Term
 binding list
Definition
 a list structure that represents a set of bindings
Term
 boolean matrix
Definition
 a matrix whose elements are 0 or 1
Term
 bucket
Definition
 a collection, such as a linked list, of values that hash to the same value
Term
 cache
Definition
 to save a value locally to save re-computing or transferring it in the future
Term
 Cartesian product
Definition
 a set of pairs (x, y) of elements from two sets X and Y
Term
 clustering
Definition
 a situation in which many elements hash to the same hash value
Term
 collision
Definition
 when two values to be stored in a hash table have the same hash value
Term
 comparison
Definition
 the act of comparing two values to determine which is greater according to some ordering
Term
 critical path
Definition
 in a PERT chart or scheduling graph, a path from the initial state to the goal such that any increase in time required along the critical path will increase the time to complete the whole project
Term
 cycle
Definition
 a circular path in a graph
Term
 DAG
Definition
 directed acyclic graph
Term
 dense graph
Definition
 a graph such that a large fraction of possible connections among nodes are present, i.e. the number of edges is of the order of the number of vertices squared. cf. sparse graph
Term
 Dijkstra's algorithm
Definition
 an optimal greedy algorithm to find the minimum distance and shortest path in a weighted graph from a given start node
Term
 directed
Definition
 describes an arc that can only be traversed in one direction, or a graph with such arcs
Term
 directed acyclic graph
Definition
 a directed graph with no cycles. Every tree is a DAG, but a DAG may be more general.
Term
 discrete event simulation
Definition
 a simulation in terms of events, in which the highest-priority (least time) event is removed from an event queue and executed, which may have the effect of scheduling future events
Term
 domain
Definition
 the set of values that are the source values of a mapping
Term
 edge
Definition
 a link or arc between nodes in a graph
Term
 exclusive or
Definition
 a binary Boolean function whose output is 1 if its inputs are different. Abbreviated XOR.
Term
 extendible hashing
Definition
 another term for hashing with buckets
Term
 external sort
Definition
 a sort using external storage in addition to main memory
Term
 fold
Definition
 to process a set of items using a specified function; another term for reduce
Term
 geometric series
Definition
 a series in which each successive term is multiplied by a constant less than 1, e.g. 1 + 1/2 + 1/4 + 1/8 ....
Term
 graph
Definition
 a set of nodes and arcs connecting the nodes
Term
 greedy algorithm
Definition
 an algorithm that always tries the solution path that appears to be the best
Term
 hash function
Definition
 a function that is deterministic but randomizing, i.e. whose output is a relatively small integer that appears to be a random function of the key value
Term
 heuristic
Definition
 a function that estimates the distance from a given node to the goal in A* search. More generally, a method that generally gives good advice about which direction to go or how to approach a problem
Term
 in-place
Definition
 describes a sort that does not require any additional memory
Term
 injective
Definition
 describes a mapping in which each element of the domain maps to a single element of the range. Also, one-to-one.
Term
 internal sort
Definition
 a sort using only the main memory of the computer
Term
 iterator
Definition
 an object containing data and methods to iterate through a collection of data, allowing processing of one data item at a time.
Term
 latency
Definition
 the delay between asking for data from an I/O device and the beginning of data transfer
Term
Definition
 in a hash table, the fraction of the table's capacity that is filled
Term
 map
Definition
 in MapReduce, a program that processes an element of a Range set with each element of a Domain set.
Term
 mapping
Definition
 association of one or more elements of a Range set with each element of a Domain set
Term
 master
Definition
 a program that controls a set of other programs or devices
Term
 max queue
Definition
 a priority queue in which the maximum element is removed first
Term
 memory hierarchy
Definition
 the use of several kinds of memory hardware in a computer system, where the fastest memory (e.g. cache) is smallest, slower memory (RAM) is larger, and the slowest memory (disk) is largest
Term
 memory locality
Definition
 the processing of data in such a way that data that are located near each other by memory address are accessed nearby in time
Term
 min queue
Definition
 a priority queue in which the minimum element is removed first
Term
 minimum spanning tree
Definition
 a tree formed from the nodes of a graph and a subset of its edges, such that all nodes are connected and the total cost of the edges is minimal
Term
 on-line
Definition
 describes a sorting algorithm that can process items one at a time
Term
 one-to-one
Definition
 describes a mapping in which each element of the domain maps to a single element of the range. Also, injective
Term
 onto
Definition
 describes a mapping in which each element of the range is the target of some element of the domain. Also, surjective.
Term
 parsing
Definition
 analysis of a sentence of a language to determine the elements of the sentence and their relationship and meaning
Term
 path
Definition
 a sequence of steps along arcs in a graph
Term
 pattern
Definition
 a representation of a class of objects, containing some constant elements in relation to variable elements
Term
 pattern variable
Definition
 a part of a pattern that can match variable parts of an input
Term
 pivot
Definition
 in Quicksort, a "center" value using in partitioning the set to be sorted
Term
 priority queue
Definition
 a queue in which the highest-priority elements are removed first; without a priority value, the earliest arrival is removed first
Term
 randomized algorithm
Definition
 an algorithm in which the data to be processed or the device to process it is randomly selected
Term
 range
Definition
 a set of values that are the targets of a mapping
Term
 reduce
Definition
 to apply a given function to the elements of a given list. Also, fold.
Term
 rehash
Definition
 to apply a different hashing function to a key when a collision occurs
Term
 row-major order
Definition
 a way of storing a multiple-dimensioned array in memory, such that elements of a row are in adjacent memory addresses
Term
 scalability
Definition
 the ability of an algorithm or hardware system to grow to handle a larger number of inputs
Term
 shortest path
Definition
 the shortest path between a start node and a goal node in a weighted graph
Term
 simple path
Definition
 a path between two nodes in a graph that does not revisit any intermediate node
Term
 slack
Definition
 in a PERT chart or scheduling graph, the amount of time by which the time of an activity could be increased without affecting the overall completion time
Term
 slave
Definition
 a program or device that operates under control of a master
Term
 sparse array
Definition
 an array in which most of the elements are zero or missing
Term
 sparse graph
Definition
 a graph in which any node is connected to relatively few other nodes. cf. dense graph.
Term
 spatial locality
Definition
 being close together in space, i.e. memory address.
Term
 Splay tree
Definition
 a self-balancing binary tree that places recently accessed elements near the top of the tree for fast access.
Term
 stable
Definition
 describes a sort algorithm in which the relative position of elements with equal keys is unchanged after sorting.
Term
 surjective
Definition
 describes a mapping in which each element of the range is the target of some element of the domain. Also, onto.
Term
 symbol table
Definition
 a data structure that links names to information about the objects denoted by the names.
Term
 temporal locality
Definition
 being close together in time, i.e. memory accesses that occur within a short time of each other.
Term
 topological sort
Definition
 a linear ordering of nodes of an acyclic graph, such that a node follows all of its graph predecessors in the ordering
Term
 tree rotation
Definition
 changing the links in a binary tree to change the relative heights of the child subtrees, while leaving the sort order of the tree unchanged
Term
 undirected
Definition
 describes a graph in which the arcs may be followed in either direction
Term
 unparsing
Definition
 converting an abstract syntax tree into a sentence in a language, such as a programming language
Term
 vertex
Definition
 a node in a graph
Term
 weight
Definition
 a number that denotes the cost of following an arc in a graph
Term
 XOR
Definition
 exclusive or
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 that 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
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
 1. in Lisp, the function that constructs a pair of pointers, or basic element of 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 its 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
 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 sub-problems are reached.
Term
Definition
 a linked list in which each element has backward and forward 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 vocab 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, it's 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 size of 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 in 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 a computer program, e.g. a Java class hierarchy.
Term
 parent
Definition
 in a tree, a node that points to a given node.
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
 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
 preorder
Definition
 a way of processing a tree in which the parent node is processed before 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 problem.
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 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 strucure.
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.
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 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 its tags.
Supporting users have an ad free experience!