Concept of Algorithm

Concept definition of algorithm

Informally, algorithm is simply a method of solving problem which can be implemented on a computer. The term algorithm has no root meaning. According to the American Heritage Dictionary, it is derived from the name of Muhammad ibn Musa al-Khwarizm (780A.D850A.D), a Muslim mathematician whose works introduced Arabic numerals and algebraic concepts to Western mathematics. The word “algebra” stem from the title of his book Kitab al jabr wa’l-muq’abala. The concept meaning of algorithm has come to be accepted as: set of step-by-step instructions for solving a well-defined problem which takes allowable inputs to produce desired output. In other words, an algorithm consists of a set of unambiguous instructions that take one or more acceptable inputs to produce desired output. This definition emphasize that an algorithm must consists of:

        i.            Set of instructions that can be followed, typically by a computer when implemented in computer language.

      ii.            Algorithm takes acceptable data as input.

    iii.            It produces desired output based on the input provided. If wrong input is provided, algorithm will not give correct output

The concept of algorithm is depicted in the diagram below;

One important concept in algorithm is that the problem solver must write explicitly all the instructions required to solve the problem without assumptions. In fact, if a problem solver cannot express the concept clearly, the algorithm will not be useful to solve the problem. Consider a problem to find the largest of three numbers. Almost anyone can immediately tell which is the largest, but many cannot explain the steps they followed to arrive at it. Most people will be exclaimed, “I just know it!”. However, an algorithm approach desires the steps to be clearly and unambiguously stated. This is what separate algorithm from ordinary human intuition, as human intuition is an impression that something might be the case.

The algorithm is stated below.

Step 1: Enter the three numbers say a,b,c.

Step 2: If a>b then go to step 3 else go to step 4

Step 3: If a>c then a is largest go to step 5 else c is largest go to step 5

Step 4: If b>c then b is the largest.

Step 5: stop

The role of algorithm in the problem-solving process

2.1 The problem solving process 

We can define problem solving as the act of getting a solution to a difficulty or constraint e.t.c. Then the steps followed in doing that is the process. There are different ways we human approach problem in trying to get a solution to it. There are so many ways towards which problems are perceived to be solved like; 

• By a way of natural endowment ( i.e We "just do it naturally")
• Guesswork-and-luck 
• Trial-and-error 

All the above mentioned ways to which problems might be solved are not the fore of concern when we talk about algorithms. Those are ways which are not systematically effective (ways that are not reliable i.e. cannot be true for every instance). However those that are systematically effective are useful to everyone. Examples of those systematic ways of solving problems include;

