Previous: 1.3 Designing Programs and the C Language
Up: 1.3 Designing Programs and the C Language
Next: 1.3.2 The C Language
Previous Page: 1.3 Designing Programs and the C Language
Next Page: 1.3.2 The C Language

1.3.1 Designing The Algorithm

An algorithm is a general solution of a problem which can be written as a verbal description of a precise, logical sequence of actions. Cooking recipes, assembly instructions for appliances and toys, or precise directions to reach a friend's house, are all examples of algorithms. A computer program is an algorithm expressed in a specific programming language. An algorithm is the key to developing a successful program.

Suppose a business office requires a program for computing its payroll. There are several people employed. They work regular hours, and sometimes overtime. The task is to compute pay for each person as well as compute the total pay disbursed.

Given the problem, we may wish to express our recipe or algorithm for solving the payroll problem in terms of repeated computations of total pay for several people. The logical modules involved are easy to see.

Algorithm: PAYROLL

     Repeat the following while there is more data:
          get data for an individual,
          calculate the pay for the individual from the current data,
               and, update the cumulative pay disbursed so far,
          print the pay for the individual.
     After the data is exhausted, print the total pay disbursed.

Figure 1.5 shows a for our task. This is a layered diagram showing the development of the steps to be performed to solve the task. Each box corresponds to some subtask which must be performed. On each layer, it is read from left to right to determine the performance order. Proceeding down one layer corresponds to breaking a task up into smaller component steps -- a refinement of the algorithm. In our example, the payroll task is at the top and that box represents the entire solution to the problem. On the second layer, we have divided the problem into two subtasks; processing a single employee's pay in a loop (to be described below), and printing the total pay disbursed for all employees. The subtask of processing an individual pay record is then further refined in the next layer. It consists of, first reading data for the employee, then calculating the pay, updating a cumulative total of pay disbursed, and finally printing the pay for the employee being processed.

The structural diagram is useful in developing the steps involved in designing the algorithm. Boxes are refined until the steps within the box are ``doable''. Our diagram corresponds well with the algorithm developed above. However, this type of diagram is not very good at expressing the sequencing of steps in the algorithm. For example, the concept of looping over many employees is lost in the bottom layer of the diagram. Another diagram, called a flow chart is useful for showing the control flow of the algorithm, and can be seen in Figure 1.6. Here the actual flow of control for repetitions is shown explicitly. We first read data since the control flow requires us to test if there is more data. If the answer is ``yes'' we proceed to the calculation of pay for an individual, updating of total disbursed pay so far, and printing of the individual pay. We then read the next set of data and loop back to the test. If there is more data, repeat the process, otherwise control passes to the printing of total disbursed pay and the program ends.

From this diagram we can write our refined algorithm as shown below. However, one module may require further attention; the one that calculates pay. Each calculation of pay may involve arithmetic expressions such as multiplying hours worked by the rate of pay. It may also involve branching to alternate computations if the hours worked indicate overtime work. Incorporating these specifics, our algorithm may be written as follows:

Algorithm: PAYROLL

     get (first) data, e.g., id, hours worked, rate of pay
     while more data (repeat the following)
          if hours worked exceeds 40
               (then) calculate pay using overtime pay calculation
          otherwise calculate pay using regular pay calculation
          calculate cumulative pay disbursed so far
          print the pay statement for this set of data
          get (next) data

     print cumulative pay disbursed

The algorithm is the most important part of solving difficult problems. Structural diagrams and flow charts are tools that make the job of writing the algorithm easier, especially in complex programs. The final refined algorithm should use the same type of constructs as most programming languages. Once an algorithm is developed, the job of writing a program in a computer language is relatively easy; a simple translation of the algorithm steps into the proper statements for the language. In this text, we will use algorithms to specify how tasks will be performed. Programs that follow the algorithmic logic will then be easy to implement. Readers may wish to draw structural diagrams and flow charts as visual aids in understanding complex algorithms.

There is a common set of programming constructs provided by most languages useful for algorithm construction, including:

• : test a condition, and specify steps to perform for the case when the condition is satisfied (True), and (optionally) when the condition is not satisfied (False). This construct was used in our algorithm as:

  if overtime hours exceed 40
            then calculate pay using overtime pay calculation
       otherwise calculate pay using regular pay calculation

• : repeat a set of steps as long as some condition is True, as seen in:

  while new data repeat the following
            ...

• or print data from/to peripheral devices. Reading of data by programs is called data input and writing by programs is called data output. The following steps were used in our algorithm:

  read data
       write/print data, individual pay, disbursed pay

Languages that include the above types of constructions are called

and include such languages as C, Pascal, and FORTRAN.

A program written in an algorithmic language must, of course, be translated into machine language. A Utility program, called a , translates source programs in algorithmic languages to object programs in machine language. One instruction in an algorithmic language, called a , usually translates to several machine level instructions. The work of the compiler, the translation process, is called compilation.

To summarize, program writing requires first formulating the underlying algorithm that will solve a particular problem. The algorithm is then coded into an algorithmic language by the programmer, compiled by the compiler, and loaded into memory by the operating system. Finally, the program is executed by the hardware.