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?

Commentaires

Enregistrer un commentaire

Posts les plus consultés de ce blog

Logarithmic Summations and Discrete Loops - Ceiling and Floor Functions

Image
Reading the so called paper " Discrete Loops and Worst Case Performance " ( by Dr. Johann Blieberger ), I came across some interesting summations: Useful here: for ( i = 1; i <= n ; i ++ ) { for (j = 1; j <= i ; j *= 2) { // Some constant time C instructions. } } Because: Likewise: Applicable here: for ( i = 1; i <= n ; i ++ ) { for (j = 1; j < i ; j *= 2) { // Some constant time C instructions. } } Because: And more generally: for ( i = 1; i <= n ; i ++ ) { for (j = 1; j <= i ; j *= a) { // Some constant time C instructions. } } We can proceed like the following: Further: for ( i = 1; i <= n ; i ++ ) { for (j = 1; j < i ; j *= a) { // Some constant time C instructions. } } With: Thus, while I tried to refine the results of some nested loops running time analysis, I had to face a particul...
Lire la suite

Indirect Recursion - A Natural Phenomenon

Image
Indirect recursion could be noticed in seeds and trees: a seed ends up to be a tree, and the latter produces many seeds, which themselves become trees and so forth. An interesting case was beautifully described in the Qur'an, chapter 2, verse 261, a plain description that is easy  to represent: " The example of those who spend their wealth in the way of Allah is like a seed [of grain] which grows seven spikes ; in each spike is a hundred grains. And Allah multiplies [His reward] for whom He wills. And Allah is all-Encompassing and Knowing ". ( Source ). Regardless of the religious aspects, one can notice the exponential growth of seeds, which is appreciated in agriculture, but seriously deprecated in Computer Science. If we represent this phenomenon (seeds and spikes) as a Java algorithm: void seed(x) { System.out.println("Seed " + x); for (i = 0; i < 7; i ++) { spike(i); } } void spike(y) { System.out.println("Sp...
Lire la suite

Triple Nested Loops - Two Linear Loops and One Logarithmic with a non-Constant Base - The Monster

Image
To obtain the function that tells the exact number of iterations a set of nested loops would perform didn't seem to be a tedious exercise. However, I came accross this interesting case: - Linear outer loop - Dependent first level linear inner loop - Dependent second level logarithmic inner loop with a general base. for ( i = 1 ; i <= n ; i ++ ) { for ( j = 1; j <= i ; j ++ ) { for ( k = 1 ; k <= j ; k *= a ) { // c } } } Ceilinged/Floored logarithmic functions within summations turned out to have very lengthy closed-forms (See my previous post). We will dissect the formulas above (for any a > 1 and n >= 1): Therefore, This link  points at a  plain   Java program that represents the above functions (f(), g () , h () , u () , v () , w () , respectively), and give the exact number of iterations performed by the covered algorithm mentioned earlier (receives two a...
Lire la suite