• Experience (possibly someone else's blue print or instructions to solving a particular problem, which is what algorithm is about).
• Using a process model: A process model defines scientific steps to which a problem is solved. Algorithm has a role to play in a systematic way of solving problem such as the problem solving process model.

2.2 Role of algorithm in problem solving process model

Figure 2: Shows the role algorithm plays in problem solving process model 

Algorithm plays a very important role in the problem solving process. In fact the algorithm step is where the procedure or instruction to getting a solution to a problem is designed. Figure 2 above proposes five (5) steps to which a problem can be solved and between the steps are activities that will occur. Steps include; 

Step 1: The problem: The problem is stated. The problem stated is analyzed to give a clear specification.

Step 2: The result of the analysis above translates into a more defined problem (i.e specified problem). With the problem specification, we can now move to design an algorithm.

Step 3: The algorithm: The algorithm step is the most important step to problem solving. It is, because; your instruction to getting a solution is designed here. Step 1 – Step 3 of this model are the most important steps. If your problem statement translation is wrong, your algorithm design will not yield a desired result to the problem. Steps 4 and 5 of the model are less important, depending on the method of implementation/representation you have chosen. Steps 4 and 5 of the process model is applicable if the algorithm is to be represented in a program using a particular programming language.

Step4: Program: At this step, the designed algorithm is implemented into a computer program. The program is compiled and executed to give a desired solution. 

Step5: At this step, a desired solution is proffered to the specified problem

2.3 The problem solving process is not linear

When we say a process is not linear we mean it is not one dimensional. A backtrack is done on certain activities of the process model. An example below;

Properties/Characteristics of a good algorithm

For an algorithm to be valid and executable by a computer, it must possess five key properties. These properties ensure the algorithm is reliable, predictable, and effective.

The Five Essential Properties

1. Finiteness (Termination): The algorithm must terminate after a finite number of steps. It cannot run forever.

Why it matters: An infinite loop is useless for solving a problem. The computer must eventually stop and produce a result.

Example: An algorithm to find the smallest number in a list will check each item once and then stop. An algorithm that says "repeat step 2 forever" violates finiteness.

2. Definiteness (Unambiguousness): Each step of the algorithm must be precisely defined and clear. There should be no room for ambiguity or multiple interpretations.

Why it matters: A computer cannot make guesses or assumptions. Every instruction must be exact.

Example: The step "Add a pinch of salt" is ambiguous. A definite step is "Add 5 grams of salt." In programming, this means every statement (like x = y + z) has a single, clear meaning.

3. Input: An algorithm has zero or more well-defined inputs. These are the values supplied to the algorithm before it begins.

Why it matters: Inputs provide the data the algorithm will process. An algorithm without input typically just produces a constant output.

Example: An algorithm for sorting requires an input list of numbers. An algorithm to calculate pi might have no inputs.

4. Output: An algorithm must have one or more well-defined outputs, which have a specified relation to the inputs.

Why it matters: The output is the solution to the problem. An algorithm without an output has not solved anything.

Example: The sorting algorithm must output the sorted list. A search algorithm must output the position of the item or a "not found" message.

5. Effectiveness (Feasibility): Every operation in the algorithm must be basic enough that it can be done exactly and in a finite amount of time. The steps must be "computable."

Why it matters: The algorithm must be practically executable with the available resources.

Example: "Find the largest prime number" is not effective because there is no largest prime the task is infinite. However, "Find the largest prime number less than 100" is effective because the steps (checking divisibility for numbers up to 100) are basic and finite.

Methods of implementing algorithms

Methods of implementing algorithms imply the same as methods of representing or specifying algorithms. It means those methods an algorithm (i.e. an instruction) can be presented in. They include;

1. Flow Charts: A graphical representation of instruction
2. Pseudo-code (not executable because it does not follow appropriate syntax of any programming language. Written in mixture of commands and words) 
3. Computer program: Could be written in any programming language like java, C++, VB, PHP…and so on. The instruction is executable because an instruction written in a computer program follows certain programming language syntax. 
4. Decision table and tree: A graphical representation of instruction
5. Mathematical formulas 
6. Natural language: E.g. English representation of instruction. May also be in other spoken languages (can be in structured or unstructured sentences)

Now let’s look at some examples on methods of implementing algorithms; Problem 1: Find the area of a circle with radius=4. Algorithm: Let’s make a representation of the instruction for the above problem in a simple mathematical formula. The solution will look like these

Problem 2a: How to change motor oil Algorithm: let’s try to represent the algorithm instruction for the stated problem in a natural language description e.g English. Plain English description: Algorithm instruction for the problem stated will look like the following if represented in plain or unstructured English.

Problem 2b: The old world puzzle [the peasant problem] “A peasant finds himself on a riverbank with a wolf, a goat and a cabbage. He needs to transport all three to the other side of the river in his boat. However, the boat has room for only the peasant himself and one other item (either the wolf, the goat, or the cabbage). In his absence the wolf would eat the goat, and the goat would eat the cabbage. (Note: the peasant is a vegetarian but does not like cabbage and hence can eat neither the goat nor the cabbage)” 

Algorithm: Algorithm instruction for the peasant problem represented in structured English

Step 1: Starting from the initial point (i.e point of peasant, wolf, goat and the cabbage), the peasant pick goat only with him to cross to the other side of the river 

Step 2: Peasant return empty to the initial point to pick the wolf with him to cross to the other side of the river 

Step 3: Peasant return to the initial point picking the goat along. 

Step 4: Peasant drops the goat and pick the cabbage with him to cross to the other side of the river 

Step 5: Peasant will return empty to the initial point and pick the goat with him to cross to the other side of the river 

Step 6: Stop

Solvable vs. Unsolvable Problems

Solvable Problems: A problem is considered solvable if an algorithm exists that can solve all instances of that problem correctly in a finite amount of time. Examples are:

        i.            Sorting a list of numbers

      ii.            Finding the shortest path between two points on a map.

    iii.            Determining if a number is prime etc.

A problem can be solvable even if we haven't found the most efficient algorithm for it yet. The key is that some algorithm is proven to exist.

Unsolvable Problems: A problem is considered unsolvable (or undecidable) if it is logically impossible to create an algorithm that can solve all instances of that problem. These limitations are not due to a lack of human ingenuity or computing power but are fundamental consequences of mathematical logic and the theory of computation, as proven by Alan Turing and others.

The Halting Problem: A Famous Unsolvable Problem

Problem Statement: Can we write a program H that takes another program P and its input I as input, and correctly determines whether P will eventually halt (finish running) or run forever when given input I?

Alan Turing's Proof (1936): Turing proved, through a brilliant logical contradiction, that no such general-purpose program H can ever exist.

Simplified Idea: Assume H exists. Then, we could create a program C that uses H on itself. If H says C halts, then C is designed to run forever, and vice versa. This contradiction means our initial assumption (that H exists) must be false.

Significance: The Halting Problem was one of the first problems proven to be undecidable. It shows there are inherent limits to what computers can do, no matter how powerful they become.

Other Examples of Unsolvable Problems:

Equivalence Problem: Determining if two arbitrary programs produce the same output for all inputs.

Entscheidungsproblem ("Decision Problem"): Determining whether a given statement of first-order logic is universally valid.