Chapter 1: Introduction to algorithm and different types of algorithms

In this chapter we shall learn about:

1.1 what is an algorithm in generic way?

1.2 what is algorithm in terms of computer science?

1.3 Now let us understand the importance of algorithms?

1.4 What are the characteristics of a good algorithm?

1.5 What are different types of algorithms?

1.5.1 Brute force approach

1.5.2 Recursive approach

1.5.3 Dynamic Programming [DP]

1.5.4 Backtracking Algorithm

1.5.5 Greedy Approach

1.5.6 Divide and Conquer

When we think of algorithm, we think of a computer program that solves a problem. But, in day to day life we come across many things that might define an algorithm. It might be your daily routine when you go to college, or how you plan your weekends.

1.1 So now, what is an algorithm in generic way?

An algorithm can be defined as a finite step by step instructions to perform an operation.

For example:

Daily we follow below set of steps like:

Getting up
Getting ready
Go to school/office
Have lunch
Come back to home have dinner
Go to sleep

The above steps can be considered as an algorithm.

1.2 But what is algorithm in terms of computer science?

In computer science an algorithm might be defined as a finite step by step instructions to solve a computational problem in an efficient way.

If you take an example of ride sharing service, how does the system deicide that a cab near to you should be allocated, or how does google maps will calculate the time take for you to reach your destination accurately?

The solutions for all the above problems can be solved by using algorithms.

1.3 Now let us understand the importance of algorithms?

Algorithms will help you to solve a computational problem efficiently by applying different methods.
It will help you to make your program run faster.
It will help you to clear interviews.
It will help you to become good at competitive programming.

In the series of chapters, we shall be looking at different types of algorithms and data structures, that will help you to understand and able to solve different types of problems.

1.4 What are the characteristics of a good algorithm?

Finite steps: An algorithm should have finite number of steps.
Clear: An algorithm should be clear and easy to understand.
Efficient: An algorithm should be efficient in utilizing CPU resources.
An algorithm should avoid repetitive code by using recursion or dynamic programming.

1.5 What are different types of algorithms?

1.5.1. Brute force approach:

I this approach we find all the solutions to a problem. As a problem can have multiple solutions, by using this approach, we might get to the correct result, but will loose efficiency.

1.5.2. Recursive approach:

In this approach, we call the same function again and again. It is important to have a base condition or exit condition to come out of recursion loop, else it will go to infinite loop.

Care to be taken while using recursion as it uses more stack space, it might result in MLE error [Memory limit exceeded] for some problems while doing competitive programming.

1.5.3. Dynamic Programming [DP]:

DP is used for optimisation problems. DP algorithms are recursive in nature. In DP, we store the previous results. Then we use those previous results to find next result. We usually store the results in the form of matrix.

1.5.4. Backtracking Algorithm:

This algorithm is similar to DP, but the main difference is we store the result in a Boolean matrix.

1.5.5. Greedy Approach:

In this approach, we take the best solution for the present step without considering in future there might be more efficient result.

1.5.6. Divide and Conquer:

In this approach, we divide the input into smaller problems and then we try to solve those problems to arrive at final result.

What are You Looking For?