# Algorithm classification

From Algowiki

## Contents

- 1 Linear algebra problems
- 2 Algorithms on lists and arrays
- 3 Computational geometry
- 4 Computer analysis and modeling
- 5 Miscellaneous applied problems
- 6 Cryptographic algorithms
- 7 Other algorithms

# 1 Linear algebra problems

## 1.1 Matrix and vector operations

### 1.1.1 Vector operations

- Pairwise summation
- Uniform norm of a vector: Real version, serial-parallel variant
- Dot product
- The serial-parallel summation method

### 1.1.2 Matrix-vector operations

#### 1.1.2.1 Multiplying a nonsingular matrix by a vector

#### 1.1.2.2 Multiplying a matrix of special form by a vector

- Fourier transform

### 1.1.3 Matrix operations

## 1.2 Matrix decompositions

- Triangular decompositions
- Gaussian elimination (finding the LU decomposition)
- LU decomposition using Gaussian elimination without pivoting
- LU decomposition using Gaussian elimination with pivoting

- Cholesky method

- Gaussian elimination (finding the LU decomposition)
- Available triangular decompositions for matrices of special form
- Unitary-triangular factorizations
- QR decomposition of dense nonsingular matrices
- QR decomposition methods for dense Hessenberg matrices

- Reducing matrices to compact forms
- Unitary reductions to Hessenberg form
- Unitary reductions to tridiagonal form
- Eigenvalue decomposition (finding eigenvalues and eigenvectors)

- Unitary non-similarity reductions to compact forms

## 1.3 Solving systems of linear algebraic equations

- Direct methods
- Linpack benchmark
- Matrices of a special form
- Triangular matrices
- Methods for solving tridiagonal SLAEs
- Methods for solving block triangular matrices
- Block forward substitution (real version)
- Block backward substitution (real version)
- Methods for solving block bidiagonal matrices

- Methods for solving block tridiagonal matrices
- Methods based on the conventional LU decomposition
- Other methods

- Solving systems of linear algebraic equations with coefficient matrices of special form whose inverses are known

- Iterative methods for solving systems of linear algebraic equations

## 1.4 Solving eigenvalue problems

- Eigenvalue decomposition (finding eigenvalues and eigenvectors)
- Partial eigenvalue problem
- Singular value decomposition (finding singular values and singular vectors)

## 1.5 Algebra of polynomials

# 2 Algorithms on lists and arrays

## 2.1 Search algorithms

- Linear search: Finding an item in an arbitrary list, [math]O(n)[/math]
- Binary search: Finding the position of a target value within a sorted array, [math]O(\log(n))[/math]

## 2.2 Sorting algorithms

## 2.3 Graph algorithms

- Graph traversal
- Single Source Shortest Path (SSSP)
- Breadth-first search (BFS) (for unweighted graphs)
- Dijkstra's algorithm
- Bellman-Ford algorithm
- Δ-stepping algorithm

- All Pairs Shortest Path (APSP)
- Transitive closure of a directed graph
- Longest shortest path
- Construction of the minimum spanning tree (MST)
- Search for isomorphic subgraphs
- Graph connectivity
- Shiloach-Vishkin algorithm for finding the connected components
- Disjoint set union
- Tarjan's strongly connected components algorithm
- DCSC algorithm for finding the strongly connected components
- Tarjan's biconnected components algorithm
- Tarjan-Vishkin biconnected components algorithm
- Tarjan's algorithm for finding the bridges of a graph
- Vertex connectivity of a graph
- Gabow's edge connectivity algorithm

- Finding maximal flow in a transportation network
- Finding minimal-cost flow in a transportation network
- Assignment problem
- Betweenness centrality algorithm

# 3 Computational geometry

- Finding the diameter of a point set
- Finding the convex hull of a point set
- Delaunay triangulation
- Voronoi diagram
- Point-in-polygon problem
- Convex polygon intersection
- Star-shaped polygon intersection

## 3.1 Computer graphics

- Line drawing algorithms: Approximating a line segment on discrete graphical media
- Determining visible parts of a three-dimensional scene
- Ray tracing: Rendering realistic images
- Global illumination: Regarding direct illumination and reflection from other objects

# 4 Computer analysis and modeling

## 4.1 Computer benchmarks

## 4.2 Algorithms of quantum system simulation

## 4.3 Machine learning algorithms

### 4.3.1 Neural networks

### 4.3.2 Game theory algorithms

# 5 Miscellaneous applied problems

## 5.1 Optimization algorithms

- Linear programming
- Simplex algorithm
- Branch and bound method
- Genetic algorithms
- Ant colony algorithms
- Hybrid algorithms
- Stochastic dual dynamic programming (SDDP)