# Algorithms

Spread the love

## Key Terms

• 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.