Introduction to Algorithm

[ Home Page ]  [ Back ]  [ Content of Contributions ]  [ Movement: Green Leaf World ]

------------------------------------------------------------------------------------------------------------------

Problem & Solution?

In our Computer Science & Engineering, a problem may be treated as a set of values(say P) which are available to you at certain time t, but it is not the desired value set that you need.

Let, the desired value set be S. If S can be obtained from P somehow, then P may be called a Problem and S is the solution to the problem P. 

The way to calculate the desired set S from the given set P may be called Method. A Method can be represented by means of Flowchart or Pseudo Code.

Example:

Let, we have an integer X, and we want to find the set F which will contain all the factors of X.

Certainly, for X=100, F will be {1, 2, 4, 5, 10, 20, 25, 50, 100}.

Let, the method of calculating F is named as Factor_Calculator. So, the method should take X as Input and should generate the set F as Output.

Thus, the method Factor_Calculator must be represented as,

Factor_Calculator(X, F) with proper specification of X and F, so that, someone can understand the relationship between the Input & the Output.

Obviously, to calculate/ generate the set F from the given set X we need at least one or more operations. When there will be more than one operations, certainly there must be a sequence in the operations to get F properly, as we have seen earlier in the arithmetic using BODMAS rule

Definition of Algorithm:

A definite set of finite number of steps/ statements(logical or mathematical ) in a particular sequence to accomplish a predefined and particular task, such that, every steps should be computed within a finite amount of time, may be called an algorithm. 

Properties of an Algorithm:

An algorithm should have the following properties

1. Input: An algorithm should have zero/ more explicit inputs.
2. Output: An algorithm must have at least one/more output.
3. Definiteness: Each step/ statement of an algorithm must be precisely defined without any confusion.
4. Finiteness: Each step/statement of an algorithm must be computed in finite amount of time.
5. Effectiveness: An algorithm must be effective, i.e. it should be computed using pencil & paper by a human being, may be taking too long time but not infinite.
6. Correctness: An algorithm must produce correct result within its specified domain.

Note that, when a method does not satisfies the definiteness property it may be called Procedure.

Steps for Solving a Problem in View of Computer Science & Engineering:

The followings are the basic steps to solve a problem-

1. Problem Statement: Generally, a set of statements is given by the client. May be a question in the laboratory or examination hall in our education system.
2. Analysis of Requirements: Finding number of values required for the specific computation as input. Nature of each input values. Finding number of outputs and also nature of the output values .
3. Problem Specifications: Define each of the input and output values specifically in terms of their nature. Also, state proper assumptions if required to ensure validity of the values. Consider a problem statement "perform X+Y". Assumptions may be taken as, (1) Z is the output, (2) X, Y, Z are the integer quantity. Assumption 2 is useful to validate the data value X & Y.
4. Design of Algorithm: Finding one efficient solution. This is our main target in this documentation.
5. Data Structure: Specification of the suitable Data Structure for the set of values required to implement the algorithm (Input, Output & temporary values) depending on the behavior of the values.
6. Program Code: Selection of the Programming Language & Coding to ensure the automation of the algorithm.
7. Testing: Testing of the program code w.r.t the specification of the Input/Output in the Algorithm designed.

Note That, Documentation of every steps stated above is very important w.r.t the future uses or modification or up gradation of the system(software/ a simple program).

There are so many things with the algorithm, those will be discussed in the later sections under this topic(Algorithms & its Analysis). You may note the following topics for future references-

1. A problem can be solved using iterative or recursive algorithm.
   
2. Complexity of an algorithm is one important part of analysis of an algorithm. This property shows the efficiency of an algorithm.
3. There are so many classifications of Problems, like
1. Decision problem
2. Satisfiability problem
3. Optimization problem
4.  etc
4. There are many types of algorithms like,
1. Divide and Conquer algorithm
2. Greedy Algorithm 
3. Backtracking
4. Branch & Bound
5. Approximate algorithm
6. Heuristic algorithms
7. Genetic algorithms
8. Dynamic Programming
9. Ant colony Optimization
10. Mimetic Algorithm
11.  Simulated annealing
12.  etc.