Algorithm

Student: Tell me about algorithms. Why are they useful?

Mentor: An algorithm is a detailed description of the actions you need to do if you want to accomplish some task. Algorithms are named for an Iranian mathematician, Al-Khawarizmi, who lived early in the 9th century, and among other things, wrote a book on arithmetic. And don't laugh about writing books about arithmetic. At that time, a lot of people were learning to use Arabic numerals instead of Roman numerals! So they needed detailed instructions on things like adding 25 plus 143. Can someone instruct me on how to add 25 and 143?

Student: First write the numbers on the board and draw a line under them.

Mentor: Can I write them any way I want to, such as with the 2 in the 25 over the 1 in the 143?

Student: No, write them with the right-most digits on top of one another. That makes it easy to start at the one's column and add them. So 5+3 is 8. Put the 8 under the line under the 3. Then you add the 2 and the 4, to get 6, and put that under the 4. Finally, nothing plus 1 is 1, put that under the 1, so the final answer is 168.

Mentor: Good, but how did I know that 5+3 is 8?

Student: Well, many of us know our addition tables, but if you didn't know your addition tables, you could count three past 5, as in 5, 6, 7, 8.

Mentor: Excellent! Does your method work for any pair of numbers? What if I want to add 79 and 46?

Student: Then you have to carry. When you add 9 and 6, you get 15, and you can only put one digit in the space under the 6. I can start to see that writing down all the steps to add two numbers could get complicated.

Mentor: It is complicated. But if you need to teach someone or want to program a computer, you need to tell them the algorithm. That is, you want to:

• Break the process up into steps that your student or your computer needs to do
• Include enough details (do you need to tell them how to add 3+5?)
• Get the steps in the right order (don't start adding at the left!)
• Tell them when they have to do something different (when do they need to carry?)
• Tell them when they can stop (you don't want them putting a string of 0's in front of the answer!)

Student: Is there always only one algorithm to solve a problem?

Mentor: Generally there are lots of possible algorithms. Sometimes different algorithms even give different answers. How could you estimate 23% of 48?

Student 1: I can change 23% to a decimal, and round 0.23 to 0.2. Then I say that 48 is close to 50 and 50 times 0.2 is 10. So my estimate is 10.

Student 2: But 23% is close to 25%, which is 1/4. A quarter of 48 is 12, so my estimate is 12.

Mentor: Both are good algorithms. One says to treat 23% as a decimal and the other says to make it into a fraction. Since the correct answer is 11.04, both are pretty accurate. Both were simpler than multiplying 0.23 by 48.

Some ways one algorithm may be better than another are:

• One gives more accurate answers
• One takes more effort to do, on the average
• One takes about the same amount of effort on the average, but sometimes takes FOREVER to find the right answer.

Student: So the estimating algorithm is faster but less accurate than the multiplication algorithm?

Mentor: Right.