Algorithms

143 views
0 copy made
Document structure

Algorithms

  1. 1. Combinatorial algorithms
    1. 1.1 General combinatorial algorithms
      1. Brent's algorithm
      2. ​Gale–Shapley algorithm
      3. Floyd's cycle-finding algorithm
      4. Pseudorandom number generators (uniformly distributed)
        1. Lagged Fibonacci generator
        2. Mersenne twister
        3. Linear congruential generator
        4. Blum Blum Shub
    2. 1.3 Sequence algorithms
      1. Part 3
        1. 1.3.7 Sequence sorting
          1. Part 1
            1. Exchange Sorts
              1. Bubble sort
              2. ​Comb sort
              3. Cocktail shaker sort (bidirectional bubble sort)
              4. Gnome sort
              5. Quicksort
              6. Odd-even sort
            2. Hybrid
              1. Timsort
              2. Flashsort
              3. Introsort
            3. Humorous or ineffective
              1. Stooge sort
              2. Bogosort
          2. Part 3
            1. Unknown class
              1. Samplesort
            2. Selection sorts
              1. Smoothsort
              2. Heapsort
              3. Selection sort
            3. Other
              1. Pancake sorting
              2. Topological sort
              3. Spaghetti sort
              4. ​Bitonic sorter
          3. Part 2
            1. Merge sorts
              1. Merge sort
              2. Strand sort
            2. Insertion sorts
              1. Shell sort
              2. Library sort
              3. Insertion sort
              4. Patience sorting
              5. Tree sort (binary tree sort)
              6. Cycle sort
            3. Non-comparison sorts
              1. Bucket sort
              2. ​Counting sort
              3. Radix sort:
              4. Bead sort
              5. Pigeonhole sort
              6. Postman sort
              7. Burstsort
        2. 1.3.9 Substrings
          1. Ukkonen's algorithm
          2. Longest common substring problem
          3. Substring search
            1. Boyer–Moore string search algorithm
            2. Knuth–Morris–Pratt algorithm
            3. Boyer–Moore–Horspool algorithm
            4. Aho–Corasick string matching algorithm
            5. Zhu–Takaoka string matching algorithm
            6. Rabin–Karp string search algorithm
        3. 1.3.8 Subsequences
          1. Shortest common supersequence problem
          2. Longest common subsequence problem
          3. Kadane's algorithm
          4. Longest increasing subsequence problem
      2. Part 1
        1. 1.3.3 Sequence search
          1. Linear search
          2. Ternary search
          3. Selection algorithm
          4. Sorted lists
            1. Fibonacci search technique
            2. Predictive search
            3. Jump search
            4. Binary search algorithm
            5. Uniform binary search
        2. 1.3.1 Approximate sequence matching
          1. String metrics
            1. Damerau–Levenshtein distance
            2. Hamming distance
            3. ​Dice's coefficient
            4. Jaro–Winkler distance
            5. Levenshtein edit distance
          2. Bitap algorithm
          3. Trigram search
          4. Phonetic algorithms
            1. Double Metaphone
            2. ​Metaphone
            3. ​Match Rating Approach
            4. Daitch–Mokotoff Soundex
            5. ​Soundex
            6. ​NYSIIS
        3. 1.3.2 Selection algorithms
          1. Quickselect
      3. Part 2
        1. 1.3.5 Sequence permutations
          1. Fisher–Yates shuffle
          2. Steinhaus–Johnson–Trotter algorithm
          3. Schensted algorithm
          4. Heap's permutation generation algorithm
        2. 1.3.6 Sequence alignment
          1. Smith–Waterman algorithm
          2. Hirschberg's algorithm
          3. Dynamic time warping
          4. Needleman–Wunsch algorithm
        3. 1.3.4 Sequence merging
          1. k-way merge algorithm
          2. Union
          3. Simple merge algorithm
    3. 1.2 Graph algorithms
      1. 1.2.3 Routing for graphs
        1. Part 1
          1. Edmonds' algorithm
          2. Euclidean shortest path problem
          3. Euclidean minimum spanning tree
          4. Longest path problem
        2. Shortest path problem
          1. Floyd–Warshall algorithm
          2. Bellman–Ford algorithm
          3. Johnson algorithm
          4. Dijkstra's algorithm
        3. Minimum spanning tree
          1. Reverse-delete algorithm
          2. Kruskal's algorithm
          3. Borůvka's algorithm
          4. Prim's algorithm
        4. Traveling salesman problem
          1. Nearest neighbour algorithm
          2. Christofides algorithm
        5. Part 2
          1. Warnsdorff's algorithm
          2. Transitive closure problem
          3. Nonblocking Minimal Spanning Switch
      2. 1.2.1 Graph drawing
        1. Force-based algorithms
        2. Spectral layout
      3. 1.2 Graph algorithms
        1. Prüfer coding
        2. ​Hopcroft–Karp algorithm
        3. Coloring algorithm
        4. Hungarian algorithm
        5. Tarjan's off-line least common ancestors algorithm
        6. Topological sort
      4. 1.2.2 Network theory
        1. Flow networks
          1. Dinic's algorithm
          2. Ford–Fulkerson algorithm
          3. Edmonds–Karp algorithm
          4. Karger's algorithm
          5. Push–relabel algorithm
        2. Network analysis
          1. Hyperlink-Induced Topic Search
          2. TrustRank
          3. PageRank
          4. Girvan–Newman algorithm
      5. 1.2.5 Subgraphs
        1. Strongly connected components
          1. Kosaraju's algorithm
          2. Path-based strong component algorithm
          3. Tarjan's strongly connected components algorithm
        2. Bron–Kerbosch algorithm
      6. 1.2.4 Graph search
        1. Part 3
          1. Dijkstra's algorithm
          2. D*
          3. General Problem Solver
          4. Depth-first search
        2. Part 2
          1. Breadth-first search
          2. Bidirectional search
          3. Best-first search
          4. Bloom filter
        3. Part 4
          1. Jump point search
          2. SSS*
          3. Lexicographic breadth-first search
          4. Iterative deepening depth-first search (IDDFS)
        4. Part 1
          1. Beam stack search
          2. ​Backtracking
          3. B*
          4. Beam search
          5. A*
  2. About this document
  3. 3. Computational science
    1. Part 1
      1. 3.3 Geoscience
        1. Vincenty's formulae
      2. 3.1 Astronomy
        1. Easter algorithms
        2. Doomsday algorithm
        3. ​Zeller's congruence
      3. 3.4 Linguistics
        1. Stemming algorithm
        2. Lesk algorithm
        3. Sukhotin's algorithm
      4. 3.2 Bioinformatics
        1. Kabsch algorithm
        2. Sorting by signed reversals
        3. Velvet assembler
        4. Basic Local Alignment Search Tool (BLAST)
        5. UPGMA
        6. ​Maximum parsimony (phylogenetics)
    2. Part 2
      1. 3.6 Physics
        1. Constraint algorithm
        2. Demon algorithm
        3. N-body problems
          1. Barnes–Hut simulation
          2. Fast multipole method (FMM)
        4. Featherstone's algorithm
        5. Ground state
          1. Variational method
            1. Ritz method
        6. Rainflow-counting algorithm
        7. VEGAS algorithm
        8. Sweep and prune
      2. 3.7 Statistics
        1. Part 2
          1. Hidden Markov model
            1. Baum–Welch algorithm
            2. Viterbi algorithm
            3. Forward–backward algorithm
          2. Estimation theory
            1. Kalman filter
            2. Expectation–maximization algorithm
              1. Ordered subset expectation maximization
            3. Odds algorithm
          3. Partial least squares regression
          4. False nearest neighbor algorithm
        2. Part 1
          1. Clustering Algorithms
            1. Average-linkage clustering
            2. Canopy clustering algorithm:
            3. Complete-linkage clustering
            4. KHOPCA clustering algorithm
            5. k-means clustering
            6. K-means++
            7. Expectation–maximization algorithm
            8. DBSCAN
            9. Fuzzy clustering
              1. FLAME clustering
              2. Fuzzy clustering
            10. k-medoids
            11. Linde–Buzo–Gray algorithm
            12. Lloyd's algorithm
            13. Ward's method
            14. SUBCLU
            15. Single-linkage clustering
            16. OPTICS algorithm
          2. ​Approximate counting algorithm
          3. Algorithms for calculating variance
          4. ​Bayesian statistics
            1. Nested sampling algorithm
        3. Part 3
          1. Random sample consensus
          2. Yamartino method
          3. Scoring algorithm
          4. Queueing theory
            1. Buzen's algorithm
          5. Ziggurat algorithm
      3. 3.5 Medicine
        1. Manning Criteria
        2. Texas Medication Algorithm Project
        3. Pulmonary embolism diagnostic algorithms
        4. ESC algorithm
  4. 2. Computational mathematics
    1. 2.4 Number theoretic algorithms
      1. Binary GCD algorithm
      2. Booth's multiplication algorithm
      3. Euclidean algorithm
      4. Extended Euclidean algorithm
      5. Chakravala method
      6. Discrete logarithm
        1. Pohlig–Hellman algorithm
        2. Index calculus algorithm
        3. Baby-step giant-step
        4. Pollard's rho algorithm for logarithms
      7. Integer factorization
        1. Fermat's factorization method
        2. General number field sieve
        3. Pollard's p − 1 algorithm
        4. Pollard's rho algorithm
        5. Lenstra elliptic curve factorization
        6. prime factorization algorithm
        7. Congruence of squares
        8. Dixon's algorithm
        9. Special number field sieve
        10. Trial division
        11. Quadratic sieve
        12. Shor's algorithm
      8. Odlyzko–Schönhage algorithm
      9. Primality tests
        1. Miller–Rabin primality test
        2. Fermat primality test
        3. Baillie-PSW primality test
        4. Lucas primality test
        5. AKS primality test
        6. Sieve of Atkin
        7. Sieve of Eratosthenes
        8. Sieve of Sundaram
      10. Multiplication algorithms
        1. Toom–Cook multiplication
        2. Schönhage–Strassen algorithm
        3. Karatsuba algorithm
      11. Lenstra–Lenstra–Lovász algorithm
    2. 2.2 Computer algebra
      1. Gosper's algorithm
      2. Buchberger's algorithm
      3. Cantor–Zassenhaus algorithm
      4. Knuth–Bendix completion algorithm
      5. Multivariate division algorithm
      6. Faugère's F4 and F5 algorithms
      7. Risch algorithm
      8. Pollard's kangaroo algorithm
      9. Polynomial long division
    3. 2.1 Abstract algebra
      1. Schreier–Sims algorithm
      2. Chien search
      3. ​​Todd–Coxeter algorithm
    4. 2.3 Geometry
      1. Part 2
        1. Euclidean Distance Transform
        2. Gilbert–Johnson–Keerthi distance algorithm
        3. Geometric hashing
        4. Jump-and-Walk algorithm
      2. Part 4
        1. Shoelace algorithm
        2. Point set registration algorithms
        3. ​​Triangulation
          1. Voronoi diagrams
            1. Bowyer–Watson algorithm
            2. Fortune's Algorithm
          2. Marching triangles
          3. Delaunay triangulation
            1. Chew's second algorithm
            2. Ruppert's algorithm
          4. Polygon triangulation algorithms
          5. Quasitriangulation
        4. Rotating calipers
      3. Part 3
        1. Point in polygon algorithms
        2. Minimum bounding box algorithms
        3. Line segment intersection
          1. Shamos–Hoey algorithm
          2. Bentley–Ottmann algorithm
        4. Nearest neighbor search
      4. Part 1
        1. Collision detection algorithms
        2. ​​​Convex hull algorithms
          1. ​Gift wrapping algorithm or Jarvis march
          2. Graham scan
          3. Chan's algorithm
          4. Quickhull
          5. Kirkpatrick–Seidel algorithm
        3. Cone algorithm
        4. Laplacian smoothing
        5. Closest pair problem
    5. 2.5 Numerical algorithms
    6. 2.6 Optimization algorithms
  5. 4. Computer science
    1. Part 2
      1. 4.5 Machine learning and statistical classification
      2. 4.7 Quantum algorithms
      3. 4.6 Programming language theory
      4. 4.8 Theory of computation and automata
    2. Part 1
      1. 4.2 Computer graphics
        1. Part 1
          1. Clipping
            1. Line clipping
              1. Cohen–Sutherland
              2. ​Fast-clipping
              3. Cyrus–Beck
              4. ​Liang–Barsky
              5. ​Nicholl–Lee–Nicholl
            2. Polygon clipping
              1. Vatti clipping algorithm
              2. Sutherland–Hodgman
              3. ​Weiler–Atherton
          2. ​​Discrete Green's Theorem
          3. Contour lines and Isosurfaces
            1. Marching squares
            2. Marching cubes
            3. Marching tetrahedra
          4. ​Flood fill
        2. Part 3
          1. ​Slerp (spherical linear interpolation)
          2. Ramer–Douglas–Peucker algorithm
          3. ​Summed area table
          4. ​Shading
            1. Phong shading
            2. Gouraud shading
        3. Part 2
          1. Midpoint circle algorithm
          2. Hidden surface removal or Visual surface determination
            1. Scanline rendering
            2. Newell's algorithm
            3. Warnock algorithm
            4. ​Painter's algorithm
          3. Global illumination algorithms
            1. Photon mapping
            2. ​Cone tracing
            3. ​Image-based lighting
            4. Ambient occlusion
            5. ​Beam tracing
            6. ​Metropolis light transport
            7. ​Path tracing
            8. Ray tracing
            9. Radiosity
          4. Line Drawing
            1. Digital differential analyzer
            2. ​Xiaolin Wu's line algorithm
            3. Bresenham's line algorithm
      2. 4.4 Digital logic
        1. Espresso heuristic logic minimizer
        2. Quine–McCluskey algorithm
        3. ​Petrick's method
      3. 4.3 Cryptography
        1. Key derivation function
          1. bcrypt
          2. scrypt
          3. PBKDF2
        2. Cryptographic hash functions
          1. ​RTR0
          2. SHA-1
          3. Hash-based message authentication code
          4. SHA-2
          5. SHA-3
          6. ​MD5
          7. ​RIPEMD-160
          8. WHIRLPOOL
          9. ​Tiger (TTH)
        3. Asymmetric (public key) encryption
          1. NTRUEncrypt
          2. ElGamal
          3. Digital Signature Algorithm
          4. Elliptic curve cryptography
          5. RSA
        4. Cryptographically secure pseudo-random number generators
          1. ​Fortuna
          2. ​ Yarrow algorithm
          3. Linear feedback shift register
          4. Blum Blum Shub
        5. Diffie–Hellman key exchange
        6. Symmetric (secret key) encryption
          1. ​IDEA
          2. RC4 (cipher)
          3. Threefish
          4. ​Blowfish
          5. Twofish
          6. Data Encryption Standard (DES)
          7. Advanced Encryption Standard (AES)
          8. Tiny Encryption Algorithm
        7. ​Secret sharing, Secret Splitting, Key Splitting, M of N algorithms
          1. Shamir's Scheme
      4. 4.1 Computer architecture
        1. Tomasulo algorithm
  6. 5. Information theory and signal processing
    1. 5.2 Digital signal processing
      1. 5.2.2 Image processing
        1. Elser difference-map algorithm
        2. Feature detection
          1. ​Canny edge detector
          2. ​Hough transform
          3. ​Generalised Hough transform
          4. ​Marr–Hildreth algorithm
          5. ​SIFT (Scale-invariant feature transform)
        3. Contrast Enhancement
          1. Histogram equalization
          2. Adaptive histogram equalization
        4. Richardson–Lucy deconvolution
        5. ​Blind deconvolution
        6. Connected-component labeling: find and label disjoint regions
        7. ​Dithering and half-toning
          1. Floyd–Steinberg dithering
          2. Ordered dithering
          3. Error diffusion
        8. ​Segmentation
          1. Region growing
          2. ​Random walker algorithm
          3. Watershed transformation
          4. GrowCut algorithm
        9. ​Median filtering
        10. Seam carving
      2. 5.2.1 Digital signal processing
        1. Gerchberg–Saxton algorithm
        2. ​Discrete Fourier transform
          1. Cooley–Tukey FFT algorithm
          2. Bluestein's FFT algorithm
          3. Fast Fourier transform
          4. Bruun's FFT algorithm
          5. Rader's FFT algorithm
          6. ​Prime-factor FFT algorithm
        3. Adaptive-additive algorithm (AA algorithm)
        4. Fast folding algorithm
        5. ​Karplus-Strong string synthesis
        6. ​Goertzel algorithm
    2. 5.1 Coding theory
      1. 5.1.3 Lossy compression algorithms
        1. Image Compression
          1. Block Truncation Coding (BTC)
          2. Fast Cosine Transform algorithms (FCT algorithms)
          3. Embedded Zerotree Wavelet (EZW)
          4. ​Fractal compression
          5. Wavelet compression
          6. Set Partitioning in Hierarchical Trees (SPIHT)
        2. 3Dc
        3. Transform coding
        4. Audio and Speech compression
          1. ​Code-excited linear prediction (CELP)
          2. ​Mu-law algorithm
          3. Linear predictive coding (LPC)
          4. A-law algorithm
          5. ​Warped Linear Predictive Coding (WLPC)
        5. Vector quantization
        6. Video compression
      2. 5.1.2 Lossless compression algorithms
        1. Dynamic Markov compression
        2. Fast Efficient & Lossless Image Compression System (FELICS)
        3. ​Context tree weighting
        4. Entropy encoding
          1. ​​Shannon–Fano coding
          2. Arithmetic coding
            1. Range encoding
          3. Shannon–Fano–Elias coding
          4. Huffman coding
            1. Package-merge algorithm
            2. Adaptive Huffman coding
        5. Burrows–Wheeler transform
        6. Dictionary coders
          1. DEFLATE
          2. Byte pair encoding (BPE)
          3. Lempel–Ziv
            1. Lempel–Ziv–Markov chain algorithm
            2. Lempel–Ziv–Oberhumer
            3. Lempel–Ziv–Welch
            4. LZWL
            5. Lempel–Ziv–Stac
            6. Lempel–Ziv–Storer–Szymanski
            7. LZ77 and LZ78
            8. LZJB
            9. LZX
            10. LZRW
        7. Delta encoding
        8. Entropy coding with known entropy characteristics
          1. Universal codes
            1. Elias delta coding
            2. Fibonacci coding
            3. Exponential-Golomb coding
            4. Levenshtein coding
            5. Elias gamma coding
            6. Elias omega coding
          2. Unary coding
          3. ​Truncated binary encoding
          4. Golomb coding
        9. ​Run-length encoding
        10. SEQUITUR algorithm
        11. Incremental encoding
        12. ​Prediction by partial matching (PPM)
      3. ​5.1.1 Error detection and correction
        1. ​Hamming codes
          1. Hamming(7,4)
          2. Hamming weight (population count)
          3. Hamming distance
        2. ​Forward error correction
        3. BCJR algorithm
        4. ​Gray code
        5. BCH Codes
          1. Reed–Solomon error correction
          2. Berlekamp–Massey algorithm
        6. Redundancy checks
          1. Luhn mod N algorithm
          2. Parity bit
          3. Fletcher's checksum
          4. Longitudinal redundancy check (LRC)
          5. Damm algorithm
          6. Luhn algorithm
          7. Verhoeff algorithm
          8. Adler-32
          9. Cyclic redundancy check
  7. 6 - 10
    1. 10. Operating systems algorithms
      1. Operating systems algorithms
        1. Banker's algorithm
        2. ​Page replacement algorithms
          1. Clock with Adaptive Replacement (CAR)
          2. Adaptive replacement cache
      2. Scheduling
        1. Multi level feedback queue
        2. Rate-monotonic scheduling
        3. Earliest deadline first scheduling
        4. Fair-share scheduling
        5. Round-robin scheduling
        6. Shortest job next
        7. Least slack time scheduling
        8. List scheduling
        9. Top-nodes algorithm
        10. Shortest remaining time
      3. Process synchronization
        1. Lamport's Bakery algorithm
        2. Dekker's algorithm
        3. Peterson's algorithm
      4. Disk scheduling
        1. ​Shortest seek first
        2. Elevator algorithm
    2. 8. Distributed systems algorithms
      1. Distributed systems algorithms
        1. Detection of Process Termination
          1. Dijkstra-Scholten algorithm
          2. Huang's algorithm
        2. Lamport ordering
        3. Bully algorithm
        4. Byzantine fault tolerance
        5. ​Mutual exclusion
          1. Raymond's Algorithm
          2. Naimi-Trehel's log(n) Algorithm
          3. Lamport's Distributed Mutual Exclusion Algorithm
          4. Maekawa's Algorithm
          5. Ricart-Agrawala Algorithm
        6. Paxos algorithm
        7. Clock synchronization
          1. Cristian's algorithm
          2. Marzullo's algorithm
          3. Intersection algorithm
          4. ​Berkeley algorithm
        8. ​Snapshot algorithm
          1. Chandy-Lamport algorithm
        9. Vector clocks
      2. Memory allocation and deallocation algorithms
        1. ​Garbage collectors
          1. Cheney's algorithm
          2. Mark-compact algorithm
          3. ​Generational garbage collector
          4. Mark and sweep
        2. Reference counting
        3. Buddy memory allocation
    3. 7. Database algorithms
      1. ​Join algorithms
        1. Nested loop join
        2. Block nested loop
        3. Sort-Merge Join
        4. Hash join
      2. Algorithms for Recovery and Isolation Exploiting Semantics (ARIES)
    4. ​9. Networking
      1. ​Luleå algorithm
      2. ​Network congestion
        1. Nagle's algorithm
        2. Exponential backoff
      3. Karn's Algorithm
    5. 6. Software engineering
      1. Unicode Collation Algorithm
      2. ​Double dabble
      3. ​CHS conversion
      4. ​Hash Function
        1. ​Pearson hashing
        2. ​Zobrist hashing
        3. Fowler–Noll–Vo hash function
      5. Xor swap algorithm
      6. Cache algorithms
by Spatial Bookworm
About this document
This document contains descriptions of most algorithms. Currently algorithms are organized by categories, but within categories their order is alphabetical. You are welcome to create a copy of this document, add and re-arrange information. You're also welcome to share the result. The content is taken from Wikipedia.
Published on 6 Feb 2017
164 cubes
669 notes
7.54 Mb
From the same author
121 cubes
760 notes
1.37 Mb
207 cubes
1330 notes
2.29 Mb
Embed viewer
Embed viewer
Share
Direct link