Turki @ CMUQ
Theory and algorithms
Algorithms
Etymology of the word “Algorithm”:
The Persian astronomer and mathematician, Al-Khawarizmi, wrote a treatise in Arabic called “On Calculation with Hindu Numerals”. When it was translated to Latin its title became “Algoritmi de numero Indorum” (“Algoritmi on the numbers of the Indians”, Algoritmi was the transliteration of Al-Khawarizmi), but some people misunderstood Algoritmi as a Latin plural; thus the word “algorithm” was born to mean “calculating method”.
Current meaning of the word “Algorithm”:
While no generally accepted formal definition exists yet, the word is commonly used to refer to a program that computes something in a number of steps that may contain flow control elements like loops or conditions. A prototypical example is Euclid's algorithm to determine the maximum common divisor of two integers greater than one: "subtract the smallest number from the biggest one, repeat until you get a zero or a one"[1].
Currently, algorithms expand to cover more problems than pure mathematical ones. For example one can create an algorithm that makes financial decisions based on the current situation.
Notation of algorithms:
There are a number of ways to express an algorithm:
-
Natural languages: The most obvious and natural way to describe an algorithm. While it's a fast and easy way to describe algorithms, this method of expression becomes too ambiguous for non-trivial algorithms making it useless in those cases.
-
Example: “Let counter and sum be 0. While counter is less than ten: add counter to sum and increment counter by one.”.
-
-
Pseudocode (Pretend code): A more practical way of describing the algorithm in a way that resemble actual code (it's not code). The reader must be familiar with the basic concepts of programming to be able to comprehend it.
-
Example:
let counter=0
let sum=0
while counter<10
do
sum = sum + counter
counter = counter + 1
done
-
-
Flowcharts: A very effective way to represent algorithms to most people (since there are visual guides), but could become confusing when describing algorithms with a lot of branches.
-
Example: (source: wikipedia.org)
-
-
Programming languages: This way of expressing an algorithm to a computer to be executed. It's limited by the chosen programming language, but it's still a very powerful way since result can be computed almost instantly in most cases.
-
Example:
int counter=0, sum=0;
while(counter<10){
sum+=counter;
counter++;
}
System.out.println(sum);
-
Questions:
-
What's turing-completeness?
-
Is there infinite algorithms in nature?
-
How do you deal with vague concepts when writing algorithms?
-
Are there any problems that can't be described with algorithms?
-
Can algorithms be applied on problems with great uncertainties (eg. human interaction with each other)?