Introduction to Algorithms and Programming
Introduction to algorithms
Algorithms for people
An algorithm is a list of steps which generates the correct output for a given set of input. Algorithms use similar steps to solve similar problems.
In business, a strategy could be an algorithm for accomplishing an objective.
In cooking, a recipe is an algorithm for making a specific culinary dish.
On the Internet, Amazon uses algorithms to determine which items to display on its website and Google use algorithms to find results of queries.
Algorithms shape our world
Kevin Slavin provides some excellent examples of algorithms that are found all around us. He raises an important question about the potential risks of losing control once algorithms have been implemented.
Algorithms for computers
The
problem specifications determine the
pre-conditions and
post-conditions of a program.
An
algorithm is a list of steps which generates the correct output for a given set of input and the
steps are suitable for computer implementation.
Algorithms depend on abstractions
Abstractions are required in order to
represent real world problems in a format that can be solved by algorithms and computers.
Test plans are linked to algorithms
Sources of algorithms
- Prior knowledge and experience
- Experience with one activity often can be applied to a different activity.
- Experimentation
- Systematic experimentation involves a plan, careful note taking, data collection and comparative analysis.
- Guessing is not the same as systematic experimentation.
- Research
- Learning from knowledge and experience of other people.
Common types of algorithms
- Deterministic algorithms
- Algorithms that use a series of similar steps that generally occur in the same order.
- For example, Ken Perlin won an Oscar Technical Achievement Award in 1997 "for the development of Perlin Noise, a technique used to produce natural appearing textures on computer generated surfaces for motion picture visual effects". His work is now widely used in the computer graphics industry.
- Heuristic algorithms
- Algorithms that use a series of steps that may not always occur in the same order.
- For example, how to find a job, find a spouse or obtain a first classification for your degree.
- Emergent algorithms
- A set of rules applied at a small scale that generates complexity at a larger scale (name is attributed to the English psychologist, George Henry Lewes)
- For example, the flock of bird algorithm published by Craig Reynolds in 1987 has 3 rules:
- Separation – steer to avoid your immediate neighbors
- Alignment – steer to align with the average heading of your immediate neighbors.
- Cohesion – steer toward the average position of your immediate neighbors
- Recursive algorithms
- Recursion is an algorithm whose definition uses smaller instances of itself.
- Recursive algorithms are one of the most common types of algorithms in the field of computing.