lundi 23 décembre 2013

Asymptotic Analysis - Approaching Algorithms to Mathematics (I)

Complexity theory is the field of mathematics that allows to determine the asymptotic order of growth of a given mathematical function.

Let's take a look first at different possible orders of growth:



We notice that n! is the most expensive order of growth in this plot; indeed, it takes a very large number of seconds, or even minutes, for instance, to execute an input of size n = 10. whilst 10n (the cheapest order of growth) would take less than a hundred seconds to execute an input of the same size (n = 10).

Moreover, we notice, for example, that 2n² is slower than 20n within the interval [0 .. 10[, but eventually do intersect when n = 10. In other words, an algorithm can be faster than an other one, when values are small, which might be misleading and deceiving.

Thanks to complexity theory, determining the order of growth of any mathematical function (remember: any algorithm can be represented as such), helps to formally decide whether the algorithm we are going to use is suitable or not.

So, how do we formally prove the order of growth?
We make use of the following fundamental notations below:

- O(n): Big Oh of n         --> The upper bound
- Ω(n): Big Omega of n   --> The lower bound
- Θ(n): Big Theta of n     --> When the upper bound and lower bound are alike

Below the formal analysis:
- T(n)  O(f(n)) iff there exist c & n0 > 0 such that T(n) ≤ cf(n) when n > n0 (upper bound);
- T(n)  Ω(f(n)) iff there exist c & n0 > 0 such that T(n) ≥ cf(n) when n > n0 (lower bound);
- T(n)  Θ(f(n)) iff T(n)  O(f(n)) and T(n)  Ω(f(n)) (upper and lower bound);
- T(n)  o(f(n)) iff T(n) ∈ O(f(n)) and T(n) not in Ω(f(n)) (upper but not lower bound).

Let's take advantage of the execution time of the plain for loop, covered in a precedent post: 3n + 2

Upper bound:


Lower bound:



Plotting the abovementioned, yields the following curves:


It is obvious that T(n) = 3n + 2's order of growth is linear, since its prevailing term is n; thus the intuitive choice of O(n). As a matter of fact, as long as T(n) is O(n), therefore, it is O(n²), O(n3), O(n4) and so forth. We can assert exactly the same way, but the other way around, that T(n) is Ω(n), Ω(√n), and then Ω(n1/3), Ω(n1/4), Ω(log2(n)) and so on.

On the other hand, we may notice that T(n) is O(n) and T(n) is Ω(n), therefore, we may use Theta notation for T(n) like the following:




The previously covered for loop fragment will execute (3n + 2) times, no matter what the value of n is.

dimanche 8 décembre 2013

Delving into Algorithm Analysis - Deducing the Mathematical Representation of a Determined Study Case (III) [Recursive Algorithms and Recursive Relations]

We have seen previously how could represent an iterative algorithm as a mathematical function.
But how are we going to do so for recursive algorithms?
Let's take a look at the renowned recursive algorithm below:


void hanoiTowers(int n, char left, char center, char right) {
     if (n == 0) {     // Base Case
          return;
     } else {          // General Case
           hanoiTowers(n - 1, left, right, center);
           printf("\nDisk: %d from %c to %c", n, left, center);
           hanoiTowers(n - 1, right, center, left);
     }
}
We notice that there are two unconditional recursive calls inside the hanoiTowers() routine.

I invite you to attempt to execute the following algorithm, once with n = 10 and once with n = 30:
void hanoiTowers(int n) {
     if (n == 0) {     // Base Case
          return;
     } else {          // General Case
           hanoiTowers(n - 1);
           hanoiTowers(n - 1);
     }
}

When n = 10, this algorithm executed in a few milliseconds, but when n = 30, it took 12 seconds. (intel Core i5 - 4 Threads, 6 GB memory).

Actually, the conventional technique (recursive relations) to solve this is like the following:



Where c is constant representing the running time it takes to execute the printf() statements.



We will assume that a = 1, and c = 1




Thus, this algorithm running time is non polynomial (very expensive algorithm).





Now, it is known how to infer "mathematical representation" of both recursive and iterative algorithms, let's dig into time complexity a little bit, in the next posts.

mercredi 4 décembre 2013

Delving into Algorithm Analysis - Deducing the Mathematical Representation of a Determined Study Case (II) [Iterative Algorithms and Sigma Notation]

In the precedent post, we concluded that the following code fragment:
     for (i = k; k <= n; i += inc) {
         /*
          * instructions
          */
     }
is equivalent to the following mathematical representation:
Let's find out what the above series is equal to (replace "instructions" by c [short of constant]).

Here, we have finally obtained the mathematical representation, the shape, or representation of the code above.

Practical case - The plainest mundane for loop:

     for (i = 1; k <= n; i ++) {
         
     }
Let's manually get the exact number of instructions via the elaborated while loop
     i = 1;                // Executes 1 time
     while ( k <= n ) {    // Executes n + 1 times
         i = i + 1;        // Executes 2n times (addition and assignment)
     }
Let's sum up: the plain mundane for loop executes 1 + (n + 1) + 2n = 3n + 2
Therefore, we can represent our for loop code fragment like the following:
T(n) = 3n + 2

and this is how its plot looks like (for any n >= 0):



Why are we doing all this? Because we need to determine the order of growth.
The order of growth is the currency by which a programmer may value whether an algorithm is expensive or "affordable". It helps to decide if the programmer should strive to come up with a better solution.
It allows to predict the algorithm's performance for small and large values (in how many nanoseconds, for instance, an algorithm is going to take to execute with 'n' values).

Be ready to get introduced to asymptotic analysis!

mardi 3 décembre 2013

Delving into Algorithm Analysis - Deducing the Mathematical Representation of a Determined Study Case (I) [Iterative Algorithms and Sigma Notation]

First of all, it is pointless to try to study a constant time algorithm (see isFibonacci() routine below), so we can skip this situation.

For example:
short isFibonacci(int number) {
      int value = 5 * number * number;
      return sqrt(value + 4) == number 
      ||     sqrt(value - 4) == number;
}

Actually, analyses become interesting when we are to manipulate iterative algorithms and recursion.
Indeed, algorithm analysis will merely help us to decide whether the solution we opted for is valid, because it is formally efficient; otherwise, we should try to persevere for extra enhancement.

For my personal experience, I came to realize that I can represent a for loop mathematically using Sigma notation, especially when the loop is regular, and is additionally incremental or subtractively decremental.

Ascending loop:
    for ( i = k ; i < n ; i += inc ) {
         /*             
          * instructions
          */           
    }
Can be transliterated like the following:


Whereas the following loop (less than or equal):
    for ( i = k ; i <= n ; i += inc ) {
         /*             
          * instructions
          */           
    }
Is accurately represented this way:



Descending loop:
    for ( i = n ; i > k ; i -= inc ) {
         /*             
          * instructions
          */           
    }
Looks like this:



While the loop above:
    for ( i = n ; i >= k ; i -= inc ) {
         /*             
          * instructions
          */           
    }
Would too be translated like the following:


A loop whose increment is an exponent (whether multiplied or divided) is called an logarithmic loop:
    for ( i = k ; i < n ; i *= m ) {
         /*             
          * instructions
          */           
    }
Would be mathematically represented like:




Again, when the less or equal is stated:
    for ( i = k ; i <= n ; i *= m ) {
         /*             
          * instructions
          */           
    }
We end up having:




The same for the other way around case:
    for ( i = n ; i > k ; i /= m) {
         /*             
          * instructions
          */           
    }
Is to be represented this way:




Doing the same when it comes to "less or equal" condition:
    for ( i = n ; i >= k ; i /= m ) {
         /*             
          * instructions
          */           
    }
We get:



This is a preliminary overview that I am sure will help to predict what is going to be covered within the next posts.
These slides from Dr. Jauhar Ali can provide further knowledge about this matter.

lundi 2 décembre 2013

Algorithms - a Debut (III) [Algorithm Analysis - The Gist!]

Grasping algorithmic notions utilizing a programming language, along with data structures are enough to engage into writing impeccable computer programs and applications.
With a little of experience, a thoughtful programmer would express the need to acquire an extra level of knowledge, so that s/he could assess the quality of the code s/he yields. "How can I prove this program is optimal? How can I criticize it? Can I improve it?" are all questions our talented programmer would pose.
The picturesque case is the previously cited problem "The Towers of Hanoi", which we ascertained it is not easily implementable when opting for an iterative solution, whereas its recursive version is definitely easy. Further, approaching mathematics to "computer algorithms" would allow us to find out that "The Towers of Hanoi" recursive version is extremely expensive in both time and space.
Also, a very fertile algorithm analysis area is the "sorting algorithms". Deducing the time complexity (and sometimes space complexity as well), and inferring if such an algorithm is stable or not, are all aspects discoverable within the field of Algorithm Analysis, indeed.

samedi 30 novembre 2013

Algorithms - a Debut (II) [Basic Algorithm and Data Structures Courses]

A basic algorithm course is about building up the abstract steps intended to solve a specific quandary. It introduces the going-to-be programmer to the fundamental tools mundanely utilized, namely reading from the standard input, writing on the standard output, conditional control structure, iterative control structure, and of course a trivial introduction to scalar data types (int [short], char, real [float, double], and boolean). The accompanying programming course is to concretize the aforementioned.
Further, the importance of data structures (their prerequisite are the scalar data types) appear when a beginner programmer has to move to "next level": manipulating arrays. Arrays allow to gather homogeneous values within one variable at run-time.
Niklaus Wirth made use of a very, very critical equation to entitle his book (Algorithms + Data Structures = Programs), in the 1970s already.
A data structures course is supposed to introduce students to the plethora of ways to organize data before engaging into its algorithmic solution.
The fate of a program's performance is fundamentally based on the choice of the data structure.
A virtuoso programmer may succeed to achieve the intended results most of the time, but might be surprised when their solution is adopted within a production environment, when the algorithm is going to be exposed to data of all kinds (vertically and horizontally).
A gullible programmer is the one who would try to solve the Towers of Hanoi using arrays. A sophomore student in Computer Science (recently introduced to recursion) might think that the recursive solution of the Towers of Hanoi problem is a perfect suggestion.
Would Facebook have been as efficient as it is, if any data structure other than Graphs was chosen?

Algorithms - a Debut (I)

Have you ever realized that Algorithms are omnipresent in our daily life?
For instance, reckoning bills and coins, consuming a beverage in a café, or taking the bus back and forth, are actions that involve a sequence of endeavors performed with the aim to achieve an eventual purpose.

Philosophically, I hope it is eligible to assert that an algorithm could be described as "Meta-Actions": Actions about Actions (imitating the definition of Meta-Data: Data about Data).

Nowadays, computer programmers are the main population that is concerned, or haunted, to some extent, by the consumption of the rules and laws offered by the field of Algorithms, to produce solutions whenever applicable, within the obfuscated realm of zeros and ones.

Indeed, a computer programmer in the twenty first century is someone who should acquire a training in basic algorithm, combined with a programming language (distinct courses, respectively), data structures, algorithm analysis along with, for instance, computer architecture, operating systems, compilers, and/or many more ...

vendredi 29 novembre 2013

Prelude - Etymology of Algorithm

Algorithm? What is Algorithm? More precisely, What is the origin of the word itself?

Let's analyse the word, before we analyse what it vaguely refers to as a field.

Dissecting the word: Algo + Rithm ?

The prefix Algo-:
Listing a few words in the dictionary, I encountered the word "Algology", which means "the branch of botany that studies algae" wordweb. Wrong track for sure.

The suffix -Rithm:
Phonetically, it sounds like Rhythm ... Intuitively, we might subjectively be leaned to provide an explanation related to "something recurring at regular intervals" wordweb. Yes, Rithm and Rhythm are two distinct words that have nothing in common, except the partial homonymy.

Dr. Rashid Bin Muhammad, the Computer Science professor at the University of Kent, included in the page of his Design and Analysis of Algorithm course, the picture and the name of an ancient scientist (born in Baghdad) like the following:

Abu Ja'far Muhammad ibn Musa Al-Khawarizmi


780 - 850
B.C.

Al-Khawarizmi, indeed, is the founder of the field of Algorithms, and that's from where the word came.
Conclusion, "The word algorithm is derived from the Latinization of his name" source.