Algorithm101

This repository is not just an implement yet a learning process to fully understand the algorithms. In this reop, I implement some common and useful algorithms.

Divide and conquer

• Find max subarray

Sorting

• Merge sort
• Quick sort
• Topological sort

Searching

• Binary search
• Binary search tree

Approximation

• Monte Carlo integral
• Metropolis–Hastings algorithm approximate Gamma(k=2.0,theta=2.0)

Dynamic programming

• Matrix chain multiplication
• Longest common subsequence

Compression

• Huffman coding (100 days: 14)

Tree

• Kruskal's algorithm (Minimum spanning tree)
• Prim's algorithm (Minimum spanning tree)
• Tree traverse: pre-order, in-order, post-order
• JSON Parser

Graph

• Depth first search on graph
• Breadth first search on graph
• Dijkstra's algorithm (100 days: 48)
• PageRank (100 days: 32)
• Strongly connected components (100 days: 95)

Machine learning

• Perceptron learning algorithm (100 days: 14)
• Linear regression with linear algebra solution
• Linear regression with gradient descent
• Conjugate gradient method
• Logistic regression with IRLS (100 days: 79)
• Markov chain
• Hidden Markov model (ref)
• K nearest neighbor classifier
• K-means (100 days: 21)
• Principle component analysis (100 days: 92)
• Naive Bayes classifier
• Decision tree classifier (ID3)

Applications

• POS system
• Interpreter for arithmetics
• MVC pattern for machine learning platform