One of the most important concepts in computing is the concept of an algorithm. An algorithm is a detailed sequence of steps that describes how to solve a problem or accomplish some task. In order to fully understand this definition, it is important to distinguish between a problem, an algorithm for solving that problem, and the process used to design the algorithm.
We all have a good intuitive feel for what a problem is – it is “something” that we want an answer to. More formally, a problem statement generally consists of: (1) a description of the conditions at the start of the problem solving process, also known as the input; and (2) a description of the valid solution states, or desired output. Often these aspects of the problem are stated explicitly, such as: “the input will be three integer numbers and the output will be the sum of those numbers.” At other times they are stated implicitly, as in: “determine the amount of income tax you owe this year,” where the inputs are implied to be your income, tax rate, deductible expenses, and other such things.
An algorithm is essentially a description of how to solve a problem. Computer programs are just algorithms that are written in a language that can be executed by a computer. It is important to realize that when a computer executes, or runs, a program, it does not really “understand” the problem it is solving. Instead, the computer is blindly following a sequence of instructions. In general, computers do not design algorithms, human beings do. The reason for this is that designing a good algorithm requires creativity and imagination (in addition to a lot of hard work).
One way to think about the difference between designing an algorithm (which humans do) and executing an algorithm (which computers do) is to think about the differences between performing a piece of music and composing that piece. Imagine a composition in the form of sheet music; say Beethoven’s Piano Sonata No. 14 “Moonlight.” The notes and other symbols printed on the page are instructions that describe how to play that piece. These instructions are an algorithm that any competent pianist can follow (execute on a piano) to produce the music. The job of the performer can be thought of as quite mechanical, requiring no imagination or creativity[1]. In fact, modern synthesizers can accept a musical score and perform it flawlessly.
The job of the composer is very different. He or she imagines and designs the piece of music and ultimately encodes it as a series of symbols on paper. Clearly, this task requires a set of skills, and level of creativity, very different from the performer. In this analogy, the performer’s role is similar to that of the computer – simply executing the algorithm or playing the music, while the composer’s role is similar to that of a computer programmer – designing the instructions that can be followed to create the music.
This chapter is intended to give you a better understanding of algorithms and how humans develop them. Its primary goal is to help you see that there are often many ways to solve a problem and that these ways can differ greatly in efficiency.
presents a simple problem and uses it to develop the concepts of “algorithm” and “algorithm efficiency.” and describe two common and useful tasks, searching and sorting, and present a number of different procedures (algorithms) for solving them. The efficiency of each of the algorithms is characterized in order to determine the “best” way to accomplish these two tasks.
Footnotes
[1] Of course, what separates an exceptional musician from one who is simply adequate is the ability to go beyond a purely mechanical reproduction of the notes on the page.