Algorithms/Overview

Writing an algorithm

An algorithm is essentially a way of representing step-by-step solutions to a problem. It therefore can be presented in many different literary forms (or languages). The only essential requirement is that it should be able to clearly communicate the steps of the solution. This requirement also justifies the use of different forms, since a solution to a particular problem might be more suitable in one form than another. However, there is a universally preferred language to represent algorithms called Pseudocode. Pseudocode is a language-like codification with two distinct parts: a language part that explains each step, and a structured part that adds extra algorithm-specific features (such as selection, looping, etc.) and makes the algorithm more easily understood.

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