What is an algorithm?
We all hear algorithm so often when doing a simple multiplication or a complicated calculus problem, but what does algorithm mean exactly?
The word algorithm itself originally comes from Medieval Latin algorismus, and east from Greek arithmos which means “number”. It seems that it is also influenced by the name of the 9th Century Persian mathematician Al-Khwārizmī who wrote about calculations, and when his work was translated into Latin 300 years later, his name was somehow incorporated into the name of the process as Algoritmi. This became confused with the Greek word for number, leading to the evolution of the word as we know it.
In mathematics, logic, computer science and related disciplines, an algorithm is a finite series of defined, computer-implementable and unambiguous instructions or rules that typically allow solving a problem, computing, processing data, automated reasoning and carrying out other tasks or activities.
Interestingly, algorithms are not just used in mathematics and computer science but are also widely used in many aspects in our daily life. For instance, user manuals apply algorithms to guide people to use electrical appliance like a cooker, or a dish washer. At work, an electrical technician can follow the instructions which also are made by algorithms step by step to perform maintenance on a transformer. In other words, algorithm is nothing more than a method of solving a problem or accomplishing things by taking steps.
Algorithms in computer programming
Just as in real life, to get a computer to do a task, we need to write a computer program to tell the computer, step by step, exactly what we want it to accomplish. The computer then reads the program and executes the commands shared in it by following each step mechanically in order to complete the said task. This set of related commands or steps is a computer algorithm.
There are many types of algorithms available in computer science, which means most of the time there are many solutions with different steps of solving a specific problem. Generally speaking, algorithms can be classified into six categories based on their kay features and functionalities.
Greedy algorithm
A greedy algorithm is an algorithmic strategy that makes the best optimal choice at each small stage with the goal of this eventually leading to a globally optimum solution. This means that the algorithm picks the best immediate solution at the moment without regard for consequences, therefore it is considered greedy.
Dynamic Programming algorithm
Dynamic programming algorithm is a technique that breaks complex problems into a collection of multiple simpler sub-problems, and stores the result for future purposes to avoid repetitive computations. The subproblems are optimized to optimize the overall solution which is known as optimal substructure property.
Divide and Conquer algorithm
Divide and Conquer algorithm breaks down a problem into two or more subproblems of the same or related type, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem. Normally, it follows these three steps:
Divide the problem into a number of subproblems that are smaller instances of the same problem.
Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
Combine the solutions to the subproblems into the solution for the original problem.
Recursive algorithm
Recursive algorithm is a method of simplification that divides the problem into sub-problems of the same nature. The result of one recursion is the input for the next recursion. The repletion is in the self-similar fashion. The algorithm calls itself with smaller input values and obtains the results by simply performing the operations on these smaller values. Generation of factorial, Fibonacci number series are the examples of recursive algorithms.
Brute Force algorithm
Brute Force algorithm is a trial and error methodology, which is used by attackers to break into any website’s data or systems. They try to steal information by generating every possible combination of the password-protected information. Brute Force relies on the computational power of the machine to try every possible combination to achieve the target.
It is also known as Exhaustive Search or Generate and Test that yields all possible solution of the problem. It is a simple problem solving technique that is easy to implement and will always come up with a solution if exists. The computational cost of Brute Force algorithm is directly proportional to the number of candidate solutions, for example it grows as quickly as the problem size increases. Therefore, it is ideal to use when the problem size is limited and small and does not have complex and large problem sets.
Backtracking algorithm
Backtracking is an algorithmic technique where the goal is to get all solutions to a problem using the brute force approach. It consists of building a set of all the solutions incrementally. Since a problem would have constraints, the solutions that fail to satisfy them will be removed.
It uses recursive calling to find a solution set by building a solution step by step, increasing levels with time. In order to find these solutions, a search tree named state-space tree is used. In a state-space tree, each branch is a variable, and each level represents a solution.
A backtracking algorithm uses the depth-first search method. When it starts exploring the solutions, a bounding function is applied so that the algorithm can check if the so-far built solution satisfies the constraints. If it does, it continues searching. If it doesn’t, the branch would be eliminated, and the algorithm goes back to the level before.
Top comments (0)