At this point we have covered enough topics that we should introduce the concept of algorithms and efficiency. Although the word sounds complicated, the concept is quite simple. An algorithm is a step-by-step problem-solving method, especially one that is an established method for solving a problem in a finite number of steps. Using a very loose interpretation of the word, every program we write to solve a problem is an algorithm. However, we usually reserve it for, as the definition says, some established method of solving a problem. Many well-known algorithms are extensively documented in various textbooks for solving problems that tend to recur in programming (such as sorting an array in ascending or descending order). We will cover many of these algorithms in Unit II. For now, we will simply introduce the concept of designing an algorithm.

Often, it is easiest to describe an algorithm in pseudocode before trying to code it. Pseudocode is pseudo because it has no defined syntax. In other words, we simply describe the steps of an algorithm in plain spoken-language terms. For example, the following is the pseudocode algorithm for finding a mean:
Set variable Sum to 0
Loop until reaching end of list:
  Add each value in the list to Sum
Divide Sum by total number of items in list
One advantage of pseudocode is that it is immediately obvious what the steps of the algorithm are without placing it into any programming language (which in turn makes it easy to translate into any programming language). Pseudocode can essentially be anything you want (since it has no defined syntax). The pseudocode above is written in very plain English, but we could write it in a more mathematical form:
  Every algorithm generally must meet two requirements (the first is obvious):
  1. It must successfully solve the problem it is meant to solve for all possible cases of input.
  2. It should solve the problem in the most computationally efficient manner possible.
The first requirement states that it must sucessfully solve the problem for all possible cases of input. For example, consider our function for finding the mean from the previous section:
function Mean(const A : TRealArray;
  Count : Integer) : Real;
var
  K : Integer;
  Sum : Real;
begin
  Sum := 0;
  For K := 0 to Count-1 do
    Sum := Sum+A[K];
  Result := Sum/Count;
end;
This algorithm successfully computes the mean for everything except an empty array. If Count is 0 then it fails because you can't divide by 0. A more robust algorithm would be the following:
function Mean(const A : TRealArray;
  Count : Integer) : Real;
var
  K : Integer;
  Sum : Real;
begin
  if Count > 0 then
  begin
    Sum := 0;
    For K := 0 to Count-1 do
      Sum := Sum+A[K];
    Result := Sum/Count;
  end
  else Result := 0;
end;
Excercise 3-10.
Solve the following problems.
  1. Say we have two variables and . Write pseudocode for an algorithm to swap the values in the two variables.
  2. Using the pseudocode from above, write a procedure in Object Pascal that swaps two integer variables.
    Although it is fairly trivial, the swap algorithm is quite fundamental so you should remember it. 
The second requirement of an algorithm is that it solves the problem in the most efficient way possible. Computational efficiency can often be tricky to define. As a general rule, it is simply the algorithm that executes the fewest statements (more acurately the fewest number of efficient assembly statements when the high level language is translated to machine code, but this is beyond the scope of this unit). However, having the smallest number of statements does not always mean you have the most efficient algorithm. For example, consider this variation of computing the mean:
function Mean(const A : TRealArray;
  Count : Integer) : Real;
var
  K : Integer;
begin
  if Count > 0 then
  begin
    Result := 0;
    For K := 0 to Count-1 do
      Result := Result+A[K]/Count;
  end
  else Result := 0;
