[FrontPage] [TitleIndex] [WordIndex] 

Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

Basic principles of algorithm design

The fundamental principle of algorithm design was best expressed by the mathematician George_Polya: "If there is a problem you can't solve, then there is an easier problem you can solve: find it." For computers, the situation is even easier: if there is any technique to make a problem easier even by a tiny bit, then you can repeat the technique until the problem becomes trivial.

For example, suppose we want to find the maximum element of an array of n ints, but we are as dumb as bricks, so it doesn't occur to us to iterate through the array keeping track of the largest value seen so far. We might instead be able to solve the problem by observing that the maximum element is either (a) the last element, or (b) the maximum of the first n-1 elements, depending on which is bigger. Figuring out (b) is an easier version of the original problem, so we are pretty much done once we've realized we can split the problem in this way. Here's the code: 

   1 /* returns maximum of the n elements in a */
   2 int
   3 max_element(int a[], int n)
   4 {
   5     int prefix_max;
   6 
   7     assert(n > 0);
   8 
   9     if(n == 1) {
  10         return a[0];
  11     } else {
  12         prefix_max = max_element(a, n-1);
  13         if(prefix_max < a[n-1]) {
  14             return a[n-1];
  15         } else {
  16             return prefix_max;
  17         }
  18     } 
  19 }

Note that we need a special case for a 1-element array, because the empty prefix of such an array has no maximum element. We also assert that the array contains at least one element, just to avoid mischief.

One problem with this algorithm (at least when coding in C) is that the recursion may get very deep. Fortunately, there is a straightforward way to convert the recursion to a loop. The idea is that instead of returning a value from the recursive call, we put it in a variable that gets used in the next pass through the loop. The result is 

   1 /* returns maximum of the n elements in a */
   2 int
   3 max_element(int a[], int n)
   4 {
   5     int i;              /* this replaces n-1 from the recursive version */
   6     int prefix_max;
   7 
   8     assert(n > 0);
   9 
  10     prefix_max = a[0];  /* this is the i == 0 case */
  11 
  12     for(i = 1; i < n; i++) {
  13         if(prefix_max < a[i]) {
  14             prefix_max = a[i];  /* was return a[n-1] */
  15         }
  16         /* else case becomes prefix_max = prefix_max, a noop */
  17     }
  18 
  19     /* at the end we have to return a value for real */
  20     return prefix_max;
  21 }

Classifying algorithms by structure

Algorithm design often requires both creativity and problem-specific knowledge, but there are certain common techniques that appear over and over again. The following classification is adapted from LevitinBook:

Some of these approaches work better than others---it is the role of AlgorithmAnalysis (and experiments with real computers) to figure out which are likely to be both correct and efficient in practice. But having all of them in your toolbox lets you try different possibilities for a given problem.

Example: Finding the maximum

Though this classification is not completely well-defined, and is a bit arbitrary for some algorithms, it does provide a useful list of things to try in solving a problem. Here are some examples of applying the different approaches to a simple problem, the problem of finding the maximum of an array of integers.

Example: Sorting

The sorting problem asks, given an array of n elements in arbitrary order, for an array containing the same n elements in nondecreasing order, i.e. with A[i] <= A[i+1] for all i. We can apply each of the techniques above to this problem and get a sorting algorithm (though some are not very good).

CategoryAlgorithmNotes CategoryProgrammingNotes

2014-06-17 11:57