loading image... Gichuki P Mwangi

Algorithm

Computer Science is heavily dependent on Mathematics – heavily. Mathematics is founded on logic and that directly translates to the foundation of Computer Science. Every time a computer is powered on, there is logic, there is Mathematics at its simplest. This article is going to use this all too obvious relationship to deflate the complexity of Algorithms into a simple and palatable topic.

Computer Scientists face problems that require logic to solve, all the time. They can be complex or simple. To find a solution, they have to come up with resounding procedures, experiments to prove and facts to support claims. Logic has to be used and steps have to be followed. That simple explanation enables the meaning of an algorithms which can be defined as; a finite, unambiguous and procedural specification of how to solve a problem or class of problems. 

Be it writing a program, executing a program or eating a sandwich, an algorithm has to be adopted – knowingly or not. This article shall not talk about eating sandwiches, no. Rather, examples of algorithms shall be used starting with a very simple Mathematics algorithm and moving forward into Computer Science.
When solving any arithmetic, there is an order that is followed. BODMAS – the order of operations is the go to here. Consider an expression:
7 x  √9 ÷ 3 (4+8) – 3 + 1

To solve this expression;
1. Solve what is in the BRACKETS.
2. Take care of the ORDERS (in this case ‘square root’)
3. Deal with DIVISION
4. MULTIPLY all relevant operands
5. ADD what is to be added
6. Make relevant SUBTRACTIONS
This here, is an algorithma finite, unambiguous and procedural specification of how to solve a problem or class of problems. 

The solution
7 x  √9 ÷ 3 (4+8) – 3 + 1
(i) … 4 + 8 = 12 therefore; 7 x  √9 ÷ 3 (12) – 3 + 1
(ii)… √9 = 3 therefore; 7 x  3 ÷ 3 (12) – 3 + 1
(iii).. 3 ÷ 3 = 1 therefore; 7 x  1(12) – 3 + 1
(iv).. 7 x 1 x 12 = 84 therefore; 84 – 3 + 1
(v)… -3 + 1 = -2 and we are left with 84 – 2
(vi).. the answer: 82

In Computer Science, it is not really different in its implementation save for some few changes with regard to logic. This becomes obvious with the use of switch, if…else, loops and operands that are a step further from the norm. To fully comprehend an algorithm in Computer Science, the use of an example is important.
We shall use Java Programming Language for this example.

Merge Sort Algorithm
This algorithm is used for sorting items in a list (array) by comparing them in an efficient fashion.
To elaborate the algorithm, I shall use these three steps;
1. A pictorial illustrating the algorithm.
2. Pseudo code giving procedure of the algorithm.
3. The actual Java Code of the algorithm.

A pictorial of a merge sort algorithm.

Pseudo Code
1. Divide list of unsorted elements into two
2. Divide each of the two groups acquired in step 1 into two
3. Divide each of the four groups acquired in step 2 into two to acquire single entities
4. Merge the single entities into pairs by comparing elements and organizing them starting with the lesser one
5. Merge the groups acquired in step 4 into groups of four and organize them in ascending order
6. Merge the resulting groups into one single list in an ascending fashion
7. Sort is completed

Java Code

package com.instanceofjava.mergesortalgorithm;
public class MergeSortAlgorithm {
private int[] resarray;
private int[] tempMergArray;
private int length;
public static void main(String a[]){

int[] inputArr ={6,42,2,32,15,8,23,4};
System.out.println(“Before sorting”);
for(int i:inputArr){
System.out.print(i);
System.out.print(” “);
}
MergeSortAlgorithm mergesortalg = new MergeSortAlgorithm();
mergesortalg.sort(inputArr);
System.out.println();
System.out.println(“After sorting”);
for(int i:inputArr){
System.out.print(i);
System.out.print(” “);
}
}
public void sort(int inputArray[]) {
this.resarray = inputArray;
this.length = inputArray.length;
this.tempMergArray = new int[length];
doMergeSort(0, length – 1);
}
private void doMergeSort(int lowerIndex, int higherIndex) {
if (lowerIndex < higherIndex) {
int middle = lowerIndex + (higherIndex – lowerIndex) / 2;
doMergeSort(lowerIndex, middle);
doMergeSort(middle + 1, higherIndex);
mergehalfs(lowerIndex, middle, higherIndex);
}
}
private void mergehalfs(int lowerIndex, int middle, int higherIndex) {
for (int i = lowerIndex; i <= higherIndex; i++) {
tempMergArray[i] = resarray[i];
}
int i = lowerIndex;
int j = middle + 1;
int k = lowerIndex;
while (i <= middle && j <= higherIndex) {
if (tempMergArray[i] <= tempMergArray[j]) {
resarray[k] = tempMergArray[i];
i++;
} else {
resarray[k] = tempMergArray[j];
j++;
}
k++;
}
while (i <= middle) {
resarray[k] = tempMergArray[i];
k++;
i++;
}
}
}

To further give an understanding of this topic, a revisit shall be done in the near future.
Knowledge is power, now you wield it.

Gichuki P. Mwangi

A computer scientist with a passion to solve real world, day to day problems using new computer technologies and those already in existence.

Leave a Reply

Your email address will not be published. Required fields are marked *