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:

• BruteForce: Try all possible solutions until you find the right one.

• DivideAndConquer: Split the problem into two or more subproblems, solve the subproblems recursively, and then combine the solutions.

• DecreaseAndConquer: Reduce the problem to a single smaller problem, solve that problem recursively, and then use that solution to solve the original problem.

• TransformAndConquer: Either (a) transform the input to a form that makes the problem easy to solve, or (b) transform the input into the input to another problem whose solution solves the original problem.

• UseSpace: Solve the problem using some auxiliary data structure.

• DynamicProgramming: Construct a table of solutions for increasingly large subproblems, where each new entry in the table is computed using previous entries in the table.

• GreedyMethod: Run through your problem one step at a time, keeping track of the single best solution at each step. Hope sincerely that this will not lead you to make a seemingly-good choice early with bad consequences later.

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.

• BruteForce: For index i, test if A[i] is greater than or equal to every element in the array. When you find such an A[i], return it. For this algorithm, T(n) = n*Theta(n) = Theta(n2) if implemented in the most natural way.

• DivideAndConquer: If A has only one element, return it. Otherwise, let m1 be the maximum of A[1]..A[n/2]. Let m2 be the maximum of A[n/2+1]..A[n]. Return the larger of m1 and m2. The running time is given by T(n) = 2T(n/2) + Theta(1) = Theta(n).

• DecreaseAndConquer: If A has only one element, return it. Otherwise, let m be the maximum of A[2]..A[n]. Return the larger of A[0] and m. Now the running time is given by T(n) = T(n-1) + Theta(1) = Sigmai=1 to n Theta(1) = Theta(n).

• TransformAndConquer: Sort the array, then return A[n]. Using an optimal comparison-based sort, this takes Theta(n log n) + Theta(1) = Theta(n log n) time. The advantage of this approach is that you probably don't have to code up the sort.

• UseSpace: Insert all elements into a balanced binary search tree, then return the rightmost element. Cost is Theta(n log n) to do n insertions, plus Theta(log n) to find the rightmost element, for a total of Theta(n log n). Sorting is equivalent and probably easier.

• DynamicProgramming: Create an auxiliary array B with indices 1 to n. Set B[1] = A[1]. As i goes from 2 to n, set B[i] to the larger of B[i-1] and A[i]. Return B[n]. Cost: Theta(n).

• GreedyMethod: Let max = A[1]. For each element A[i] in A[2..n], if A[i] > max, set max = A[i]. Return the final value of max. Cost: Theta(n); this algorithm is pretty much identical to the previous one.

# 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).

• BruteForce: For each of the n! permutations of the input, test if it is sorted by checking A[i] <= A[i+1] for all i. Cost if implemented naively: n!*Theta(n) = Theta(n*n!). This algorithm is known as deterministic monkeysort or deterministic bogosort. It also has a randomized variant, where the careful generation of all n! permutations is replaced by shuffling. The randomized variant is easier to code and runs about a factor of two faster than the deterministic variant, but does not guarantee termination if the shuffling is consistently unlucky.

• DivideAndConquer: Sort A[1..floor(n/2)] and A[floor(n/2+1)..n] separately, then merge the results (which takes Theta(n) time and Theta(n) additional space if implemented in the most straightforward way). Cost: T(n)=2T(n/2)+Theta(n)=Theta(n log n) by the Master Theorem. This algorithm is known as MergeSort, and is one of the fastest general-purpose sorting algorithms. The merge can be avoided by carefully splitting the array into elements less than and elements greater than some pivot, then sorting the two resulting piles; this gives QuickSort. The performance of QuickSort is often faster than MergeSort in practice, but its worst-case performance (when the pivot is chosen badly) is just as bad as the result of:

• DecreaseAndConquer: Remove A[n], sort the remainder, then insert A[n] in the appropriate place. This algorithm is called InsertionSort. The final insertion step requires finding the right place (which can be done fairly quickly if one is clever) but then moving up to n-1 elements to make room for A[n]. Total cost is given by T(n) = T(n-1) + Theta(n) = T(n2).

• TransformAndConquer: I'm not aware of any good general TransformAndConquer approach to sorting (there are some bad ones), but in some cases one can transform seemingly general sorting problem (e.g. sorting strings) into specialized sorting problems that permit faster solutions (e.g. sorting small integers).

• UseSpace: Insert the elements into a balanced binary search tree, then read them out from left to right. Another version: insert them into a heap. Both take Theta(n log n) time, but are more complicated to implement than MergeSort or QuickSort unless you have BST or heap code lying around already.

• DynamicProgramming: (InsertionSort may be seen as an example of this.)

• GreedyMethod: Find the smallest element, mark it as used, and output it. Repeat until no elements are left. The result is SelectionSort, which runs in a respectable but suboptimal Theta(n2) time.

2014-06-17 11:57