Click here to skip to main content.
Distance Learning Design Banner

Lesson Four: Algorithms

Overview

Before you proceed to programming computers, you need to prepare yourself by learning how to think about programming. At the heart of programming is the algorithm: a very carefully-expressed problem-solving strategy, usually in the form of a structured set of instructions. We say we "use" or "apply" an algorithm to solve the problem for which it was designed.

In everyday life, when we think of instructions, we mean instructions for other people (rather than a machine) to follow. We conveniently make many unstated assumptions, and get away with being ambiguous. Unlike instructions for people, however, instructions for computers can leave no room for misinterpretation, so algorithms require an extreme level of precision. Here we will follow the guidelines discussed in Fluency with Information Technology, Chapter 10, "Algoritmic Thinking," to exercise our logical thinking on a wide variety of problems, ranging from everyday tasks to mathematical problems.

Objectives

This part of Lesson Four focuses on:

 Key Concepts
  • algorithm
  • input, output
  • degree of precision required in an algorithm
  • control flow
  • conditional
  • iteration

 Key Skills
  • writing an algorithm, given a properly specified problem statement
  • identifying examples of conditionals and iteration in algorithms

Required Resources

You won't need a computer. This section consists entirely of written exercises.

to top

Procedure

 Key Terms
  • algorithm, program
  • control flow
  • iteration, looping, loop condition

You will be writing algorithms for three different kinds of problems. Before we plunge into writing algorithms for common computing problems, we will work with problems that are probably more familiar to you.

  1. In Part 1, you will write algorithms for completing everyday tasks like doing laundry or making a sandwich.
  2. In Part 2, you will move on to special everyday tasks carefully chosen for their strong similarities to mathematical or computing problems. For example, locating a word's definition in a dictionary is an example of a "search problem," using computer science terminology. The CD-sorting example also falls into this category.
  3. In Part 3, you will work with problems that are explicitly mathematical or computational in nature: for example, finding the average of a large set of numbers. You will be instructed to choose one or two problems from each of these three groups and write an algorithm for each. For each algorithm you write, make sure to follow the following instructions.

Instructions for Writing Algorithms

For each problem, write a carefully-worded and structured set of instructions for solving the problem. Include the following sections, described in detail:

  • inputs or start state, including a list of required materials, if applicable (Note: This might seem obvious for physical tasks like preparing a sandwich. However, even for mathematical problems, you might want to note which quantities you want to track.);
  • outputs or end result(s); and
  • numbered steps.

Always keep conscious of the assumptions you are making by writing them down explicitly. You should adhere to the guidelines discussed in Chapter 10 of your textbook, and follow the format shown in the sample solution below.

Remember, there is no one right answer. Many different algorithms might be acceptable for each problem. Due to the flexibility of the English language, the same algorithm can often be expressed in more than one way. In addition, there is almost always more than one way to solve a problem. Solutions might differ in their complexity, the time they require, and other aspects, but they can all be valid algorithms for the problem.

Finally, both as you write and after you are finished, check your algorithm to make sure it satisfies all of the properties discussed at the beginning of Chapter 10. Questions you can ask yourself to check your algorithm include the following:

  1. Inputs specified—do you precisely describe all of the data or materials needed for the algorithm?
  2. Outputs specified—do you precisely describe the results of your algorithm? Your outputs description should clearly state what the algorithm is supposed to do, and solve the problem for which it is designed.
  3. Definiteness—is each detail essential to the algorithm's correctness? Does it add important information not evident from what you have already written? Include the detail only if you answer "yes" to these questions.
  4. Effectiveness—are the required resources (whether they are information or the ability to do certain things) realistic and reasonable? For instance, an algorithm for converting a temperature from Fahrenheit to Celsius degrees that relies on looking up the temperature in a Fahrenheit-Celsius conversion table is hardly interesting or useful.
  5. Finiteness— Are you sure the algorithm actually completes? For instance, one algorithm for finding a specific playing card in a deck is to repeat the following:›
    • Shuffle the deck and check the top card;
    • Shuffle the deck and check the top card;
    • Shuffle the deck and check the top card;
    • And so on . . .

    Strictly speaking, the card you are looking for might never end up at the top of the deck, no matter how many times you reshuffle. That would be pretty rotten luck, but it is possible. In contrast, checking the whole deck one card at a time, while time-consuming, is an algorithm guaranteed to finish. At worst, your card would end up being the fifty-second one you check.

to top

Example

Notice that each problem statement in these exercises is very carefully stated, with as many details and as few implicit assumptions as possible. This is no accident. It is only reasonable that a detailed and precise algorithm requires an equally carefully stated problem.

Problem

Given a VCR, TV, and videotape of twelve 30-minute episodes of your favorite television show, find a specified episode, and cue the tape to the start of the episode. For instance, suppose you have already seen all but one of the episodes, but you are not sure where that one is on the tape. Your objective is to find this episode on the tape. Assume that the TV and VCR are both on, and that the tape is in the VCR, cued to an unknown location (that is, not necessarily rewound).

Example Algorithm

  • Start State or Inputs: videotape of twelve 30-minute episodes, VCR, and TV, with assumptions as stated in problem above, and your ability to recognize one specific episode;
  • End Result or Outputs: videotape cued to beginning of specified episode
  • Assumptions:
    • the VCR has a tape counter that shows the tape's position in hours and minutes;
    • episodes begin at 30 minute multiples; that is, the first episode starts at time 0:00, the second at 0:30, the third at 1:00, and so on;
    • there is no other video recorded on the tape between episodes.
  • Procedure:
    1. Rewind tape to start.
    2. Reset tape counter.
    3. Play tape for a few minutes to check whether the episode is the one you are looking for. If so, proceed to Step 5; otherwise, proceed to Step 4.
    4. Stop play, and fast forward the tape. Watch the counter for the next 30 minute multiple, and press stop when the tape reaches that point, which should be the start of the next episode on the tape. For example, if you stopped the tape at 2:04, two hours, four minutes, fast forward until the counter reads 2:30. Go to Step 3.
    5. Stop play, and rewind to the previous 30 minute multiple using the tape counter. For example, if you recognize the episode you are looking for and the counter reads 3:32 (three hours, 32 minutes), rewind to 3:30.
