Algorithms

A collection of commonly used algorithms, written in C/C++, java, Python...

• Data Structures

  • Fenwick tree/Binary indexed tree
  • Segment tree
  • Skip list
  • Strings
    • Longest common subsequence

• Graph Theory

  • Lowest common ancestor
  • Largest independent set in a binary tree
  • Threaded binary tree
  • Morris Traversal
  • Shortest path: Dijstra | Bellman-Ford | Floyd–Warshall

• Search

  • K_{th} element selection
  • Knuth–Morris–Pratt algorithm
  • Longest increasing subsequence

• Sorting

  • Quick sort
  • Merge sort
  • Heap sort
  • Patience sort

• Computational Geometry

  • Convex hull

• Number Theory

  • Greatest common divisor
  • Extended Euclidean algorithm

• Efficient Computation

  • Modular exponentiation
  • Hamming distance

• Image Processing

  • Gabor filter
  • Hough transform

• Utilities

  • Date recorder
  • Number/String conversion

Needing improvements

• Convex hull Marriage-before-Conquest and 3D version
• Interval tree

TODO

• Randomized Algorithms: Reservoir sampling
• Number Theory: Catalan number .