Section 2.5
Algorithm Development
PROGRAMMING IS DIFFICULT (like many activities that are useful and worthwhile -- and like most of those activities, it can also be rewarding and a lot of fun). When you write a program, you have to tell the computer every small detail of what to do. And you have to get everything exactly right, since the computer will blindly follow your program exactly as written. How, then, do people write any but the most simple programs? It's not a big mystery, actually. It's a matter of learning to think in the right way.
A program is an expression of an idea. A programmer starts with a general idea of a task for the computer to perform. Presumably, the programmer has some idea of how to perform the task by hand, at least in general outline. The problem is to flesh out that outline. What is needed is a complete, unambiguous, step-by-step procedure for carrying out the task. Such a procedure is called an "algorithm." (Technically, an algorithm is an unambiguous, step-by-step procedure that terminates after a finite number of steps; we don't want to count procedures that go on forever.) An algorithm is not the same as a program. A program is written in some particular programming language. An algorithm is more like the idea behind the program, but it's the idea of the steps the program will take to perform its task, not just the idea of the task itself. The steps of the algorithm don't have to be filled in in complete detail, as long as its clear that carrying out the steps will accomplish the assigned task. An algorithm can be expressed in any language, including English, as long as it is unambiguous.
So, where do algorithms come from? Usually, they have to be developed, often with a lot of thought and hard work. Skill at algorithm development is something that comes with practice, but there are techniques and guidelines that can help. I'll talk here about some techniques and guidelines that are relevant to "programming in the small," and I also will return to the subject several times in later chapters.
When programming in the small, you have a few basics to work with: variables, assignment statements, and input-output routines. You might also have some subroutines, objects, or other building blocks that have already been written by you or someone else. (Input/output routines fall into this class, actually.) You can build sequences of these basic instructions, and you can also combine them into more complex control structures such as while loops and if statements. And you have a task in mind that you want the computer to perform.
One way to proceed is to write a description of the task, and take that description as an outline of the algorithm you want to develop. Then you can refine and elaborate that description, gradually adding steps and detail, until you have a complete algorithm that can be translated directly into programming language. This method is called stepwise refinement, and it is a type of top-down design. As you proceed through the stages of stepwise refinement, you can write out descriptions of your algorithm in pseudocode -- informal instructions that imitate the structure of programming languages without the complete detail and perfect syntax of actual program code.
As an example, let's see how one might develop the program from the previous section, which computes the value of an investment over five years. The task that you want the program to perform is: "Compute and display the value of an investment for each of the next five years." You might then write -- or at least think -- that this can be expanded as:
Compute the value after 1 year; Display the value; Compute the value after 2 years; Display the value; Compute the value after 3 years; Display the value; Compute the value after 4 years; Display the value; Compute the value after 5 years; Display the value;This is correct, but rather repetitive. And seeing that repetition, you might notice an opportunity to use a loop. A loop would take less typing. More important, it would be more general: Essentially the same loop will work no matter how many years you want to process. So, you might rewrite the above sequence of steps as:
while there are more years to process: Compute the value after the next year; Display the value;Now, for a computer, we'll have to be more explicit about how to "Compute the value after the next year" and what it means to say "there are more years to process." To proceed, you have to know how to do the computation yourself. (Maybe you need to ask your boss or professor for clarification?) Let's say you know that the value is computed by adding some interest to the previous value. Then we can refine our algorithm to:
while there are more years to process: Compute the interest; Add the interest to the value; Display the value;As for testing whether there are more years to process, the only way that we can do that is by counting the years ourselves. This displays a very common pattern, and you should expect to use something similar in a lot of programs: We have to start with zero years, add one each time we process a year, and stop when we reach the desired number of years:
years = 0; while years < 5: years = years + 1; Compute the interest; Add the interest to the value; Display the value;Well, this is fine, but there is a problem: We can't compute the interest unless we know the interest rate, and we can't compute the value of the investment in future years unless we know the value at the start. Where does this information come from? Are the interest rate and the initial value given as fixed values? Are they supposed to be typed in by the user when the program is run? Better go back to the boss or professor again -- or read your assignment more carefully! Let's say that the interest rate and the initial value of the investment are to be input by the user of the program. And also let's say that the interest is to be computed by multiplying the interest rate by the current value:
get the initial value from the user; get the interest rate from the user; years = 0; while years < 5: years = years + 1; Compute interest = value * interest rate; Add the interest to the value; Display the value;Finally, we are at the point where we can translate pretty directly into proper programming-language syntax. We still have to choose names for the variables, decide exactly what we want to say to the user, and so forth. Having done this, we could express our algorithm in Java as:
TextIO.put("Type initial investment: "); double principal = TextIO.getlnDouble(); TextIO.put("Type interest rate: "); double rate = TextIO.getlnDouble(); int years = 0; while (years < 5) { years = years + 1; double interest = principal * rate; principal = principal + interest; TextIO.putln(principal); }This still needs to be wrapped inside a complete program, it still needs to be commented, and it really needs to print out more information for the user. But it's essentially the same program as the one in the previous section.
One thing you should have noticed here is that my original specification of the problem -- "Compute and display the value of an investment for each of the next five years" -- was far from being complete. Before you start writing a program, you should make sure you have a complete specification of exactly what the program is supposed to do. In particular, you need to know what information the program is going to input and output and what computation it is going to perform. Here is what a reasonably complete specification of the problem might look like in this example:
"Write a program that will compute and display the value of an investment for each of the next five years. Each year, interest is added to the value. The interest is computed by multiplying the current value by a fixed interest rate. Assume that the initial value and the rate of interest are to be input by the user when the program is run."
Let's do another example, working this time with a program that you haven't already seen. The assignment here is an abstract mathematical problem that is one of my favorite programming exercises. This time, we'll start with a proper and complete specification:
"Given a positive integer, N, define the '3N+1' sequence starting from N as follows: If N is an even number, then divide N by two; but if N is odd, then multiply N by 3 and add 1. Continue to generate numbers in this way until N becomes equal to 1. For example, starting from N = 3, which is odd, we multiply by 3 and add 1, giving N = 3*3+1 = 10. Then, since N is even, we divide by 2, giving N = 10/2 = 5. We continue in this way, stopping when we reach 1, giving the complete sequence: 3, 10, 5, 16, 8, 4, 2, 1.
"Write a program that will read a positive integer from the user and will print out the 3N+1 sequence starting from that integer. The program should also count and print out the number of terms in the sequence."
A general outline of the algorithm for the program we want is:
Get a positive integer N from the user; Compute, print, and count each number in the sequence; Output the number of terms;The bulk of the program is in the second step. We'll need a loop, since we want to keep computing numbers until we get 1. So we can expand our pseudocode algorithm to:
Get a positive integer N from the user; while N is not 1: Compute N = next term; Output N; Count this term; Output the number of terms;In order to compute the next term, the computer must take different actions depending on whether N is even or odd. We need an if statement to decide between the two cases:
Get a positive integer N from the user; while N is not 1: if N is even: Compute N = N/2; else Compute N = 3 * N + 1; Output N; Count this term; Output the number of terms;We are almost there. The one problem that remains is counting. Counting means that you start with zero, and every time you have something to count, you add one. We need a variable to do the counting. (Again, this is a common pattern that you should expect to see over and over.) With the counter added, we get:
Get a positive integer N from the user; Let counter = 0; while N is not 1: if N is even: Compute N = N/2; else Compute N = 3 * N + 1; Output N; Add 1 to counter; Output the counter;We still have to worry about the very first step. How can we get a positive integer from the user? If we just read in a number, it's possible that the user might type in a negative number or zero. If you follow what happens when the value of N is negative or zero, you'll see that the program will go on forever, since the value of N will never become equal to 1. This is bad. In this case, the problem is probably no big deal, but in general you should try to write programs that are foolproof. One way to fix this is to keep reading in numbers until the user types in a positive number:
Ask user to input a positive number; Let N be the user's response; while N is not positive: Print an error message; Read another value for N; Let counter = 0; while N is not 1: if N is even: Compute N = N/2; else Compute N = 3 * N + 1; Output N; Add 1 to counter; Output the counter;Here is a Java program implementing this algorithm. It uses the operators <= to mean "is less than or equal to" and != to mean "is not equal to." To test whether N is even, it uses "N % 2 == 0". The expression N % 2 computes the remainder when N is divided by 2. We know N is even if this remainder is equal to 0. The operator == is used to test whether two numbers are equal. (I cover operators in more detail in Section 7.)
public class ThreeN { /* This program prints out a 3N+1 sequence starting from a positive integer specified by the user. It also counts the number of terms in the sequence, and prints out that number. */ public static void main(String[] args) { int N; // for computing terms in the sequence int counter; // for counting the terms TextIO.put("Starting point for sequence: "); N = TextIO.getlnInt(); while (N <= 0) { TextIO.put("The starting point must be positive. Please try again: "); N = TextIO.getlnInt(); } // At this point, we know that N > 0 counter = 0; while (N != 1) { if (N % 2 == 0) N = N / 2; else N = 3 * N + 1; TextIO.putln(N); counter = counter + 1; } TextIO.putln(); TextIO.put("There were "); TextIO.put(counter); TextIO.putln(" terms in the sequence."); } // end of main() } // end of class ThreeNAs usual, you can try this out in an applet that simulates the program. Try different starting values for N, including some negative values:
Two final notes on this program: First, you might have noticed that the first term of the sequence -- the value of N input by the user -- is not printed or counted by this program. Is this an error? It's hard to say. Was the specification of the program careful enough to decide? This is the type of thing that might send you back to the boss/professor for clarification. The problem can be fixed easily enough. Just replace the line "counter = 0" before the while loop with the two lines:
TextIO.putln(N); // print out initial term counter = 1; // and count itSecond, there is the question of why this problem is at all interesting. Well, it's interesting to mathematicians and computer scientists because of a simple question about the problem that they haven't been able to answer: Will the process of computing the 3N+1 sequence finish after a finite number of steps for all possible starting values of N? Although individual sequences are easy to compute, no one has been able to answer the general question. (To put this another way, no one knows whether the process of computing 3N+1 sequences can properly be called an algorithm, since algorithms are required to terminate after a finite number of steps!)
[ Next Section | Previous Section | Chapter Index | Main Index ]