Abstraction: The ability to separate the high-level view of an entity from the low-level details; a central intellectual tool in computer science.
Algorithm discovery: Creating an algorithmic solution to a given problem.
Analysis of algorithms: The process of determining the time and space efficiency of an algorithm, resulting in a function described with ? notation.
Approximation algorithm: A solution to a possibly intractable problem that is not guaranteed to give the best answer, but gives a good approximation of the best answer in a tractable amount of time.
Benchmarking: The process of timing an algorithm on a particular machine and system in order to determine how it performs. This process is usually used to evaluate a machine and system, rather than a particular algorithm.
Best case: For a particular size of input, the least work an algorithm could do based on the configuration of the input values.
Binary search algorithm: An algorithm that searches for a particular value in a sorted list of values and runs in ?(lg n) time in the worst case.
Bin-packing problem: Given a list of objects and some bins, find the minimum number of bins required to contain the objects. A difficult, probably intractable problem.
Brute force algorithm: An algorithm that tries all possible solutions in order to find the optimal solution.
Computation: A sequential operation that calculates some value and saves the result.
Conditional statements: The “question-asking” operations of an algorithm.
Control operations: Operations used in an algorithm that alter the top-to-bottom flow of control; usually, conditional and iterative operations.
Correctness: An attribute of an algorithm that says that it solves the correct problem in the correct way.
Ease of understanding: An attribute of an algorithm that describes how easy it is to understand and modify the algorithm.
Efficiency: An attribute of an algorithm that captures the time and space requirements of the algorithm.
Elegance: An attribute of an algorithm that captures the cleverness and sophistication of the algorithm.
Exponential algorithm: An algorithm that runs in ?(2n) or worse.
Hamiltonian circuit: Find a path through the graph that visits each node in the graph once and returns to the start node. A graph problem that is probably intractable.
Infinite loop: A loop in which the continuation condition never becomes false.
Input: A sequential operation for receiving data from the outside world.
Intractable: A description of a problem or algorithm for which the best-known performance is ?(2n).
Library: A collection of useful algorithms.
Loop: The repetition of a block of instructions.
Natural language: A language that is spoken and/or written by people in everyday life (for example, English).
Order of magnitude: The general form of the curve that a particular function exhibits, for instance, linear, quadratic, polynomial, or exponential.
Output: A sequential operation for presenting results to the outside world.
Pattern matching: The problem of finding one pattern within a larger string.
Polynomially bounded: A problem that has a known polynomial time algorithm.
Posttest loop: A loop in which the continuation condition is tested at the end of each pass through the loop.
Pretest loop: A loop in which the continuation condition is tested at the beginning of each pass through the loop.
Primitive operation: The instructions that we assume the computing agent for an algorithm understands and can execute.
Program maintenance: The task of maintaining and updating a piece of software once it has been created and released for public use.
Pseudocode: A notation for describing algorithms that lies between a formal program and plain natural language. Typically, pseudocode is highly structured and uses well-understood and computable statements.
Searching: The problem of finding a particular value in a list of values.
Selection sort algorithm: An algorithm for sorting a collection of values that repeatedly finds the largest values in the unsorted section of the list and moves them into the correct position.
Sequential algorithm: An algorithm that contains only sequential operations so that it is executed from top to bottom without any choice points or loops (also called a straight-line algorithm).
Sequential search: The algorithm for searching an unordered collection of data for a particular value.
Sorting: The problem of ordering a collection of values into some specified order: alphabetic, numeric, and so on.
Straight-line algorithm: An algorithm that contains only sequential operations so that it is executed from top to bottom without any conditionals or loops (also called a sequential algorithm).
Time/space tradeoff: Choice in which you gain something by giving up something else.
Top-down design: The process of viewing an operation at a high level of abstraction, and then later filling in the details required to implement the high-level operation.
Variable: A named location for storing data values.
Worst case: For a particular size of input, the most work an algorithm might have to do is based on the configuration of the input values.