# Algorithms

## Introduction:

The following pages introduce the topic of algorithms by discussing the characteristics of a good algorithm and comparing several sorting algorithms to illustrate algorithm efficiency and algorithm analysis. Each section includes a set of review questions which test the important concepts from the section and provide practice problems. After reading each section, you should work the review questions before proceeding to the next lesson. Use the navigation bar at the top of this page to view the lessons and access the review questions. Each lesson page has a link on the navigation bar which will take you to the review questions for that lesson.

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.

### Directions to John's House

From the Quik Mart, you should follow Saddle road for four miles until you reach a stoplight. Then make a left-hand turn at the stop light. Now you will be on Hollow street. Continue driving on Hollow street for one mile. You should drive past four blocks until you reach the post office. Once you are at the post office, turn right onto Jackson road. Then stay on Jackson for about 10 miles. Eventually you will pass the Happy Meadow farm on your right. Just after Happy Meadow, you should turn left onto Brickland drive. My house is the first house on your left.

### 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 are algorithms, 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. For example, once you have the directions to John's house, you do not need to look at a map to decide where to make the next turn. The intelligence needed to find the correct route is contained in the algorithm. All you have to do is follow the directions. 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:

• Write some simple algorithms
• Sort numbers using three basic sorting algorithms
• Compare the sorting algorithms for efficiency.