Algorithms that programmers should know
First start with Linear data structures and algorithms.
- Arrays
- Linked List
- Stack
- Queues
Then move to basic algorithms:
- Sorting - Merge Sort, Insertion Sort, Quick Sort, Number of inversions
- Matrix Multiplication (just know the algo if not implement it)
- Prime Sieving
- Modular Math including multiplication and division
- Euclidean Algorithm for GCD, Modular Inverse, Fast Exponentiation
- Fibonacci number with matrix multiplication
- Probability distribution and expected value
- Stats - Mean, Median, Variance, Bayes theorem
The one can learn some popular algorithmic techniques:
- Divide and Conquer - Binary Search, Maximum Subarray
- Greedy Algorithms - Activity Selection, Huffman encoding
- Dynamic Programming - Matrix Chain Multiplication, Knapsack,
- Linear Programming - Variable Maximisation, Linear time sorting
- String Algorithms - Manacher, LCS, Edit Distance
Then comes some typical non-linear data structures:
- Trees - Binary Tree, General Tree, Lowest Common Ancestor
- Binary Search Tree - Inorder Traversal, Level order traversal, finding kth largest element, diameter, depth, number of nodes, etc.
- Heaps - Array Implementation, Heapify, Heap Sort
- Union Find
- Hash Table - Linear Probing, Open addressing, Collision avoidance
Then you can learn about Graphs:
- Adjacency List, Adjacency Matrix, Weighted Edge Graphs
- Basic Traversal algos - Breadth First Search, Depth First Search, etc
- Shortest Path Finding Algorithm - Dijkstra, Floyd Warshal, Bellman Ford
- Minimum Spanning Tree - Kruskal's Algo, Prim's Algo
Advance Tree and Graph :
- Balanced Trees - AVL, Red-Black
- Heavy Light Decomposition, B+ Trees, Quad Tree
- Advance Graph - Min Cut, Max Flow
- Maximum Matching - Hall's Marriage
- Hamiltonian Cycle
- Edge Graphs / Line Graphs
- Strongly Connected Components
- Dominant Sub-Graph, Vertex Cover, Travelling Salesman - Approx algos
Advance String Algorithms :
- Knuth Morris Pratt Algorithm
- Rabin Karp Algorithm
- Tries and Compressed Tries
- Prefix Trees, Suffix Trees, Suffix Automation - Ukkonen Algorithm
Advance Math:
- Fast Fourier Tranformation
- Primality Testing
- Computational Geometry - Closest point pair, Voronoi diagram, Convex Hull
General Advance topics :
- Iterating through all combination / permutation
- Bit manipulation