## Basic Algorithms Resources

- More information on pseudocode
- A discussion of sequential search
- More information on sequential search
- TED talk on “How Algorithms Shape Our World”

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