Algorithms

From Computing Concepts
Jump to: navigation, search

Chapter Overview

An algorithm is a well-ordered, unambiguous, effectively computable set of operations that, when executed, returns a result in a finite amount of time. An effectively computable operation means that a computing device can execute it (e.g. it works with binary data).

A cooking recipe is similar to an algorithm. The steps of a recipe are well-ordered: for example, a recipe might specify mixing the cake batter before baking. A recipe is only effective if the operations are ones that the cook can perform - which is equivalent to algorithm operations needing to be effectively computable. For example, if the recipe called for unscrambling eggs, it would be useless because that operation cannot be done. If a recipe required the cook to "mix forever" it would be useless because it would not be done in a finite amount of time; instead recipes often say "mix for X minutes".

An example of a computer algorithm is the set of operations a computer program uses to find the largest item in a list. An example of that algorithm written is pseudo code is:

Pseudo code.png

Building Blocks

Sequencing, selection, and iteration are building blocks of algorithms. Sequencing is the application of each step of an algorithm in the order in which the statements are given. Selection uses a Boolean condition to determine which of two parts of an algorithm is used. Iteration is the repetition of a part of an algorithm until a condition is met or for a specified number of times.

Algorithms can be combined to make new algorithms. Using existing correct algorithms as building blocks for constructing a new algorithm helps ensure the new algorithm is correct. Knowledge of standard algorithms, such as searching and sorting algorithms, can help in constructing new algorithms.

Different algorithms can be developed to solve the same problem. Algorithms that solve the same problem can have different efficiencies. For example, a recipe to make a cake from a box results in a faster creation of the cake than a recipe to create a cake from scratch. Both yield cakes, but one is faster than the other.

Languages to express algorithms include natural language, pseudo code, and visual and textual programming languages. Natural language and pseudo code describe algorithms so that humans can understand them. Algorithms described in programming languages can be executed on a computer. Different languages are better suited for expressing different algorithms. Some programming languages are designed for specific domains and are better for expressing algorithms in those domains. For instance, the SQL language is good for expressing queries to databases, but not for implementing games.

The language used to express an algorithm can affect characteristics such as clarity or readability but not whether an algorithmic solution exists. For example, the High-Level Description and the (Quasi-)formal description are both algorithms to find the largest number in a set of numbers. Which one is easier to read?

High-level description:

  1. If there are no numbers in the set then there is no highest number.
  2. Assume the first number in the set is the largest number in the set.
  3. For each remaining number in the set: if this number is larger than the current largest number, consider this number to be the largest number in the set.
  4. When there are no numbers left in the set to iterate over, consider the current largest number to be the largest number of the set.

(Quasi-)formal description:

  Input: A list of numbers L.
  Output: The largest number in the list L.
  if L.size = 0 return null
  largestL[0]
  for each item in L, do
    if item > largest, then
      largestitem
  return largest 

Every algorithm can be constructed using only sequencing, selection, and iteration. Nearly all-programming languages are equivalent in terms of being able to express any algorithm. Clarity and readability are important considerations when expressing an algorithm in a language.

Solving Problems

Algorithms can solve many but not all problems. Many problems can be solved in a reasonable time. Reasonable time means that as the input size grows, the number of steps the algorithm takes is proportional to the square (or cube, fourth power, fifth power, etc.) of the size of the input. Some problems cannot be solved in a reasonable time, even for small input sizes. Some problems can be solved but cannot be solved in a reasonable time. In these cases, heuristic approaches may be helpful to find solutions in reasonable time.

A heuristic is a technique that may allow us to find an approximate solution when typical methods fail to find an exact solution. Heuristics may be helpful finding an approximate solution more quickly when exact methods are too slow. Some optimization problems such as “find the best” or “find the smallest” cannot be solved in a reasonable time, but approximations to the optimal solution can.

Un-decidable Problems

Some problems cannot be solved using any algorithm. An un-decidable problem may have instances that have an algorithmic solution, but there is no algorithmic solution that solves all instances of the problem. A decidable problem is one in which an algorithm can be constructed to answer 'yes' or 'no' for all inputs, such as "is the number even?" An un-decidable problem is one in which no algorithm can be constructed that always leads to a correct yes-or-no answer.

Efficiency

Determining an algorithm’s efficiency is done by reasoning formally or mathematically about the algorithm. Implementing the algorithm and running it on different inputs do empirical analysis of an algorithm. The correctness of an algorithm is determined by reasoning formally or mathematically about the algorithm, not by testing an implementation of the algorithm. Different correct algorithms for the same problem can have different efficiencies. Sometimes more efficient algorithms are more complex. Finding an efficient algorithm for a problem can help solve larger instances of the problem. Efficiency includes both execution time and memory usage. Linear search can be used when searching for an item in any list but binary search, which has better average case performance, can only be used when the list is sorted.

References

Parts of this page are based on information from: Wikipedia: The Free Encyclopedia