Algorithms

Section 1: How to write algorithms

The programmer analyzes the problem and develops a general solution called an algorithm.

• Understanding and analysis of a problem requires a great deal of time.
• They are the heart of the programming processes.

Algorithm – A step-by-step procedure for solving a problem in a finite amount of time.

We use algorithms every day.

• They are simply a verbal or written description of logical sequences of actions.
• Cooking recipes, laundry detergent instructions, and refrigerator defrosting instructions are examples of written algorithms.

When we start our car, we go through a step-by-step procedure. The algorithm might look something like this:

1. Insert key.
2. Make sure transmission is in Park (or Neutral).
3. Depress the gas pedal.
4. Turn the key to the "start" position.
5. If the engine starts within 6 seconds, release the key to the "ignition" position.
6. If the engine doesn't start in 6 seconds, wait 10 seconds and repeat steps 3 through 6 (but not more than 5 times).
7. If the car doesn't start, call the garage.

Without the phrase "but not more than 5 times" in step 6 it would be possible to be stuck trying to start our car forever.

• Why? Because, if something is wrong with the car, repeating steps 3 through 6 over and over again may not start it.
• That never-ending situation is known as an infinite loop.
• So, if the phrase "but not more than 5 times" is left out of step 6, then our algorithm does not fit our definition.
• An algorithm must terminate in a finite amount of time for any possible conditions.

The programmer might need an algorithm to determine an employee's wages for the week, reflecting what would be done by hand.

1. Look up employee's pay rate.
2. Determine the # of hours worked during the week.
3. If the # of hours worked is less than or equal to 40.0, multiply the # of hours by the payrate to get regular wages.
4. If the # of hours is greater than 40.0, multiply the pay rate by 40.0 to get regular wages and multiply one and a half times the payrate by the difference between the # of hours worked and 40.0 to get overtime wages.
5. Add regular wages to overtime wages (if any) to get total wages for the week.

Although we work with algorithms all the time, most of our experience with them is in the context of following them.

• We follow a recipe, play a game, assemble a toy, take medicine.
• We are all taught how to follow directions, i.e., execute an algorithm.

In the problem-solving phase of computer-programming you will be designing algorithms, not following them.

• You will be given a problem and asked to devise the algorithm, to design the set of steps to be carried out in order to solve the problem.
• Actually, we do this kind of problem solving all the time at a subconscious level.
• We don't write down our solutions, however, we just execute them.

Section 2: Strategies

In learning to program you will have to make conscious some of your underlying problem-solving strategies in order to apply them to programming problems.

Let's look at some of these strategies we all use every day.

1. Ask Questions

   If you are given a task verbally, you ask questions until what you are to do is clear.

   • You ask when, why, where until your task is completely specified.
   • If your instructions are written, you might put question marks in the margin, underline a word, group of words or a sentence, or in some other way indicate that the task is not clear.
   • Perhaps your questions will be answered by a later paragraph, or you might have to discuss them with the person giving you the task.
   • If the task is one you set for yourself, this sort of questioning might not be verbal, but instead takes place on the subconscious level.

   Some typical questions you will be asking in the programming context are as follows:

   • What am I given to work with, i.e., what is my data?
   • What does the data look like?
   • How much data is there?
   • How will I know when I have processed all the data?
   • What must my output look like?
   • How many times is the process I am doing to be repeated?
   • What special error conditions might come up?
2. Look for Things that are Familiar

   We should never reinvent the wheel.

   • If a solution exists, use it.
   • If we have solved the same or a similar problem before, we just repeat the successful solution.
   • We don't consciously think, "I have seen this before, and I know what to do," we just do it.
   • Humans are good at recognizing similar situations.
   • We don't have to learn how to go to the store to buy milk, then to buy eggs, then to buy candy; we know that going to the store will be the same, and only what is bought is different.

   In computing you will see certain problems again and again in different guises.

   • A good programmer will immediately see a subtask that has been solved before and plug in the solution.
   • For example, finding the daily high and low temperature is exactly the same problem as finding the highest and lowest grade on a test; you want the largest and smallest numbers among a set of numbers.
3. Divide and Conquer

   We constantly break up a large problem into smaller units that we can handle.

   • The task of cleaning the house or apartment may seem overwhelming.
   • The task composed of cleaning the living room, the dining room, the kitchen, the bedrooms, and the bathrooms seems more manageable.
   • The same principle applies to programming.
   • We break up a large problem into smaller pieces that we can solve individually.

Section 3: Example

Let's apply these strategies (called heuristics) to a specific problem.

Problem How can I get to the party?

Questions

• Where is the party?
• Where am I coming from?
• What is the weather like (or likely to be like)?
• Will I be walking? Driving a car? Taking a bus?

Once these questions have been answered, you can begin to design your algorithm.

If it is raining, your car is in the shop and the buses have stopped, your best solution (algorithm) might be to call a taxi and give the driver the address.

If you look at a map and see that where you are going is six blocks west of the building where you work,

• the first part of your algorithm might be to repeat what you do each morning to get to work (providing you are leaving from home).
• The next part would be to turn west and go six blocks.
• If you have trouble remembering how many blocks you have walked, you might take a pencil and make a hash mark on a piece of paper each time you cross a street.

Though hash marking might be stretching the human algorithm a little too much, this is a technique you will use frequently in your programs.

• If you wish to repeat a process 10 times, you will have to write the instructions to count each time you do the process and check to see when your count reaches 10.

If you wanted to write a set of directions for other people, some of whom would be leaving from one place and some from another, you would have to have two sets of instructions prefaced by a question.

• If you are coming from place A, follow the first set of directions; otherwise follow the second set of directions.

Coming up with a step-by-step procedure for solving a particular problem is not always cut and dried.

• In fact, it is usually a trial-and-error process requiring several attempts and refinements.
• Each attempt is tested to see if it truly solves the problem.
• If it does, fine; if it doesn't, we try again.

When designing algorithms for computer programs it is important to keep in mind that the computer manipulates data – that information that we have reduced to symbolic form.

• We have looked at some algorithms that require physical actions by a human being.
• These algorithms are not suitable for use on a computer, because typically human involvement is limited to interacting with a user interface.
• Our primary concern, then, is how the computer can transform, manipulate, calculate or process the input data to produce the desired output or results.
• We can analyze the content (what it is composed of) and the form (what the order or pattern is) of the input data as well as the required content and form of the output to help us develop an algorithm to process the data.

Section 4: Another Example

The following algorithm parallels what is done by hand to compute the wages for each employee in a company and the total wages for the company. Here is the form:

Here is the algorithm:

Enter Button Event

1. Read the employee number from the text box labeled Employee #.
2. Read the pay rate from the text box labeled Pay Rate.
3. Read the hours worked from the text box labeled Hours Worked.
4. If the hours worked is greater than 40.0, then wages = ((40.0 x pay rate) + (hours worked - 40.0) x 1.5 x pay rate); otherwise, wages = hours worked x pay rate.
5. Add the employee's wages to the total payroll.
6. Write the total payroll on the form.

Reset Button Event

1. Clear all form fields.

This algorithm for the enter button event parallels how the payroll is figured by hand.

• The algorithm for doing something by hand can very often be used with little or no modification as our general solution.
• Just keep in mind the things a computer can do.
• When writing an algorithm for a program, you know in the back of your mind the allowable instructions in a programming language.
• This awareness lets you avoid designing an algorithm that would be difficult or impossible to code.