A balanced search tree where each node can have two or three children, maintaining efficient search, insertion, and deletion operations.

A conceptual model that defines object in terms of a set of operations (their inputs and outputs).

Techniques that use hypothetical adversaries to establish lower bounds on algorithm complexity, demonstrating the minimal resources required.

The process of creating a collection of records.

A formal description for a process taken by a computer program.

A analytic process to determine the runtime cost of an algorithm.

Programming Languages

In parsing, the property that a given string can be interpreted in multiple ways under the associated grammar.

A technique in algorithm analysis used to average the running time of operations over a sequence of operations, providing a better understanding of the overall efficiency than analyzing individual operations in isolatio

Methods for assessing the complexity of different computational problems.

Techniques for examining the performance and behavior of computer programs.

A contiguous collection of same-sized objects in memory.

A contiguous collection of same-sized objects in memory.

Implementing a list using an array.

Implementing a queue using an array.

Implementing a stack using an array.

An array-based list implementation in Java

A generic term for a finite state machine.

Scenario describing algorithm performance for the weighted average of all inputs for a given size.

A self-balancing binary search tree.

A balanced tree data structure that maintains large sorted lists and allows for efficient insertion, deletion, and search operations. Widely used to store datbases on disk.

Programming Languages

A notation used to express context-free grammars, commonly used in the description of programming languages.

Binary tree that maintains balance to improve performance.

Scenario describing algorithm performance for the best of all inputs for a given size.

Notation used to describe an upper bound on performance of an algorithm.

Notation used to describe a lower bound on performance of an algorithm.

Notation used to describe performance of an algorithm, indicating that the upper and lower bounds are the same within a constant factor.

A (largely theoretical) variant on insertion sort where the location for inserting the next object into the sorted portion of the list is found using binary search. This minimizes the number of comparisons required, but in practice does not improve the amount of swaps required.

A divide-and-conquer algorithm that finds the position of a target value within a sorted array.

A binary tree where each node has a key greater than its left child and less than its right child.

A binary tree where each node has a key greater than its left child and less than its right child.

Design techniques for the node of a binary tree.

Evaluating the memory requirements for storing and processing binary trees.

Terms and definitions related to binary trees.

Technique for visiting all nodes in a binary.

A Binomial Tree of order 0 has 1 node. A Binomial Tree of order k can be constructed by taking two binomial trees of order k-1 and making one the leftmost child of the other.

A type of bucket sort, where a bucket stores only one key value (though it might store multiple records with that key value).

A spatial data structure with the shape of a binary tree, that splits the key space in half, alternating through each dimension.

A data structure that assigns each key to a position in an array that stroes a single bit to indicate if that key is in the represented set or not.

A mathematical expression where boolean variables are combined using boolean operators.

Programming Language Construct

Programming Languages

A mathematical expression where boolean variables are combined using boolean operators.

Programming Language Construct

Programming Languages

A mathematical operator whose parameters are boolean variables.

An algorithm for performing string matching.

An organized process to visit all nodes in a graph by first visiting all nodes one step from the source, then two steps, and so on. If the graph were actually a tree, this would be visitng nodes level by level.

A simple, but inefficient, comparison-based sorting algorithm.

A type of hashing where keys are hashed to a bucket that might store multiple records.

Distributes elements into buckets and sorts each bucket individually.

A memory allocation algorithm that splits blocks of memory in half, with the two halves defined to be buddies.

A data structure that caches frequently accessed data in memory to improve access times.

Chained Matrix Multplication Problem

A series of matricies are multiplied together. While the order in which adjacent matricies are multiplied will not change the final answer, it can greatly affect the cost if the matricies are of different sizes.

Determining the inputs to a Boolean circuit that result in a true output.

Determining the inputs to a Boolean circuit that result in a true output.

Object-Oriented Programming

Programming Languages

A classification of object types with super-class/sub-class relationships.

Identifying the largest clique within a graph.

Identifying the largest clique within a graph.

A property of a relation that ensure the relation is closed under certain operations.

Use of a closure property to help prove whether a given language is included or excluded as a member of a particular language classification.

The process of determining the classification for a langauge, such as regular, context free, etc.

A measure of the extent to which a program is executed during testing.

The process of optimizing code to improve performance and efficiency, separate from improving the underlying algorithm.

Techniques used to handle collisions in hashing.

A text-based interface for interacting with computer programs by entering commands

Arguments passed to a program at the command line, used to customize program behavior.

A function that compares two objects (generally records in a collection for sorting or searching purposes).

Programming Languages

A program that takes a program as input and converts it to another form for more efficient processing.

Binary trees where all levels except possibly the last are completely filled.

A structural design pattern that composes objects into tree structures to represent part-whole hierarchies, allowing clients to treat individual objects and compositions uniformly.

The combining of distinct parts or elements to form a whole.

Programming Language Construct

Programming Languages

A branch statement like an IF or CASE statement.

An abstract data type that stores multiple elements, providing methods for accessing and modifying them.

A grammar for a language that is confext free.

A language generated by a context-free grammar.

An algorithm to minimize the number of nodes in a DFA.

An algorithm to minimize the number of nodes in a DFA.

A data representation and its associated operations. Alternatively, the implementation for an ADT.

A type together with a collection of operations to manipulate the type.

Techniques used to identify and correct errors in software.

The process of reasoning from general principles to derive specific instances.

One object (the delegating object) passes responsibility for a task to another object (the delegate).

A graph traversal algorithm. Whenever vertex v is visited during a traversal, DFS will recursively visit all of v's unvisted neighbors. In a tree, this results in a preorder traversal.

A graph traversal algorithm. Whenever vertex v is visited during a traversal, DFS will recursively visit all of v's unvisted neighbors. In a tree, this results in a preorder traversal.

Reusable solutions to common design problems in software development.

A theoretical machine used to recognize regular languages by accepting or rejecting strings. A pair of states has at most a single transition between them for a given symbol.

A theoretical machine used to recognize context-free languages by accepting or rejecting strings. A pair of states has at most a single transition between them for a given symbol.

An abstract data type representing a collection of key-value pairs.

Within a buffer pool, a piece of information associated with each buffer that indicates whether the contents of the buffer have changed since being read in from backing storage.

A collection of sets that are mutually exclusive, supporting efficient union and find operations.

A device for storing and retrieving digital data using magnetic storage or other media.

A linked list where each node has pointers to both the previous and next nodes.

Allocates memory from a pool as needed

The Eclipse integrated programming environment.

A measure of the similarity between two strings, calculated by counting the minimum number of operations required to transform one string into another.

An approach to comparing to things by actually seeing how they perform. Most typically, we are referring to the comparison of two programs by running each on a suite of test data and measuring the actual running times. Empirical comparison is subject to many possible complications, including unfair selection of test data, and inaccuracies in the time measurements due to variations in the computing environment between various executions of the programs.

A distint subset that results from partitioning a set based on an equivalence relation.

Any sorting algorithm that can only reorder the list by swapping adjacent records.

The operation of computing a value to a given power.

The operation of computing a value to a given power.

A tree structure meant to represent a mathematical expression. Internal nodes of the expression tree are operators in the expression, with the subtrees being the sub-expressions that are its operand. All leaf nodes are operands.

Sorting methods that involve data stored outside of main memory, such as on disk.

An O(n log n) algorithm to compute the discrete Fourier transform, used for example to speed up polynomial multiplication.