Algorithms

An algorithm is a finite sequence of steps, each step taking a finite length of time, that solves a problem or computes a result. A computer program is one example of an algorithm, as is a recipe to make lasagna. In both of these examples, the order of the steps matter. In the case of lasagna, the noodles must be cooked in boiling water before they are layered into the filling to be baked. It would be inappropriate to place the raw noodles into the pan with all the other ingredients, bake it, and then later remove the already baked noodles to cook them in boiling water separately. In the same way, the ordering of steps is very important in a computer program. While this point may be obvious, consider the following sound argument:

1. The relationship between degrees Celsius and degrees Fahrenheit can be expressed as

                              ◦C = 5/ 9 ×( ◦F −32) 
   

2. Given a temperature in degrees Fahrenheit, the corresponding temperature in degrees Celsius can be computed

Unfortunately, when run the program always displays

                         -17.7778  

regardless of the input provided. The English description provided above is correct. The formula is implemented faithfully. The problem lies simply in statement ordering. The statement

                          degreesC = 5/9*(degreesF - 32);  

is an assignment statement, not a definition of a relationship that exists throughout the program. At the point of the assignment, degreesF has the value of zero. The variable degreesC is assigned before degreesF’s value is received from the user

As another example, suppose x and y are two variables in some program. How would we interchange the values of the two variables? We want x to have y’s original value and y to have x’s original value. This code may seem reasonable:

                x = y  

                 y = x  

The problem with this section of code is that after the first statement is executed, x and y both have the same value (y’s original value). The second assignment is superfluous and does nothing to change the values of x or y. The solution requires a third variable to remember the original value of one the variables before it is reassigned. The correct code to swap the values is

              temp = x 

              x = y  

              y = temp 

We can use tuple assignment to make the swap even simpler:

        x, y = y, x  

These small examples emphasize the fact that algorithms must be specified precisely. Informal notions about how to solve a problem can be valuable in the early stages of program design, but the coded program requires a correct detailed description of the solution.

The algorithms we have seen so far have been simple. Statement 1, followed by Statement 2, etc. until every statement in the program has been executed. Chapters 4 and ?? introduce some language constructs that permit optional and repetitive execution of some statements. These constructs allow us to build programs that do much more interesting things, but more complex algorithms are required to make it happen. We must not lose sight of the fact that a complicated algorithm that is 99% correct is not correct. An algorithm’s design and implementation can be derailed by inattention to the smallest of details.