← •   HOME  • UP  •   →
Top/Algorithms/Discovery  

8.2. Algorithm Discovery


Common sense

Your most important tool for discovering algorithms is common sense. Think about how you would solve a problem by hand. Try examples. Then work out how to express your hand algorithm so that a computer can carry it out.


A sequence of steps

Some problems break naturally down into a sequence of a fixed number of steps. The steps themselves can be big ones, each involving an algorithm of its own, but the big picture is a sequence of steps.

As an example, consider the problem of writing a nonnegative integer i using at least n characters by adding spaces as required. But instead of padding with spaces on the left, we will add spaces to the right end. For example, 

  writePadded(25,4);
  writePadded(725,4);
  writePadded(9,4);
writes 
  25  725 9
using 4 total characters for each number, but with the added spaces to the right of the number. (If i uses more than n characters, then writePadded(i, n) just writes i, without any added spaces.)

(It would be possible to use printf to do this job. A simple definition of writePadded is as follows. 

  void writePadded(int x, int n)
  {
    printf("%-*i", n, x);
  }
but our purpose here is not so much about writing a definition of writePadded, but instead of using it to illustrate algorithm design, so we avoid using printf.)

The steps to do writePadded(i,n) are as follows.

  1. Write the integer i (without any padding), counting the number of characters used. Suppose that a total of k characters are used in this step.
  2. If n > k then write n−k spaces.

The individual steps still need to be solved, but you don't need to worry about that right away. Breaking the problem down into steps has yielded some simpler problems.


Top-down design

At this point in writing a definition of writePadded, you might hope to find a function in the library that carries out step 1 and another that carries out step 2. But you do not always find one. In that case, the principle of top-down design suggests that you should imagine that suitable functions are already available, and use them. Then work out how to solve them; write them yourself. Of course, in order to do this, you need to know exactly what each of the imagined functions is supposed to do. So you need a contract and heading for each one. It is the function bodies that you fill in later.

For writePadded(i, n), here are some obvious tools, one for doing step 1 and the other for doing step 2.

  1. writeInteger(i) writes nonnegative integer i and returns the number of characters written.

  2. writeSpaces(n) writes n spaces.

Using those tools yields a simple definition of writePadded. 

  void writePadded(int i, int n)
  {
    int k = writeInteger(i);
    if(n > k)
    {
      writeSpaces(n - k);
    }
  }
Notice that it is clearly two steps, one after the other.


Loops

If a problem involves doing a variable number of steps, a loop is an obvious tool to use. For example, how would you write n spaces? It suffices to write one space n times. That is a simple repetition. 

  void writeSpaces(int n)
  {
    for(int i = 1; i <= n; i++)
    {
      putchar(' ');
    }
  }
We will encounter other algorithms that are naturally expressed as loops.


Cases

Some problems break down into two or more cases. For example, to find the larger of x and y, you know that

  1. If x > y, then x is the larger one.
  2. If x <= y, then y is the larger one.
The great thing about breaking a problem down into cases is that you only need to think about how to solve one case at a time. Then, putting all of the cases together yields a solution to the whole problem, as in the following definition of larger. 
  int larger(int x, int y)
  {
    if(x > y)
    {
      return x;
    }
    else
    {
      return y;
    }
  }

 

← •   HOME  • UP  •   →
Top/Algorithms/Discovery