Algorithms

Introduction See Introduction to Algorithms.

Writing an algorithm

Algorithm essentially is just a way of representing step-by-step solution of a problem. It, hence, can be presented in many different literary forms (or languages). Only essential requirement is that it should be able to communicate the steps of solution clearly. This requirement also justifies the use of different forms as solution to a particular problem is more suited in one form than the others. There, however, exists a universally preferred language to represent algorithms; Its Pseudocode. Pseudocode is an English like language having two distinct parts, a english part which deals with explanation of step, and a structured part which adds extra algorithm specific features (like selection, looping etc) and also increases understandability as an algorithm.

To further explain the making of an algorithm, we'll take an example of a few commonly used ones.

The first will be a simple function that finds a specified character in a string. It will return -1 if the character is not found, or else the last position in the string at which that character appears.

Pseudocode

 Function FindCharacter (CharacterToFind, StringToSearch) returns Position
   Step 1.
   Position := -1
   PositionInString := 0
   Step 2.
     Let character C := PositionInString in StringToSearch
     If character C equals CharacterToFind then Position := PositionInString
     PositionInString := PositionInString + 1
   If PositionInString < length of StringToSearch then go back to Step 2
   Return Position
 End Function

C code

int findChar(char ch, const char *s)
{
    int i, n = strlen(s);
    int position = -1;
    for (i=0; i < n; ++i) {
        if (s[i] == ch)
          position = i;
    }
    return position;
}

Recursive Algorithms

Recursion actually means to repeat a set of steps in a similar way. In computer science, recursive generally refers to an algorithm that calls itself, usually on a subset of the same problem. In more general language An algorithm is called recursive algorithm if an step in the algorithm instructs to repeat the same algorithm again with different/same/similar set of data. This approach is particularly useful in solving problems having step wise solution, in which the problem is reduced into smaller parts at each step and eventually solved at a particular step. An typical example is of finding factorial where

(n)! = n.(n-1)! = n.(n-1).(n-2)! = n.(n-1).(n-1)...(3).(2).(1).(0!)

we only know the value of factorial 0 i.e. 1, however we can reduce each factorial finding problem into smaller parts until its dependent only on value of factorial 0 and at this step our problem gets solved.

As the previous example would suggest each recursive algorithm is essentially divided into two parts. First part, the base case, is the condition which solves the problem; Second part, general case, is the condition which divides the problem into smaller part(s) such that each of the parts approaches base case. Hence at this point we can conclude that writing of a recursive algorithm involves three steps, viz.

• Determine the base case
• Determine the general case
• Combine the two into an algorithm

A point to be noted is that every recursive solution can also be represented in a iterative form and vice-versa. Iterative solutions have lesser memory requirements but are more complex in general, recursive solutions on other hand are easier to visualize, simpler and straight forward in concepts but require more memory and run-time. So for a programmer choosing one of them is actually a trade off between simplicity and resources. A given problem may naturally be suited to solutions using any one of them, if case be so use of other solution should be avoided.

Pseudocode example of factorial algorithm:

 Function Factorial (num) returns Value_of_Factorial
   Base case:
   If(num equals 0)
     Return 1
   End if
   General Case:
   Return Factorial(num-1)
 End Function

Partial List of Algorithms

• Bubble Sort
• Insertion Sort
• Selection Sort
• Shell Sort
• Quick Sort
• Fibonacci Sequence
• Topological Sorting
• Binary Search
• Binary Search Tree
• Data Encryption Standard (DES)
• Gauss-Jordan Elimination
• Doomsday Algorithm