Details in Algorithm

                                   Algorithm

●Definition of Algorithm

Algorithm can be defined as "A sequence of steps to be carried out for a required output from a certain given input". There are 3 main features of algorithm from its definition:

The essential aim of an algorithm is to get a specific output,

An algorithm involves with several continuous steps,

The output comes after the algorithm finished the whole process.

●Algorithm Analysis

Efficiency of an algorithm can be analyzed at two different stages, before implementation and after implementation. They are the following −

A Priori Analysis − This is a theoretical analysis of an algorithm. Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation.

A Posterior Analysis − This is an empirical analysis of an algorithm. The selected algorithm is implemented using programming language. This is then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected.

We shall learn about a priori algorithm analysis. Algorithm analysis deals with the execution or running time of various operations involved. The running time of an operation can be defined as the number of computer instructions executed per operation.

●Expressing Algorithms

Describing algorithms requires a notation for expressing a sequence of steps to be performed. The three most common options are (1) English, (2) pseudocode, or (3) a real programming language. Pseudocode is perhaps the most mysterious of the bunch, but it is best defined as a programming language that never complains about syntax errors. All three methods can be useful in certain circumstances, since there is a natural tradeoff between greater ease of expression and precision. English is the most natural but least precise language, while C and Pascal are precise but difficult to write and understand. Pseudocode is useful because it is a happy medium.    

The correct choice of which notation is best depends upon which of the three methods you are most comfortable with. I prefer to describe the ideas of an algorithm in English, moving onto a more formal, programming-language-like pseudocode to clarify sufficiently tricky details of the algorithm. A common mistake among my students is to use pseudocode to take an ill-defined idea and dress it up so that it looks more formal. In the real world, you only fool yourself when you pull this kind of stunt.

The implementation complexity of an algorithm is usually why the fastest algorithm known for a problem may not be the most appropriate for a given application. An algorithm's implementation complexity is often a function of how it has been described.   Fast algorithms often make use of very complicated data structures, or use other complicated algorithms as subroutines. Turning these algorithms into programs requires building implementations of every substructure. Each catalog entry in Section  points out available implementations of algorithms to solve the given problem. Hopefully, these can be used as building blocks to reduce the implementation complexity of algorithms that use them, thus making more complicated algorithms worthy of consideration in practice.

●Types of Algorithm

It is not surprising that algorithms are widely used in computer programming. However, it can be applied to solving mathematical problems and even in everyday life. Here come a question: how many types of algorithms? According to Dr. Christoph Koutschan, a computer scientist working at the Research Institute for Symbolic Computation (RISC) in Austria has surveyed about voting for the important types of algorithms. As a result, he has listed 32 important algorithms in computer science. Despite the complexity of algorithms, we can generally divide algorithms into 6 fundamental types based on their function.

1. Recursive Algorithm

It refers to a way to solve problems by repeatedly breaking down the problem into sub-problems of the same kind. The classic example of using recursive algorithm to solve problems is the Tower of Hanoi.

2. Divide and Conquer Algorithm

Traditionally, the divide and conquer algorithm consists of two parts: 1. breaking down a problem into some smaller independent sub-problems of the same type; 2. finding the final solution of the original problems after solving these smaller problems separately.

The key points of the divide and conquer algorithm are:

If you can find the repeated sub-problems and the loop substructure of the original problem, you may easily turn the original problem into a small simple problem.

Try to break down the whole solution into various steps (different steps need different solutions) to make the process easier.

Are sub-problems easy to solve? If not, the original problem may cost lots of time.

3. Dynamic Programming Algorithm

Developed by Richard Bellman in the 1950s, the dynamic programming algorithm is generally used for optimization problems. In this type of algorithm, past results are collected for future use. Similar to the divide and conquer algorithm, a dynamic programming algorithm simplifies a complex problem by breaking it down into some simple sub-problems. However, the biggest difference between them is that the latter requires overlapping sub-problems, while the former doesn’t need to.

4. Greedy Algorithm

This is another way of solving optimization problems – greedy algorithm. It refers to always finding the best solution in every step instead of considering the overall optimality. That is to say, what he has done is just at a local optimum. Due to the limitations of the greedy algorithm, it has to be noted that the key to choosing a greedy algorithm is whether to consider any consequences in the future.

5. Brute Force Algorithm

The brute force algorithm is a simple and straightforward solution to the problem, normally based on the description of the problem and the definition of the concept involved. You can also use "just do it!" to describe the strategy of brute force. In short, a brute force algorithm is considered as one of the simplest algorithms, which iterates all possibilities and ends up with a satisfactory solution.

6. Backtracking Algorithm

Based on a depth-first recursive search, the backtracking algorithm focusing on finding the solution to the problem during the enumeration-like searching process. When it cannot satisfy the condition, it will return “backtracking” and tries another path. It is suitable for solving large and complicated problems, which gains the reputation of the “general solution method”. One of the most famous backtracking algorithm example it the eight queens puzzle.