Graph Algorithms

Breadth First Search (BFS)
Depth First Search (DFS)
Shortest Path from source to all vertices Dijkstra
Shortest Path from every vertex to every other vertex Floyd Warshall
Minimum Spanning tree Prim
Minimum Spanning tree Kruskal
Topological Sort
Johnson’s algorithm
Articulation Points (or Cut Vertices) in a Graph
Bridges in a graph

Dynamic Programming

Longest Common Subsequence
Longest Increasing Subsequence
Edit Distance
Minimum Partition
Ways to Cover a Distance
Longest Path In Matrix
Subset Sum Problem
Optimal Strategy for a Game
0-1 Knapsack Problem
Assembly Line Scheduling

Searching And Sorting

Binary Search
Quick Sort
Merge Sort
Order Statistics
KMP algorithm
Rabin karp
Z’s algorithm
Aho Corasick String Matching
Counting Sort
Manacher’s algorithm: Part 1, Part 2 and Part 3

Number theory and Other Mathematica

Prime Numbers and Prime Factorization

Primality Test | Set 1 (Introduction and School Method)
Primality Test | Set 2 (Fermat Method)
Primality Test | Set 3 (Miller–Rabin)
Sieve of Eratosthenes
Segmented Sieve
Wilson’s Theorem
Prime Factorization
Pollard’s rho algorithm

Modulo Arithmetic Algorithms

Basic and Extended Euclidean algorithms
Euler’s Totient Function
Modular Exponentiation
Modular Multiplicative Inverse
Chinese remainder theorem Introduction
Chinese remainder theorem and Modulo Inverse Implementation
nCr%m and this.

Miscellaneous:

Counting Inversions
Counting Inversions using BIT
logarithmic exponentiation
Square root of an integer
Heavy light Decomposition , this and this
Matrix Rank
Gaussian Elimination to Solve Linear Equations
Hungarian algorithm
Link cut
Mo’s algorithm and this
Factorial of a large number in C++
Factorial of a large number in Java+
Russian Peasant Multiplication
Catalan Number

Data Structures

Binary Indexed Tree or Fenwick tree
Segment Tree (RMQ, Range Sum and Lazy Propagation)
K-D tree (See insert, minimum and delete)
Union Find Disjoint Set (Cycle Detection and By Rank and Path Compression)
Tries
Suffix array (this, this and this)
Sparse table
Suffix automata
Suffix automata II
LCA and RMQ

======================

Naive Bayes. Classification is a natural first step to machine learning and the Naive Bayes classifier combines that with the trending concept of Bayesian inference. Despite its simplicity, can address key problems like spam classification.
Map-Reduce. A simple and visual way of leveraging multiple computers to solve a single task. More on its different uses here: MapReduce Patterns, Algorithms, and Use Cases.
Hill Climbing. Introduces optimization over a non-exhaustible domain and leads to a whole array of powerful methods like gradient-descent, simulated annealing. Optimization allows us to do decision making, it's important.
Binary search. Introduces logarithmic complexity and how the structure of data can change complexity characteristics of operations.
Exponentiation (powers) by halving. Great example of a recursive attack. You would be surprised how many problems can be described as exponentiation (for an associative operation) of something: a number, a matrix and more. Again it's magical that associativity of an operation allows you to turn a linear factor into a logarithmic one.
Floyd-Warshall. Graphs as matrices, shortest paths, negative cycles, dynamic programming in five lines of code.
Inductive inference. Inductive inference. This idea on how to find programs that do certain things without having a human write them I believe is the key to the future of AI and simulating and understanding the human mind.
Markov Chain Monte Carlo. Approximate integral, expected value computation based on a conditional specification of the probability distribution. This gives us a general way of doing data analysis.
Shor's algorithm. Non-trvial example of a quantum algorithm that shows a significant complexity improvement. Reveals how quantum computing works.
PageRank. How to iteratively solve for tightly related variables to extract metrics on graphs.

=============================

AI

