Algorithm List

Writing tutorials for algorithm can be really time consuming and hard. Also, a bit redundant since there are already so many tutorials out there. I will give the links where possible. Anyways, here are the list of algorithms that I currently know. I am trying my best not to share anything that I don't know myself.

NUMBER THEORY

1. Primality testing : Determine whether a number is prime or not.

• Prime Sieve to generate list prime number
• Bit-wise prime sieve
• Segmented prime sieve

2. Euclidean algorithm : To calculate the greatest-common-divisor ( GCD ).

• Calculation of lowest-common-multiple ( LCM ).
• Extended Euclidean algorithm: To calculate inverse of a modulus.

3. Big-mod: To calculate modulus of a number of the form ( a ^ p ) % d, where a number, p is the power and d is the divisor.

4. Factorization of a number

• Number of divisor of a number
• Euler's Totient (Phi) Function: To calculate number of co-primes of a number.

5. Algorithm related to factorials

• Number of digit of a factorial
• Number of trailing zeroes
• Last X digit of a factorial
• First X digit of a factorial

GRAPH THEORY

1. Graph Traversal using

• Breadth First Search ( BFS ) : SSSP on unweighted graph
• Depth First Search ( DFS )
• Finding Connected Components

2. Single Source Shortest Path algorithm ( SSSP ):

• Dijkstra algorithm : Works for positive edges only
• Bellman-ford : Detects negative cycle and finds SSSP with negative edges.

3. Minimum Spanning Tree ( MST )

• Kruskal Algorithm

4. Graph Bipartite Algorithm.

5. Depth First Search:

• Topological Sorting of directed graph
• Strongly Connected Components
• Cycle detection

6. Euler Circuit/ Path

• Euler Circuit: Return to source node after traveling every edge exactly once.
• Euler Path: Travel to target node from source node after traveling every edge exactly once.

DYNAMIC PROGRAMMING

1. Longest Common Subsequence ( LCS ): Finding LCS between multiple strings

2. Bit-mask