Spread the love

Basic Algorithms Resources

Efficiency of Algorithms

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.