Gradient Descent It’s the cornerstone of many machine learning pipelines and an industry standard for convex optimization. Also a good idea would be to get familiar with it’s modifications like Adagrad/Adadelta
Backpropagation You are unlikely to implement it for production, but it’s extremely useful to understand the principle behind
Q-Learning With the increasing power of acting agents approach and reinforcement learning in general I think it’s appropriate to include the main method.
DFS and BFS Yes, they are often very useful for implementing various optimization methods and heuristics. Beam search is one of the examples.
Gibbs sampling Not necessary the kind of thing you need to think of daily, but one of the most important algorithms in machine learning easily.
Long Short-Term Memory Cell In many cases this is the main building material for recurrent neural networks.
Decision Trees and Ensembling Sometimes they work really well as a reinforcement part.
K Nearest Neighbors It can do amazing things in case of embeddings that represent semantic similarity as spatial proximity. AMAZING.
Encoder-Decoder Architecture Extremely powerful sequence-to-sequence learning method, I would predict an increasing popularity for it in research later.
Convolutional NNs The concept is very complicated…until you try to implement it, which is the best way to learn them.

Pattern Recognition and Machine Learning by Christopher Bishop

Deep Learning by Ian Goodfellow et al.

Supervised Sequence Labeling with RNNs by Alex Graves

======================

BFS / DFS / TopSort
MergeSort
Binary power / SQRT - binary search / GCD
Sieve of Eratosthenes
Dijkstra shortest paths
Tarjan's strongly connected components
Dynamic: Fibonacci numbers / Knapsack
Range minimum query: SQRT decomposition / Segment trees
Hashing: Rabin Karp
Selection / Median finding algorithm - O(n)

========================

Evolutionary Algorithms - aim at solving combinatorial search problems (such as the famous TSP problem) by initializing a set of solutions and “breeding” the better ones in each iteration to “give birth” to new, possibly better solutions. This way they search the space of solutions in clever & efficient ways. Some of those algorithms are a result of nature & biology studies. My favorite, a little different by nature, is the Ant Colony Optimization (ACO).
Kalman Filter - That is a classical algorithm that is used in radar systems, robotics, and quite a lot of applications where GPS (location data) is involved. The idea is to use statistics to separate the noise/signal of a temporal location input, and to output a somewhat smoothed version of the path that is “cleansed” from the noise.
Dijkstra Algorithm - The gold-standard for exact shortest-path-searching in discrete space (e.g. graphs). It is quite powerful and massively used, relatively easy to understand, implement, and to visualize.
Hungarian Algorithm - This is an efficient solver for the assignment problem (akamatching problem) that is a fundamental problem in operation research. It is a classic, but is still used today in practice due to its efficiency and relative simplicity.
Rapid-exploring Random Tree (RRT) - This one is a less obvious but is really interesting (in my opinion) and fun to watch working. This is a sampling-basedalgorithm for path-searching in continuous spaces, such as in robotics applications (it gets interesting in the presence of obstacles). Its basic version is very simple to implement, but it is followed by really interesting variations that use different techniques for different optimization goals.
Statistics-based Spelling Correctors are also nice to have! Read Phrase Spelling Corrector using Word Collocation Probabilities for a nice intro.
Regarding Hidden Markov Model - let me add this is a consequence of roughly 3 great algorithmic frameworks:
- Markov Chain - It is the core of the HMM model. Very powerful framework to relax complex models to simpler ones to achieve simplicity for inference. Try looking for MCMC algorithms (Gibbs sampling, Metropolis-Hastings) for complex statistical learning - very interesting field that is Markov Chain based as well.
- Dynamic Programming (DP) - I consider this field as a must for CS practitioners. It is a base framework for a massive amount of great optimization algorithms that work by dividing the problems into subproblems. HMM’s Baum-Welch uses DP.
- Expectation Maximization (EM) - A wide set of Data Mining algorithms are a result of this learning paradigm, such as (Gaussian, but not limited to) Mixture Models, HMM, K-Means and more. It is used in the presence of latent variables (or missing values) to find the Maximum Likelihood Estimates (MLE) of the parameters and the most probable assignment to the latent variables, simultaneously, such as in K-Means’ centroids (model’s parameters) and observation-to-cluster assignments (latent variables).

=========================

Reverse Polish Notation
SAT solver (Boolean satisfiability problem)

erhangundogan/algorithms.md