end;
This certainly has fewer statements as well as fewer variables by dividing each A[K] by Count. It achieves the exact same result. However, it is much less efficient than the previous algorithm. The reason is that a real number division is one of the most computationally expensive operations the processor can perform. The way the algorithm is written now, it will perform one division for every item in the array instead of one division per call to the function Mean. Thus, in terms of faster code, the previous formulation of the algorithm is more efficient.
Excercise 3-11.
In Section 2.10 we wrote a simple loop algorithm that computes the greatest common factor (gcf) of two numbers by testing the expression Factor1 mod Factor2 = 0 all the way from 2 to min(Factor1,Factor2). Although this algorithm accomplishes what it sets out to do, it is not actually the most efficient way to find the gcf of two numbers. The fastest algorithm known for finding the gcf is Euclid's algorithm. If you remember from mathematics, Euclid was the Greek mathematician who developed much of the theory behind modern geometry over 2000 years ago. This makes Euclid's algorithm one of the oldest (possibly even the oldest) known algorithm. As with most improvements of algorithmic efficiency, the algorithm comes from an insight about the properties of two integers with respect to their gcf: the gcf of two numbers does not change if the smaller number is subtracted from the larger. For example, 8 is the gcf of 40 and 16. (40-16) = 24 and the gcf of 24 and 16 is still 8. This is easy to see when we rewrite 40 and 16 in terms of their gcf's: 8*5-8*2 = 8*(5-2). If we replace the larger number with the difference and continue this loop, the difference will eventually be 0 because the larger number will always decrease by an integer multiple of one of its factors:
Iteration 1: (40-16) = 8*5-8*2 = 8*(5-2) = 8*3 = 24
Iteration 2: (24-16) = 8*3-8*2 = 8*(3-2) = 8*1 = 8
Iteration 3: (16-8) = 8*2-8*1 = 8*(2-1) = 8*1 = 8
Iteration 4: (8-8) = 8*1-8*1 = 8*(1-1) = 8*0 = 0
  1. Write pseudocode for that specifies the algorithm described above.
  2. Implement the pseudocode from the previous problem in Object Pascal. Our previous algorithm from Section 2.10 is given below. Compare it to Euclid's algorithm by placing a global variable counter in each that counts the number of iterations. Test both implementations on GCF(40,16) and GCF(8704,22016) by printing the returned values and iteration counts to the screen (Remember: You'll need the unit Math for the Min function in following code).
    function SlowGCF(A,B : Integer) : Integer;
    var
      K : Integer;
    begin
      for K := Min(A,B) downto 1 do
      begin
        if (A mod K = 0) and (B mod K = 0) then
        begin
          Result := K;
          Break;
        end;
      end;
    end;
  3. In the previous problem we implemented Euclid's algorithm using subtractions. Is there a better way? Think about how 40-16 = 24 and then 24-16=8. We subtracted 16 twice. Is there a way we can save iterations by doing an operation only once? In other words, given 40 and 16 we could find some X such that 40-16*X = SomeNum where SomeNum is the next value to be used in the iteration? Hint: Think about what would happen in this situation if X = 3. Then think about what simple operation between 40 and 16 would give 8. Really: think about this before looking at the solution.
  4. Given what we discovered in the previous problem, write the pseudocode for an even faster version of Euclid's algorithm. Start with the iterations we used before and think about how we eliminate iterations.
    Iteration 1: (40-16) = 8*5-8*2 = 8*(5-2) = 8*3 = 24
    Iteration 2: (24-16) = 8*3-8*2 = 8*(3-2) = 8*1 = 8
    Iteration 3: (16-8) = 8*2-8*1 = 8*(2-1) = 8*1 = 8
    Iteration 4: (8-8) = 8*1-8*1 = 8*(1-1) = 8*0 = 0
  5. Implement the pseudocode from the previous problem in Object Pascal as a function called FastGCF. Include an iteration counter and then compare all three algorithms with 40 and 16 as well as 8704 and 22016.
  6. Take this exercise one step further by writing one line of code that will give the least common multiple (LCM) in terms of the greatest common factor. Hint: Think about what it would mean for two numbers to have a least common multiple. For example, the lcm of 2 and 4 is 4 because 4 is evenly divisible by 2. But for 5 and 7 it's 5*7 = 35 because they have no common factors. What about 10 and 15. Is it 10*15 = 150? This is a common multiple but it is not the least common multiple because 10 and 15 share 5 as a common factor. So given this knowledge, how would we find the least common multiple when we know the greatest common factor.