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
