# Algorithm : Top Algorithms/Data Structures every computer science student should know

## What is the Algorithm?

A process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer is called Algorithm.

For example, to make a cup of coffee there is a set of instruction to which we have to go through like :

1. Start
• Boil Water
• Prepare a mug
• Put a teaspoon of coffee and sugar
• Pour hot water
• Stir
• End

I hope you will now know what algorithm is if you had any confusion before. Now let’s go through the top common algorithm which you need to know as a computer student.

## 1. Sorting Algorithm

As the name says sorting means rearrangement. Sp to rearrange the set of similar elements (array) or list of elements we use sorting algorithms.

For Example, We have a set of characters (c,o,d, i,n,g) if we sort them according to there ASCII value then the output will be shown like this (c,d,g, i,n,o)

Sorting Algorithms :

• Selection Sort
• Bubble Sort
• Merge Sort
• Quick Sort
• Heap Sort

For a full reference of sorting algorithms: GFG

## 2.  Searching algorithms

The searching algorithms are used to search or find one or more than one element from a dataset.

Searching may be sequential or not. If the data in the dataset are random, then we need to use sequential searching. Otherwise, we can use other different techniques to reduce complexity.

Searching algorithms:

• Linear Search
• Binary Search
• Exponential Search

For a full reference of searching algorithms: GFG

## 3. Hashing Algorithm

Let’s say you have an important file to send and you want to ensure it will get to the address without any changes, in one piece. You could use some trivial methods, like sending it multiple times, contact the addressee and verify the file, and so on… but there’s a much better approach and it’s called hashing algorithm.

Hashing algorithms:

• MD5
• SHA-2
• CRC32

For a full reference of hashing algorithms: 2BS.com

## 4. Dynamic Programming Algorithms

Dynamic Programming is a powerful technique that can be used
to solve many problems in time O(n2) or O(n3) for which a naive approach would take exponential time. (Usually to get running time below that—if it is possible—one would need to add other ideas as well.) Dynamic Programming is a general approach to solving problems, much like “divide-and-conquer” is a general method, except that unlike divide-and-conquer, the subproblems will typically overlap. There are several ways of thinking about the basic idea. Basic Idea: What we want to do is take our problem and somehow break it down into a reasonable number of subproblems (where “reasonable” might be something like n2) in such a way that we can use optimal solutions to the smaller subproblems to give us optimal solutions to the larger ones. Unlike divide-and-conquer (as in mergesort or quicksort) it is OK if our subproblems overlap, so long as there are not too many of them.
Important Reference :
2.  PDF

## 5. Exponentiation by Squaring

Exponentiating by squaring is an algorithm that is used for quickly working out large integer powers of a number. It is also known as the square-and-multiply algorithm or binary exponentiation. It uses the binary expansion of the exponent.

Exponentiation by Squaring is of quite general use, for example in modular arithmetic.

Example: GFG

## 6. String Matching and Parsing

The Rabin–Karp algorithm is a string-searching algorithm that uses hashing to find an exact match of a pattern string in a text. It uses a rolling hash to quickly filter out positions of the text that cannot match the pattern and then checks for a match at the remaining positions. Generalizations of the same idea can be used to find more than one match of a single pattern or to find matches for more than one pattern.

To find a single match of a single pattern, the expected time of the algorithm is linear in the combined length of the pattern and text, although its worst-case time complexity is the product of the two lengths. To find multiple matches, the expected time is linear in the input lengths, plus the combined length of all the matches, which could be greater than linear. In contrast, the Aho–Corasick algorithm can find all matches of multiple patterns in worst-case time and space linear in the input length and the number of matches (instead of the total length of the matches).

A practical application of the algorithm is detecting plagiarism. Given the source material, the algorithm can rapidly search through a paper for instances of sentences from the source material, ignoring details such as case and punctuation. Because of the abundance of the sought strings, single-string searching algorithms are impractical.

Reference

## 7. Primality Testing Algorithm

primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not.