to top

Part I— Algorithms for Everyday Problems

Important Advice:› Do not assume problems in this part will be easy just because the procedures for these tasks might be second nature to you. In fact, the more familiar you are with a task, the more likely it is you will make implicit assumptions and skip details in your algorithm.

Choose one of the problems below and write an algorithm to solve it. Assume a reasonably-equipped kitchen as the context.

  • Prepare a bowl of cold cereal—you may choose to include fruit or other ingredients beyond cereal and milk, but make sure to state them explicitly. Assume there is a carton of milk in the refrigerator.
  • Prepare a sandwich—be sure to state what kind of sandwich you are making and what ingredients and utensils are required. Again, assume all required ingredients are in the kitchen, refrigerated if needed.
  • Prepare a cup of tea using a tea bag—you may describe adding cream, sugar, lemon, or honey, but mention these ingredients in your writeup.

Each of the following everyday problems involves repeating some steps in the procedure, just as Step 4 in the videotape example can be repeated. Choose one and write an algorithm to solve it:

  • Given a pile of pens, find and discard the ones that do not write any more.
  • Suppose you are told your favorite movie is on television right now, but you are not sure which channel it is on. Without the use of a program guide (that is, without using things like TV Guide or the newspaper program listings), find the channel broadcasting the movie. Assume you could recognize any part of the movie if you saw it.
  • Brush your teeth.
  • Wash and dry a load of laundry using coin-operated washing machine and dryer.
to top

Part 2—Algorithms for Everyday Computational Problems

The problems in this section are real-life versions of computational problems. Choose one of the following problems:

  • Given two words, determine which would come first in alphabetical order. Do not use a dictionary or other reference book.
  • Given a bag full of cherries, determine whether you could split them evenly among seven people so each person has the same number of cherries and none are left over. The result is a yes or no answer.
  • Given a restaurant check subtotal, before tax, and total, after tax, calculate how much you should leave for a 15 percent tip.
  • Given fifty apples and a two-pan balance that can determine whether two items have the same weight, determine which two, if any, have the same weight (that is their weight is close enough to equal that the balance measures them as being equal).
to top

Part 3—Algorithms for Computational Problems

Problems in this section are obviously computational, involving computing mathematically interesting results. They are fundamentally different from the problems in the previous two parts of this lab, in that they involve no physical processes. That is, these problems involve manipulating numbers rather than physical objects like foods, pens, or laundry detergent. Choose one of the following problems:

  • Given a set of 20 numbers, compute the average of the numbers.
  • Given a set of 100 numbers, find the largest and smallest numbers in the set.
  • Find the kth power of two without using a calculator.
to top

Recognizing Control Flow Patterns

Some algorithms are very simple, and applying them just involves proceeding from one step to the next in sequential execution. We have already seen examples of algorithms, however, which involve skipping ahead to a later step or repeating an earlier step, depending on certain conditions. Control flow is the programming term used to describe the order in which the steps are executed, and we will discuss two common ways control flow diverges from simple, sequential execution. In the self-study questions at the end of this section, you are asked to examine the algorithms you wrote and identify at least one example of each of these control flow patterns

Conditionals

The keyword is "if."› A conditional , also known as a branch, is when control flow reaches a point where it can proceed to one of two or more alternatives. The condition is what determines the next step the computer proceeds to. For example, to round a number off to its nearest integer, you first need to check the following condition: whether the fractional part is less than 0.5. If so, the result is just the integer part; otherwise, you add 1 to the integer part.

Use of the phrase structure if/then and instructions to skip ahead or back to other steps in an algorithm are hallmarks of the conditional.

Iteration›

Iteration is controlled repetition of one or more steps in an algorithm. Iteration is related to the conditional in that the number of times you do the repetition is usually controlled by a condition. Iteration is also called looping, and the condition is accordingly called the loop condition. The video-searching example algorithm has a loop in Steps 3 and 4, where the conditional in Step 3 that checks whether the episode is the one you are looking for determines whether you repeat Step 4's fast-forwarding. Understanding the concepts of control flow and its two standard patterns of the conditional and iteration will help you a great deal as you proceed to expressing algorithms in a programming language.

to top

Optional Additional Activities

The following activity is much more difficult than it sounds, and it should help you gain an appreciation for precise language and instructions. You will need to work with a friend for this activity. You will be an "instruction writer," and your friend will be a "builder."

  1. Using a building toy kit such as Tinker Toys, Legos, or Construx, build a simple structure using four to six parts. Do not show your friend this structure.
  2. Place the structure on a table and, without touching it, write a set of instructions for constructing it, starting from the individual parts, all separated. You are not allowed to draw diagrams or use anything other than English to describe the steps.
  3. Either find a set of parts identical to those used in the structure, or dismantle it. Make sure you remember it exactly with sketches, digital, or Polaroid photographs.

Provide your friend with the parts and the instructions you wrote and see if they can reproduce the structure from just your instructions. No coaching from you!›

Or, try more some of the problems in the previous parts of this lab.

to top

Self-Study Questions

These questions will help you determine if you have mastered important concepts. Review the required reading and procedures if you find gaps in your understanding.

Go on to Lesson Four, Part B.

to top
©2003, University of Washington. All rights reserved.
No part of this publication may be reproduced in any form or by any means without permission in writing from the publisher.