2.3 How to Solve a Problem

With these remarks on the structure of simple Modula-2 programs, it is time to return to the theme of problem solving. This was discussed at the start of chapter one; here that general discussion will be applied specifically to the kinds of problem for which a computer-assisted solution is anticipated. During the course of the following discussion, a simple problem will be posed and a complete solution provided. This will culminate in a program that embodies the solution in a coded form.

Most problems appear insurmountable at first--that seems to be their very nature. Many students (and some teachers), on being presented with one, will scan it over lightly in an attempt to get the whole picture in their mind at once and then, after a few minutes, throw up their hands in despair and shout "I don't know where to start!" Worse still, they may make dozens of trips to the professor or teaching assistants, each time with the same poignant question: "What's the next step?"

Note, however, that the way problem solving was defined in section 1.1 presupposes that a problem is something that has a solution. That which has no solution is not a problem in the sense used in this text. Thus, the person faced with a problem is here assumed to be one who can solve it, given a suitable strategy or technique. The task is to find such a technique, then to employ the computer to implement it. That is, a computer programmer is a problem solver who uses a particular tool (the computer) as part of the solution process.

In section 1.3, eight goals for a problem solver were detailed. It is time to turn those goals into a specific strategy. Thus, though the step-by-step problem solving system that follows still has enough generality to be modified for other types of problem, it has been formulated here with the assumption that computer assistance will be employed in the final process.

2.3.1 Analysis

Goals:

Write Everything Down.

1. Have a clear grasp of the existing state of affairs.

2. Have a clear conception of the goal.

3. Formulate the problem clearly.

Strategic Step 1 Write the problem out.

This forces the would-be problem solver to slow down an overheated mind long enough to read the problem carefully instead of trying to absorb it as a whole by staring at entire paragraphs at once. If necessary, copy the whole thing word for word or highlight it in the book, or tap a pencil on each word while reading it. Before beginning to consider what the solution might be, one must know what the problem means--and that presupposes knowing what the words say.

Example problem:

Write a program that can raise a whole number (say 4) to a positive whole number power (say 6.)

Strategic Step 2 Ask whether a computer is appropriate.

There is no sense using a sledgehammer to crack a peanut or a chain saw to cut a toothpick. Likewise, there is no point in using a computer for simple additions or multiplications. They can be done mentally, or with a calculator, but it is a waste of both human and machine resources to write a computer program for such tasks. True, some of the examples in this book are trivial, but this is necessary to make teaching points simply. Students ought to remember that they have to walk before they can run. It will take a while to begin to realize the true power of the machine, and to write substantial programs to take advantage of that power.

Example problem suitability:

The sample problem posed above is well within the reach of a simple calculator, and is therefore of marginal suitability for computer solution. However, the solution does illustrate how a number of the programming ideas discussed in chapter one are actually implemented in Modula-2.

Still, some problems may be too general, or too easy to be appropriate for computer solution. On the other hand, they may be out of a machine's reach for other reasons, such as the requirement for some thinking process that is outside the domain of machines. Here are examples of the kind of problem that might not at this time be appropriate for computer solution.

1. How do we solve Canada's economic problems?

2. What is the aesthetic value of that painting?

3. Who will win the Stampeders vs. Lions game?

4. Who is right--the Evolutionists or the Creationists?

Partial answers might be obtainable for the first problem by computer analysis of available data (provided that the meaning of the words "economic" and "problem" can be agreed upon). Reference to some base of information also may give an answer to the second question, but only as a dollar value, and even then only if the painting had a previous sales history. The third question can be responded to in terms of probabilities based on an analysis of the past (perhaps computer-assisted) but cannot be answered as stated here. The fourth question is not answerable in any final sense that would be satisfying to all concerned, either via data analysis or the scientific method, since there is no evidence compelling enough to convince either side that its religious or philosophical beliefs are wrong. Each will continue to "keep the faith" regardless of the other's interpretation of the data, and neither is likely to experience a conversion to the other view as a result of any computerized analysis.

