Consider the following three examples. What do they all have in common?
Chocolate Cream Pie :
(1) Heat milk, marshmallows and chocolate in 3-quart saucepan over low heat, stirring constantly, until chocolate and marshmallows are melted and blended. Refrigerate about 20 minutes, stirring occasionally until mixture mounds slightly when dropped from a spoon.
(2) Beat whipping cream in chilled small bowl with electric mixer on high speed until soft peaks form. Fold chocolate mixture into whipped cream. Pour into pie shell. Refrigerate uncovered about 8 hours or until set. Garnish with milk chocolate curls and whipped cream.
How to change your motor oil
(1) Place the oil pan underneath the oil plug of your car.
(2) Unscrew the oil plug.
(3) Drain oil.
(4) Replace the oil plug.
(5) Remove the oil cap from the engine.
(6) Pour in 4 quarts of oil.
(7) Replace the oil cap.
Each of these examples is algorithm, a set of instructions for solving a problem. Once we have created an algorithm, we no longer need to think about the principles on which the algorithm is based. This means that algorithms are a way of capturing intelligence and sharing it with others. Once you have encoded the necessary intelligence to solve a problem in an algorithm, many people can use your algorithm without needing to become experts in a particular field.
Algorithms are especially important to computers because computers are really general purpose machines for solving problems. But in order for a computer to be useful, we must give it a problem to solve and a technique for solving the problem. Through the use of algorithms, we can make computers "intelligent" by programming them with various algorithms to solve problems. Because of their speed and accuracy, computers are well-suited for solving tedious problems such as searching for a name in a large telephone directory or adding a long column of numbers.
However, the usefulness of computers as problem solving machines is limited because the solutions to some problems cannot be stated in an algorithm.
Much of the study of computer science is dedicated to discovering efficient algorithms and representing them so that they can be understood by computers.
During our study of algorithms, we will discuss what defines an algorithm, how to represent algorithms, and what makes algorithms efficient. Along the way we will illustrate these concepts by introducing several algorithms for sorting. By the end of our study, you should be able to do the following:
1 Write some simple algorithms,
2 Sort numbers using three basic sorting algorithms, and
3 Compare the sorting algorithms for efficiency.
In the introduction, we gave an informal definition of an algorithm as "a set of instructions for solving a problem" and we illustrated this definition with a recipe, and instructions for changing the oil in a car engine. You also created your own algorithm for putting letters and numbers in order. While these simple algorithms are fine for us, they are much too ambiguous for a computer.
In order for an algorithm to be applicable to a computer, it must have certain characteristics. We will specify these characteristics in our formal definition of an algorithm.
An algorithm is a well-ordered collection of unambiguous and effectively computable operations that when executed produces a result and halts in a finite
amount of time [Schneider and Gersting 1995]. With this definition, we can identify five important characteristics of algorithms :
(1) Algorithms are well-ordered.
(2) Algorithms have unambiguous operations.
(3) Algorithms have effectively computable operations.
(4) Algorithms produce a result.
(5) Algorithms halt in a finite amount of time.
When writing algorithms, we have several choices of how we will specify the operations in our algorithm. One option is to write the algorithm using plain English. Although plain English may seem like a good way to write an algorithm, it has some problems that make it a poor choice. First, plain English is too wordy.
When we write in plain English, we must include many words that contribute to correct grammar or style but do nothing to help communicate the algorithm. Second, plain English is too ambiguous. Often an English sentence can be interpreted in many different ways. Remember that our definition of an algorithm requires that each operation be unambiguous.
Another option for writing algorithms is using programming languages. These languages are collections of primitives (basic operations) that a computer understands. While programming languages avoid the problems of being wordy
and ambiguous, they have some other disadvantages that make them undesirable for writing algorithms. Consider the following lines of code from the programming language C++.
a = 1;
b = 0;
while (a <= 10)
b = b + a;
cout << b;
This algorithm sums the numbers from 1 to 10 and displays the answer on the computer screen. However, without some special knowledge of the C++ programming language, it would be difficult for you to know what this algorithm does. Using a programming language to specify algorithms means learning special syntax and symbols that are not part of Standard English.
For example, in the code above, it is not very obvious what the symbol "++" or the symbol "<<" does. When we write algorithms, we would rather not worry about the details of a particular programming language. What we would really like to do is combine the familiarity of plain English with the structure and order of programming languages.
A good compromise is structured English. This approach uses English to write operations, but groups operations by indenting and numbering lines. An example of this approach is the directions for changing motor oil in the introduction lesson. Each operation in the algorithm is written on a separate line so they are easily distinguished from each other. We can easily see the advantage of this organization by comparing the structured English algorithm with the plain English algorithm.
For the remainder of this study, we will write our algorithms using the structured English approach.