Introduction to Big O Notation

Different Types of Algorithms in Data Structure.

What is Algorithm?

An Algorithm is a sequence of steps that describe how a problem can be solved. Every computer program that ends with a result is basically based on an Algorithm. These can also be used to solve mathematical problems and on many matters of day-to-day life. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language.

The Algorithm are different Categories which are described as below:

1. Search − Algorithm to search an item in a data structure.
2. Sort − Algorithm to sort items in a certain order.
3. Insert − Algorithm to insert item in a data structure.
4. Update − Algorithm to update an existing item in a data structure.
5. Delete − Algorithm to delete an existing item from a data structure.

These are the categories by which every problem become easy and can easily solved.

How to Write an Algorithm?

here are no well-defined standards for writing algorithms. Rather, it is problem and resource dependent. Algorithms are never written to support a particular programming code.

As we know that all programming languages share basic code constructs like loops (do, for, while), flow-control (if-else), etc. These common constructs can be used to write an algorithm.

We write algorithms in a step-by-step manner, but it is not always the case. Algorithm writing is a process and is executed after the problem domain is well-defined. That is, we should know the problem domain, for which we are designing a solution.

Example

Let's try to learn algorithm-writing by using an example.

Problem − Design an algorithm to add two numbers and display the result.

**Step 1** − START

**Step 2** − declare three integers **a**, **b** & **c**

**Step 3** − define values of **a** & **b**

**Step 4** − add values of **a** & **b**

**Step 5** − store output of step 4 to **c**

**Step 6** − print **c**

**Step 7** − STOP

Algorithms tell the programmers how to code the program. Alternatively, the algorithm can be written as

**Step 1** − START ADD

**Step 2** − get values of **a** & **b**

**Step 3** − c ← a + b

**Step 4** − display c

**Step 5** − STOP

In design and analysis of algorithms, usually the second method is used to describe an algorithm. It makes it easy for the analyst to analyze the algorithm ignoring all unwanted definitions. He can observe what operations are being used and how the process is flowing.

Advantages and Disadvantages of Algorithms.

Advantages of Algorithm

1. It is a step wise representation of a solution for a give problem
2. Algorithm use a definite procedure
3. It does not depend upon any programming language which make algorithm easily understandable without any programming knowledge.
4. Every step in algorithm has logical reason so it can be easily debugged.
5. Algorithm divide the problem into smaller problems due to which every problem can easily solved.

Disadvantages of Algorithm

1. Algorithm is Time Consuming
2. Every problem cannot be converted into algorithm which makes it difficult
3. Difficult to show looping and branching in Algorithm

Types of Algorithms

Based on how they function, we can divide Algorithms into multiple types. Let’s take a look at some of the important ones.

1. Recursive Algorithm

This is one of the most interesting Algorithms as it calls itself with a smaller value as inputs which it gets after solving for the current inputs. In more simpler words, It’s an Algorithm that calls itself repeatedly until the problem is solved.

Example:

To find factorial using recursion, here is the pseudo code:

    Fact(x)
        If x is 0      /\*0 is the base value and x is 0 is base case\*/
            return 1
    return (x\*Fact(x-1))  /\* breaks the problem into small problems\*/

2. Divide and Conquer Algorithm

This is another effective way of solving many problems. In Divide and Conquer algorithms, divide the algorithm into two parts, the first parts divides the problem on hand into smaller subproblems of the same type. Then on the second part, these smaller problems are solved and then added together (combined) to produce the final solution of the problem.

Example:

Merge sort , Quick sort

3. Dynamic Programming Algorithm

These algorithms work by remembering the results of the past run and using them to find new results. In other words, dynamic programming algorithm solves complex problems by breaking it into multiple simple subproblems and then it solves each of them once and then stores them for future use.

Example:

Fibonacci sequence, here is the pseudo code :

Fib(n)
    if n=0
        return 0
    else
        prev\_Fib=0,curr\_Fib=1
    repeat n-1 times  /\*if n=0 it will skip\*/
        next\_Fib=prev\_Fib+curr\_Fib   
        prev\_Fib=curr\_Fib
        curr\_Fib=new\_Fib
    return curr\_Fib

4. Greedy Algorithm

These algorithms are used for solving optimization problems. In this algorithm, we find a locally optimum solution (without any regard for any consequence in future) and hope to find the optimal solution at the global level.

The method does not guarantee that we will be able to find an optimal solution.

The algorithm has 5 components:

• The first one is a candidate set from which we try to find a solution.
• A selection function which helps choose the best possible candidate.
• A feasibility function which helps in deciding if the candidate can be used to find a solution.
• An objective function which assigns value to a possible solution or to a partial solution
• Solution function that tells when we have found a solution to the problem.

Huffman Coding and Dijkstra’s algorithm are two prime examples where Greedy algorithm is used.

In Huffman coding, The algorithm goes through a message and depending on the frequency of the characters in that message, for each character, it assigns a variable length encoding. To do Huffman coding, we first need to build a Huffman tree from the input characters and then traverse through the tree to assign codes to the characters.

Example:

Huffman tree, Counting money

5. Brute Force Algorithm

This is one of the simplest algorithms in the concept. A brute force algorithm blindly iterates all possible solutions to search one or more than one solution that may solve a function. Think of brute force as using all possible combinations of numbers to open a safe.

Example:

1. Exact string

2. Matching algorithm

6. Backtracking Algorithm

Backtracking is a technique to find a solution to a problem in an incremental approach. It solves problems recursively and tries to get to a solution to a problem by solving one piece of the problem at a time. If one of the solutions fail, we remove it and backtrack to find another solution.

In other words, a backtracking algorithm solves a subproblem and if it fails to solve the problem, it undoes the last step and starts again to find the solution to the problem.

N Queens problem is one good example to see Backtracking algorithm in action. The N Queen Problem states that there are N pieces of Queens in a chess board and we have to arrange them so that no queen can attack any other queen in the board once organized.