There is a third category of problem that may be inappropriate to tackle with the particular resources at hand. These are the questions that could be analyzed by a machine, but not, say by a personal computer, for it may be too slow, or lack a suitable notation, peripherals, or storage space. For instance, one cannot run Canada's income tax collection system or design aircraft frames on a personal computer. One may also find that certain computing notations lack some facilities needed to solve a particular problem efficiently. In this case, the programmer must learn how to work within a different programming environment in order to get the desired answers.

Lack of knowledge about what the computer can do to solve a problem constitutes a fourth difficulty in this category. Even this many years into the computer revolution, many people have a knowledge of computing limited to what they read in the gushy reviews typical of many trade magazines. They often believe in such ephemeral enthusiasms and rush out to buy the latest brand-name computer solution for their accounting, inventory, or information flow troubles. However, computerizing a badly organized business will not solve any of its existing problems; it will only ensure that they occur more rapidly, in greater numbers, and with more potential for harm. An already efficient operation can be improved with carefully chosen machines and software, but an inefficient one will only become worse with the addition of a computer.

Caveat computorae! To err is human. To really foul things up requires a computer.
Murphy's Law: It only takes a millisecond for everything to go wrong using a computer.

Strategic Step 3 Re-write the problem in your own words.

At this third stage, one is aiming for an understanding of what is being asked. This is the stage where one begins to go from the general to specifics. If one's conception of what is known and what is required for the solution are vague, there is no point in carrying on. Use headings and point form, and concentrate on the given information and the desired result. Try to be precise. Write out any formulas that are stated or implied--in the latter case, it may be necessary to look something up.

Example problem restatement:

Given: Two whole numbers, one the base and the other the exponent

To Do: Compute baseexponent

Desired Result: print the result

Formula: none. Use a repeated multiplication

2.3.2 Planning and Refining a Solution

Goals: 1. Consider related tasks.

2. Break the main task into sub-tasks.

Strategic Step 4 Re-Use Previous Work Where Possible

