The Top 10 Algorithms and Data Structures that you must know!

It’s been over a decade since I started learning about the computers and the programming languages. During my graduation, I studied algorithms as a major. It started with "The Data Structures and Algorithms" with c++. As we all know "Algorithms is a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer." Algorithm usually means a small procedure that solves a recurrent problem.

Algorithm is not something that you can beneficially memorize and use. You need to understand its purpose. For example, there are many algorithms available for sorting a set of numbers. But you need to understand how every single algorithm is different than other and which algorithm meets your requirements.

Here are the top 10 algorithms and data structures that you must know.

1.    Sort Algorithm

2.    Search algorithms

3.    Hashing

4.    Dynamic programming

5.    Exponentiation by squaring

6.    String matching and parsing

7.    Primality testing algorithm

8.    Graph algorithms

9.    State space search algorithm

10. Linear Programming

1.   Sort Algorithm
Everyone knows about this algorithm. Here idea is to arrange the items of a list in a specific order, usually in ascending or descending order. Many programming languages come with built-in libraries which provides sort functionality for you. But is very useful if you know how they work. Some of sorting algorithms are

§ Selection Sort

§ Bubble Sort

§ Insertion Sort

§ Merge Sort

§ Quick Sort

§ Heap Sort

§ Counting Sort

§ Radix Sort

§ Bucket Sort

Depending on the requirements you can use any of it.

2.   Search algorithms
Searching algorithms are used to solve search-related problems by performing an efficient search. There are many algorithms present but Binary search and Depth First Search (DFS) Breadth-first search (BFS) are the one you must know of.

Binary Search is used to perform a very efficient search on the sorted dataset. The time complexity is O(log2N). The idea is to repeatedly divide in half the portion of the list that could contain the item until we narrow it down to one possible item.

Depth first search and Breadth first search are tree/graph traversing and searching data structures. It helps to find the shortest path to achieve perfect location on the map.

    3.   Hashing

Hashing plays a different role for cache management, cryptography, efficient look up and error detection. This algorithm gives more quality and produces pseudo-random and n bits. Hash lookup is currently the most widely used technique to find appropriate data by key or ID. We access data by its index. Previously we relied on Sorting + Binary Search to look for index whereas now we use hashing.

The data structure is referred as Hash-Map or Hash-Table or Dictionary that maps keys to values, efficiently. We can perform value lookups using keys. Idea is to use an appropriate hash function which does the key -> value mapping. Choosing a good hash function depends on the scenario.

4.   Dynamic programming

Dynamic programming is a method for solving a complex problem by breaking it down into simpler subproblems. We solve the subproblems, remember their results and using them we make our way to solving the complex problem, quickly.

Dynamic programming algorithm helps to give expensive function to the evaluation. The algorithm is used by the Fibonacci number to formulate the result with the ratio. This gives dynamic programming and reduces the computational complexity for using the algorithm for optimization. It will exchange the memory of computation and commonly used for trade off. The algorithm gives a great solution to the large problem that can be expressed in an optimal solution. The algorithm is used to save time for solving the large problem.

An answer on Quora explains Dynamic programming in layman terms.

*writes down "1+1+1+1+1+1+1+1 =" on a sheet of paper* What's that equal to?

*counting* Eight!

*writes down another "1+" on the left* What about that?

*quickly* Nine!

How'd you know it was nine so fast?

You just added one more

So, you didn't need to recount because you remembered there were eight! Dynamic Programming is just a fancy way to say 'remembering stuff to save time later'

5.   Exponentiation by squaring

Say you want to calculate 232. Normally we'd iterate 32 times and find the result. What if I told you it can be done in 5 iterations?

Exponentiation by squaring or Binary exponentiation is a general method for fast computation of large positive integer powers of a number in O(log2N). Not only this, the method is also used for computation of powers of polynomials and square matrices.

6.   String matching and parsing

The algorithm is used for pattern matching and one of the most necessary in computer science. The programmer should know the two algorithms are the regular expression and Knuth Morris Pratt (KMP) algorithm. The KMP algorithm is used to make the short pattern in the longer string. It will perform whole document should be matched in the pattern. A regular expression is used to parsing the string with predefined conditions. This is used in web development for matching and URL parsing.

7.   Primality testing algorithm

There are deterministic and probabilistic ways of determining whether a given number is prime or not. We’ll see both deterministic and probabilistic (nondeterministic) ways.

Sieve of Eratosthenes (deterministic)

If we have a certain limit on the range of numbers, say determine all primes within range 100 to 1000 then Sieve is a way to go. The length of the range is a crucial factor because we have to allocate a certain amount of memory according to the range.

For any number n, incrementally testing up to sqrt(n) (deterministic)

In case you want to check for few numbers which are sparsely spread over a long range (say 1 to 1012), Sieve won't be able to allocate enough memory. You can check for each number n by traversing only up to sqrt(n) and perform a divisibility check on n.

Fermat primality test and Miller–Rabin primality test (both are nondeterministic)

Both of these are compositeness tests. If a number is proved to be composite, then it sure isn’t a prime number. Miller-Rabin is a more sophisticated one than Fermat’s. In fact, Miller-Rabin also has a deterministic variant, but then it's a game of trade between time complexity and accuracy of the algorithm.

8.   Data Structures and Graph algorithms

The graph algorithm is very efficient to use and solve the unrelated problems which can be mapped in the algorithm. The algorithm helps to solve the problems such as shortest path, minimum spanning tree, matching and cut vertexes. Using the algorithm solve the dynamic programming related to already exist coding. Besides, the algorithm helps to make the problem as a graph structure to find the way to get the result to the problem. This is one of the most important algorithms to software engineer.

9.   State space search algorithm

The state space search is used to optimization the problem. One should use this algorithm for limited breadth first search and depth first search. This solves the problems with iteration and vectors are randomly used to search the space. The algorithm is used to solve the game as chess, you can find more ways to move. The exact number of the valid state is given in the order and number of arcs on the game is graphed. The algorithm uses A* to find the state space search of the problem.

10.   Linear Programming
Linear programming (LP) is one of the simplest ways to perform optimization. It helps you solve some very complex optimization problems by making a few simplifying assumptions. As an analyst you are bound to come across applications and problems to be solved by Linear Programming.