A set of everyday algorithms. Majority of algorithms are implemented in Python, however, some of them are also in Groovy or Java. Majority of implementations in Python (especially scientific algorithms) require several dependencies: numpy, matplotlib, scipy.
- Quicksort, typical divide and conquer implementation. On average runs in O(n log(n)) time complexity, where n is problem size.
- Radix sort, least significant digit implementation using bucket method. On average runs in O(nk) time complexity, where n is problem size and k is maximum number of digits.
- Universal hashing - implementation of one of the hash functions from universal familiy of hash functions.
- Bloom filter - implementation of space-efficient probabilistic data structure that is used to test whether an element is a member of a set.
Sample set of keys is also added.
Algorithm to maximize and minimize the arithmetic expressions by adding missing * and + signs. I.e., given a list of numbers, e.g. 2 1 3 4, calculate the maximizing placement of operations. E.g. minimum is (2×1)+(3+4)=9, and maximum is (2+1)×3×4=36.
- Depth-first search, recursive and non recursive implementation with stack. Also, prints each vertex discovery and finishing times.
- Breadth-first search, recursive implementation.
Sample graph is also added.
- Edit distance - implementation of Damerau–Levenshtein distance - distance between two strings, i.e., finite sequence of symbols, given by counting the minimum number of operations needed to transform one string into the other, where an operation is defined as an insertion, deletion, or substitution of a single character, or a transposition of two adjacent characters.
- DBSCAN - pure and simple implementation from pseudocode.
- OPTICS - implementation produces hierarchical structure of the clusters by creating dendrogram and examining steep down and steep up areas.
- LU-factorisation - function that performs LU-factorisation of a given matrix A = LU.
- Gaussian elimination - implementation of partial pivoting in the Gauss elimination method.
- Curve fitting - simple 2 degree polynomial fit.
- Gradient descent - implementation of Gradient Descent algorithm with example function and initial guess.
- Jacobi method - function that solves the system of linear equations using Jacobi method. The function takes a sparse matrix and a right-hand side vector.
- 1D Laplacian matrix - function that generates 1D Laplace matrix using Dirichlet boundary conditions.
- 2D Laplacian matrix - function that generates 2D Laplace matrix using Dirichlet boundary conditions.
- Conjugate gradient method - Conjugate Gradient method with preconditioning for solving sparse linear systems. Is location under other project here.