If you have written any previous programs in Modula-2, there will likely be parts that one can copy into the new solution in order to avoid typing them again. These should be noted now. If this is a first program in Modula-2, one might think that there is nothing to be re-used. However, that is far from the case. Every implementation of Modula-2 comes with a substantial library of routines designed to solve certain problems commonly encountered in writing programs. As noted in the discussion of the simple example earlier in this chapter, those library routines include code for input and output. There are also pre-programmed mathematical functions, utilities for using other parts of the system (such as the computer's clock), and many others. Almost all Modula-2 programs import from these libraries, so a note should be made at any stage of the planning process when it is observed that the library can be used.

Example problem library use:

This problem has output requirements. It will, therefore make use of the standard STextIO and SWholeIO Modula-2 libraries. No other libraries are required.

Strategic Step 5 Break the problem into steps.

This is done first into larger tasks, then into smaller ones. Simple programs may not have this distinction, but most do. Ultimately, individual detailed program statements must be fed to the computer's editor one statement at a time for later compilation. The place to decide how to do this is not at the terminal, as the programmer sits down to start typing. Rather, the steps to solve the problem must be written out ahead of time in enough detail to allow a more or less direct translation into computer code.

The amount of detail necessary varies with experience and familiarity with the question at hand, but most problems worth solving by computer require several refinements first into broad detail, then into finer steps. If several restatements and refinements are necessary, they must be documented. The time spent at this stage saves many hours later. Sloppily designed and poorly thought out programs simply do not work.

Example problem refinement:

1. Input Section	 obtain base
			 obtain exponent
			(these will be stored in the program)
2. Computation	 calculate baseexponent
3. Output		 print out final result

Second refinement of problem: (same numbers as above)

1. Set up values of base and exponent
	 Assign the value of the base to a cardinal variable
	 Assign the value of the exponent to another cardinal variable

2. Computation
	 set the result initially to the base
	 set a counter to one
	 while the counter is less than the exponent
		multiply the result by the base and increase the counter

3. Print out the final answer

2.3.3 Data Tables and Sample I/O

Goals: Write everything down.

Strategic Step 6 List all variables and imports.

Before actually beginning to code, write down the names of all variables that will be used and the names of all library items required. This section serves as a quick reference when writing the code, so that a name is not inadvertently used for the wrong thing.

Example problem data table:

 Variables: base, exponent, counter, result--all cardinals
 Imports from STextIO: WriteString, WriteLn
              from SWholeIO: WriteCard

Strategic Step 7 Show what input is required and what output is expected

Here, the exact form of everything that will appear on the computer screen is specified. The final program is correct if it matches the specifications that were written for it in advance. Note that this section does not contain a sample of the actual output produced after the program is run; it specifies what the output for a given input will be before the program is ever written.

Example problem sample I/O:

Input:

Set the base to 5 and the exponent to 6 in the code.

Output:

5 raised to the power 6 equals 15625

2.3.4 Refining the Solution

Goals: Refine the sub-tasks into individual steps.

Strategic Step 8 Sketch the solution using pseudocode

Writing the solution in pseudocode is just another refinement, this time into a shorter and less wordy form. Pseudocode resembles the final program, but there is no need to pay attention to the exact syntax of the computing notation that will be used.

Example problem pseudocode:

  Write "This program will raise a given base to a given exponent"
  Assign the base
  Assign the exponent
  result <-- base
  counter <-- 1
  while counter <-- exponent
    result <-- result * base
    counter <-- counter + 1
  write base
  write "raised to the power"
  write exponent
  write "equals"
  write result

Strategic Step 9 Refine the code completely before entering it

Do not waste scarce computer resources by doing initial rough copies of code at the keyboard. Ideally, what the programmer does type is so well thought out and so carefully written out (by hand) that it compiles and runs error free the first time. Actually, the world may not always turn in this fashion, but it is nice to try. In the case at hand, the final code looks like this:

MODULE Powers;

FROM STextIO IMPORT
  WriteString, WriteLn;

FROM SWholeIO IMPORT
  WriteCard;

VAR
  base, exponent, counter, result: CARDINAL;

BEGIN
  WriteString ("This program raises a base to a power");
  WriteLn;
  base := 4;
  exponent := 6;
  result := base;
  counter := 1;
  WHILE counter < exponent
    DO
      result  := result *  base;
      counter := counter + 1
    END;

  WriteCard (base, 0);
  WriteString ( " raised to the power ");
  WriteCard (exponent, 0);
  WriteString (" equals ");
  WriteCard (result, 0);
  WriteLn;

END Powers.

NOTES: 1. Observe the specific syntax for the listing of variables and giving their type at the start of the program, for assignment and for the Modula-2 version of the WHILE loop. The assignment operator := is a reserved symbol; WHILE and DO are reserved words, and the name CARDINAL is a built-in identifier (see section 2.5.2.)

2. The purpose of the number 0 in the WriteCard statements will be given later.

3. Observe the use of spaces in the WriteString statements in order to separate the words from the numbers.

4. If using non standard-conforming Modula-2, WriteCard may be imported from InOut. Only one FROM..IMPORT line is needed instead of two.

There you have it--the top-down design of a small program in all its gory detail. As mentioned earlier, the amount of detail may vary, as may the number of times one must refine the problem into steps, but the kind of planning outlined here is not optional.

2.3.5 Execution and Satisfaction

Goals: 1. Execute the completed process.

2. Re-develop the solution until the desired goal is reached.

Strategic Step 10 Compile, link and run the finished program

The task is not complete until the program has been run and the output checked against the specifications. Output from a few sample runs should be recorded and made a part of the documentation for the project.

Example problem sample output:

First run: (using the code above)

This program raises a base to a power
 4 raised to the power  6 equals  4096

Second run: (with the base set to 3 and the exponent to 4)

This program raises a base to a power
 3 raised to the power  4 equals  81

Strategic Step 11 Check actual output with specifications and correct errors

Only the final code was given above. The first time it was compiled there were several punctuation errors, including some missing semicolons and a missing colon in an assignment operator. The sample program could also use a little more work (not done here) in order to catch erroneous inputs such as incorrectly typed numbers. It also produces an incorrect result if the exponent is zero (try it.) That possibility was not allowed for in the original problem statement, so the solution is correct. However, one could add additional code, either to give a correct result for this case, or to exclude it by printing an error message whenever zero is input for the exponent.


Contents