Roadmap to learning Data Structures and Algorithms (DSA)

Introduction :

We all know that Data structure algorithms are backbone of every concept that we use.

`One of the most common applications of data structure is Search & Sort algorithms. The most commonly used of these are :

1. Binary Search
2. Linear Search
3. Bubble Sort
4. Selection Sort
5. Insertion Sort
6. Merge Sort
7. Heap Sort (Binary Heap)
8. Quick Sort
9. Topological Sort

Algorithms should know :

• DFS and BFS Traversals
• Dijkstra’s Algorithm for Shortest Path
• Prim’s and Kruskal’s For Minimum Spanning Tree
• 0–1 Knapsack Problem
• Subset Sum Problem
• Longest Common Subsequence
• Longest Increasing Subsequence
• Modular Exponentiation
• Sum of Bit Differences among All Pairs

Making Code Efficient :

We often hear the performance of an algorithm described using Big O Notation.

The study of the performance of algorithms – or algorithmic complexity – falls into the field of algorithm analysis. Algorithm analysis answers the question of how many resources, such as disk space or time, an algorithm consumes. We’ll be looking at time as a resource. Typically, the less time an algorithm takes to complete, the better.

• O(1)
• O(log n)
• O(n)
• O(n log n)
• O(n^p)
• O(kⁿ)
• O(n!)

Constant Time Algorithms – O(1)

How does this input size of an algorithm affect its running time? Key to understanding Big O is understanding the rates at which things can grow. The rate in question here is time taken per input size.

int n = 1000;
System.out.println("Man your input is : " + n);
System.out.println("Yeah I'm doing more stuff with your input : " + n);
System.out.println("And more : " + n);

The above example is constant time. Even if it takes 3 times as long to run, it doesn’t depend on the size of the input, n. We denote constant time algorithms as follows: O(1). Note that O(2), O(3) or even O(1000) would mean the same thing.

Logarithmic Time Algorithms – O(log n):

Constant time algorithms are the quickest one, the next quickest is Logarithmic time.

The important point is here is that the running time grows in proportion to the logarithm of the input (in this case, log to the base 2):

for (int i = 1; i < n; i++) {
}