Algorithms

lastmod 2026-02-13created 2014-01-1192 edits

An algorithm (IPA: [ǽlɡərìðm]) is a finite set of operations for solving a given problem.

Categories

• Data structure
• Algorithm Visualizer - Visualization of algorithms.

Average and worst-case analysis

See Big O notation for details.

Sorting

• Sorting Algorithms Animations
• Youtube - Visualization and Comparison of Sorting Algorithms

• Depth-first search (DFS)
• Breadth-first search (BFS)

Data compression

• ZXC - High-performance asymmetric lossless compression library optimized for content delivery
• zip
• gzip
• lzma

Finding

• Circular Obstacle Pathfinding - Pathfinding around a set of circular obstacles

Routing

• Border Gateway Protocol (BGP)
• Equal-cost multi-path routing (ECMP)

Mathematics

• Euclidean Algorithm: an algorithm for finding the greatest common divisor.
• Karatsuba Algorithm: a method for multiplying large numbers that reduces the number of multiplications by increasing the number of additions and subtractions.
• Fast inverse square root - The fast inverse square root algorithm is used to compute angles of incidence and reflection in computations such as lighting.

Curves

• Bezier curve: a curve that does not pass through the intermediate points but bends under their influence.
• Ferguson / Xoons curve
• Catmull-Rom spline curve: a curve that passes through all intermediate points. In games it is often used to create shapes such as the trail of a sword.
• Lemniscate of Bernoulli

Computer Graphics

• Line drawing
  • DDA
  • Bresenham's Line Algorithm
  • wu
  • efla
• Circle drawing
  • Midpoint circle algorithm
• Filling
  • Scanline rendering
  • Flood Fill Algorithm
  • Boundary Fill Algorithm
• Curve
  • Bezier curve (Interpolation)
  • Spline

Image

• jpeg
• png (zlib)
• Seam Carving - Finds only the unimportant repeated parts (seams) in an image and shrinks or expands them
• FELICS - A lossless image compression algorithm that is 5 times faster than the lossless JPEG codec with a similar compression ratio.
• ImageZero
• QOI - O(n) lossless image compression

Network Programming

• Nagle's algorithm

Cliping

• Cohen–Sutherland algorithm
• Cyrus–Beck algorithm
• Sutherland–Hodgman algorithm

Natural phenomena

• Light
  • Rayleigh Scattering & Mie Scattering
• Plasma Effect
• Ripple Effect

Collision Detection

• Point in polygon
• 2D Polygon Collision Detection
• Axis Aligned Bounding Box (AABB)

Geometry

• Intersection of a triangle polygon and a ray ¹
• Finding the intersection of two line segments using the cross product ²
• Determining the relative direction of two vectors using the cross product ³
• Finding the position of a point relative to a polygon
• 2DGeometry - Finding the position of a point in a space divided by lines and line segments ⁴ (method using the Cross product)
• Line–sphere intersection
• Distance from a point to a line
• Angle - How to compute angles.
• Douglas-Peucker algorithm - Simplifies a curve or polygon. Implemented as the cv2.approxPolyDP function.
• Geometry:LocalToGlobal - Converts local ROI coordinates to global ROI coordinates.

Fluid Simulation

Algorithm categories by purpose

• Multidimensional spatial files: aimed at fast search of spatial information.
• Search and Matching algorithms: algorithms related to pattern matching or search.

Cryptography

• Cryptographic hash function
• Message authentication code (MAC)
• Blockchain

Key derivation function

• Argon2
• bcrypt
• crypt
• Lyra2
• PBKDF2
• scrypt

Error detection and correction

• Repetition code
• Parity bit
• Checksum
• Cyclic redundancy check (CRC)
• Cryptographic hash function
• Forward error correction

Consensus algorithm

• Raft
• Conflict-free replicated data type (CRDT)

Game Algorithmes

• Dungeon Generation
  • Binary space partitioning (BSP)
  • Wave function collapse (Korean: 파동 함수 붕괴)
• Fast inverse square root

Trees

See also

• Design pattern
• Software design
• Software design patterns
• Gang of Four (GoF)
• Algorithms
• Software architecture - Content on software architecture design.
• Event driven architecture
• System Architecture
• Layered Design - A design method for preventing circular package references.
• Spaced repetition (Korean: 간격 반복 학습)
• Bloom filter

Favorite site

• Wikipedia (en) explanation of algorithms
• Hyoung-Jun(Kim Hyoung-Jun) GIS Lab: Programming/Algorithms ⁵
• Algorithmia - Open Marketplace for Algorithms (open market for algorithms, including deep learning)

Tutorials

• Gihub - 1ambda - Algorithm ⁶

Articles

• A new horizon in algorithm research: proof that "a little memory can be more powerful than a lot of time" | GeekNews
  • [Original] For Algorithms, a Little Memory Outweighs a Lot of Time | Quanta Magazine
  • A new proof by MIT theoretical computer scientist Ryan Williams shows that memory can be a more powerful computational resource than time
  • Breaks a 50-year standstill on the relationship between time and space complexity, presenting a way to convert any algorithm to use less memory
  • The core of the proof is the idea of generalizing space-saving simulation to reduce an algorithm's space usage to around the square root of its time
  • This makes progress toward quantitatively proving the gap between the PSPACE and P classes, and also opens the possibility of proofs of wider gaps
  • Experts call the result "a stunning advance and a starting point for new exploration", and it may become a clue to solving other hard problems in theoretical computer science

References