The Role of Algorithms in Computing

Algorithms

Characteristics

• A sequence of steps that transforms some input into an output.

• Computational problem: A specification of an input/output pair.

  • Example: sorting
    • Input: An unsorted list of numbers.
    • Output: A permutation of the list, where all numbers are greater than or equal to the element in the previous index.

• Problem instance: a specific real-life problem to solve.

  • For example, sort the list [1, 3, 2, 7, 1, 3].

• Algorithm Correctness: if an algorithm always halts with the correct output for every input. This means an algorithm cannot have an infinite loop for any input instance.

  • Example of useless incorrect algorithms: a badly implemented for-loop.
  • Example of a useful incorrect algorithm: a non-deterministic test. Sometimes, getting the right answer within a certain error rate is incredibly useful.

Places Where Algorithms Are Useful

Basically everywhere.

• Human Genome Project, for searching and storing data
• Internet, for web searches and data transit
• Cryptography, to secure passwords + credit card data
• Optimization problems in industry

Many (even most) algorithms have practical implications.

Algorithms as a Technology