## Main algorithms to use.

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

Linear data structures and algorithms:

• Arrays
• Stack
• Queues

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

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

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

• 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

• Knuth Morris Pratt Algorithm
• Rabin Karp Algorithm
• Tries and Compressed Tries
• Prefix Trees, Suffix Trees, Suffix Automation – Ukkonen Algorithm