Difference between revisions of "Computer science eponyms"

From dankwiki
(Created page with "Computer science needs more eponyms, in the vein of [http://en.wikipedia.org/wiki/Mordenkainen#Spells Mordenkainen]. Collect them all, and impress your friends! The vast major...")
 
(Bélády's Anomaly)
 
(52 intermediate revisions by the same user not shown)
Line 1: Line 1:
Computer science needs more eponyms, in the vein of [http://en.wikipedia.org/wiki/Mordenkainen#Spells Mordenkainen]. Collect them all, and impress your friends! The vast majority of links below are stubs -- I might make a project one day of filling them all in, but I'd likely sell the result as a [[book ideas|book]].
Computer science needs more eponyms, in the vein of [http://en.wikipedia.org/wiki/Mordenkainen#Spells Mordenkainen]. Collect them all, and impress your friends! I might make a project one day of summarizing these entries, but I'd likely sell the result as a [[book ideas|book]].


*'''FIXME''' Tarjan has something like 20,004 algorithms, and all of them are outstanding
*'''FIXME''' Tarjan has something like 20,004 algorithms, and all of them are outstanding


Explicitly '''not included''' in this list are: general logic (Peano and Presburger arithmetic), mathematical entities not primarily associated with computer science (Markov's inequality, Chapman-Kolmogorov equation, Young tableaux), physical theories to which computer science is merely applied (Navier-Stokes equations, Taylor-Couette flow), or statistical entities not primarily associated with computer science (Ziph's Law, Parmeto efficiency). Explicitly '''included''' are: terms from computer engineering ([[Mead-Conway Rules]], [[Ling adders]]) and mathematical entities primarily associated with computer science.
Explicitly '''not included''' in this list are: general logic (Peano and Presburger arithmetic), mathematical entities not primarily associated with computer science (Markov's inequality, Chapman-Kolmogorov equation, Young tableaux), physical theories to which computer science is merely applied (Navier-Stokes equations, Taylor-Couette flow), or statistical entities not primarily associated with computer science (Ziph's Law, Pareto efficiency). Explicitly '''included''' are: terms from computer engineering (Mead-Conway rules, Ling adders) and mathematical entities primarily associated with computer science.


'''UPDATE''' the threshold for inclusion is now: De Morgan's Laws. If you're not more computer sciency than De Morgan's Laws, you ain't gettin' in. [[User:Dank|Dank]] 12:25, 3 October 2011 (CDT)
'''UPDATE''' the threshold for inclusion is now: De Morgan's Laws. If you're not more computer sciency than De Morgan's Laws, you ain't gettin' in. [[User:Dank|Dank]] 12:25, 3 October 2011 (CDT)




* Aanderaa–Rosenberg Conjecture
* '''Aanderaa–Rosenberg Conjecture''' suggests that non-trivial monotonicity properties of undirected graphs can only be solved by ''Ω(N<sup>2</sup>)'' algorithms on ''N'' vertices (these are all evasive decision trees on all possible edges)
* Adelson-Velskii-Landis Trees
* '''Adam7 Algorithm''' is a 2D, 7-pass interlacing scheme optionally used by PNG due to Adam Costello
* Aho-Corasick Algorithm
* '''Adleman's Theorem''' states that P/poly contains all problems solvable in randomized polynomial time
* Akra-Bazzi Method
* '''Adelson-Velskii-Landis Trees''' are self-height-balancing binary search trees, optimizing for lookup over modification viz. red-black trees
* '''Aho-Corasick Algorithm''' extends the Knuth-Morris-Pratt automaton to match multiple strings in one pass of a text
* '''Akra-Bazzi Method''' generalizes the "master method" of Bentley, Haken, and Saxe for subproblems of significantly different size
* Amdahl's Law
* Amdahl's Law
* Andersen's Algorithm
* Andersen's Algorithm
* '''Armstrong's axioms''' are a set of inference rules which generate all functional dependencies of a relational database. Similarly, an '''Armstrong relation''' satisfies all the functional dependencies in the closure F<sup>+</sup> (and only those dependencies).


* Backus-Naur Form
* Backus-Naur Form
Line 23: Line 26:
* Baskett, Chandy, Muntz and Palacios network
* Baskett, Chandy, Muntz and Palacios network
* Batcher's Odd-Even Merge
* Batcher's Odd-Even Merge
* '''Bayer Filter''' mosaics arrange RGB color filters on a square array of photosensors, and are used in a majority of single-chip image sensors. It uses twice as many green sensors as red or blue, to mimic the physiology of the human eye
* '''Bélády's anomaly''' is the phenomenon in which increasing the number of page frames results in an ''increase'' in the number of page faults for certain memory access patterns, especially when using FIFO page replacement
* Bell-La Padula model
* Bell-La Padula model
* Bellman-Ford Algorithm
* Bellman-Ford Algorithm
Line 46: Line 51:
* Bremermann's Limit
* Bremermann's Limit
* Brent's Adder
* Brent's Adder
* Brent's Algorithm
* '''Brent's Algorithm''' detects cycles using two pointers, and finds the length of the cycle directly
* Brent's Theorem
* '''Brent's Method''' is a hybrid root-finding algorithm combining bisection, the secant method, and inverse quadratic interpolation
* '''Brent's Theorem''' aka '''Brent's Law''' states that p < N processors can simulate N in T_p ≤ T_N + (T_1 - T_N)/p
* Bresenham's Algorithm
* Bresenham's Algorithm
* Brewer's Theorem
* Brewer's Theorem
Line 69: Line 75:
* Chakravala's Algorithm
* Chakravala's Algorithm
* Chan's Algorithm
* Chan's Algorithm
* Chang-Roberts Algorithm
* the '''Chang-Roberts Algorithm''' elects leaders for distributed systems.
* Cheney's Algorithm
* Cheney's Algorithm
* Chew's Second Algorithm
* Chew's Second Algorithm
* Chien search
* Chien search
* '''Cholesky decomposition''' expands Hermitian positive-definite matrices into products of a lower triangular matrix and its conjugate transpose. solved using the Cholesky–Crout and Cholesky–Banachiewicz algorithms.
* Chomsky Hierarchy
* Chomsky Hierarchy
* Chomsky Normal Form
* Chomsky Normal Form
Line 84: Line 91:
* Cocke-Younger-Kasami Algorithm
* Cocke-Younger-Kasami Algorithm
* Cohen-Sutherland algorithm
* Cohen-Sutherland algorithm
* '''Coffman conditions''' enumerate the four conditions necessary and sufficient for deadlock within a system (mutual exclusion, hold-and-wait, a lack of preemption, and circular wait)
* Commentz-Walter Algorithm
* Commentz-Walter Algorithm
* [https://en.wikipedia.org/wiki/Conway%27s_law Conway's Law]
* Cook reduction
* Cook reduction
* Cook-Levin Theorem
* the '''Cook-Levin Theorem''' (sometimes just '''Cook Theorem''') proves that the Boolean satisfiability problem is NP-complete.
* Cooley-Tukey Algorithm
* the '''Cooley-Tukey Algorithm''' is the workhorse algorithm for Fast Fourier Transforms.
* Coppersmith-Winograd Algorithm
* the '''Coppersmith-Winograd Algorithm''' multiplied matrices in the least time complexity from 1990-2010, and used the "laser method" employed by all improvements since.
* Craig, Landin and Hagersten lock
* Craig, Landin and Hagersten lock
* Cranfield method
* Cranfield method
* (preconditioned) Crank–Nicolson Algorithm
* Crusader’s Convergence Algorithm
* Crusader’s Convergence Algorithm


Line 106: Line 116:
* Dijkstra's Algorithm
* Dijkstra's Algorithm
* Dinic's Algorithm
* Dinic's Algorithm
* '''DiVincenzo's criteria''' specify conditions necessary for a quantum computer
* Dolev's Algorithm
* Dolev's Algorithm
* Doo-Sabin subdivision surface
* Doo-Sabin subdivision surface
Line 112: Line 123:


* Earley Parser
* Earley Parser
* '''Edmonds's matching algorithm''' constructs maximum matchings on graphs in O(|E||V|²)
* Edmonds-Karp Algorithm
* Edmonds-Karp Algorithm
* Euclid's Algorithm
* Euclid's Algorithm


* Fagin's Theorem
* '''Fagin's Theorem''' states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP
* Faugère F5 algorithm
* Faugère F5 algorithm
* Fiat-Shamir Heuristic
* Fiat-Shamir Heuristic
Line 129: Line 141:
* Fredkin gate
* Fredkin gate
* Friedberg-Muchnik Theorem
* Friedberg-Muchnik Theorem
* Fürer's algorithm
* Fruchterman-Reingold heuristic
* '''Fürer's algorithm''' multiplies two ''n''-digit numbers in ''O(nlgn*2<sup>O(lg*n)</sup>)''


* Gabbay's separation theorem
* Gabbay's separation theorem
Line 148: Line 161:
* Gosper's Loop Detection Algorithm
* Gosper's Loop Detection Algorithm
* Gouraud shading
* Gouraud shading
* Graham Scan
* The '''Graham Scan''' solves for the convex hull of a set of points in ''O(NlgN)''.
* The '''Graham-Andrew Algorithm''' modifies the Graham Scan to solve for convex hulls in ''O(N)'' best case.
* Graham-Denning Model
* Graham-Denning Model
* Gram–Schmidt process
* Gram–Schmidt process
Line 157: Line 171:
* Guruswami-Sudan Algorithm
* Guruswami-Sudan Algorithm
* Gustafson's Law
* Gustafson's Law
* '''Gutmann's Method''' is a 35-phase recipe for destroying data on ferromagnetic drives.
* Guttman-Rosler transform


* Hamming code
* Hamming code
* Hamming distance
* Hamming distance
* '''Heckel's algorithm''' isolates changes between files, and is the basis for <tt>diff</tt> [https://dl.acm.org/doi/10.1145/359460.359467 CACM 1978]
* Hennessy-Milner Logic
* Hennessy-Milner Logic
* Herlihy's wait-free hierarchy
* Herlihy's wait-free hierarchy
Line 189: Line 206:
* Kahan Summation Algorithm
* Kahan Summation Algorithm
* Kannan's Theorem
* Kannan's Theorem
* Karatsuba Algorithm
* '''Karatsuba's Algorithm''' multiplies two ''n''-digit numbers using ''n<sup>log<sub>2</sub>3</sup>'' single-digit mults
* Karger's Algorithm
* Karger's Algorithm
* '''Karn's algorithm''' extracts accurate [[TCP]] RTT measures, Karn-Partridge 1987
* Karmarkar's algorithm
* Karmarkar's algorithm
* Karnaugh map
* Karnaugh map
Line 196: Line 214:
* Karp-Flatt metric
* Karp-Flatt metric
* Karp-Lipton Theorem
* Karp-Lipton Theorem
* Kamada-Kawai algorithm
* Kernighan-Lin algorithm
* Kernighan-Lin algorithm
* Kirkpatrick-Seidel Algorithm
* Kirkpatrick-Seidel Algorithm
Line 207: Line 226:
* Koenig Lookup
* Koenig Lookup
* Kohonen Algorithm
* Kohonen Algorithm
* Kohonen network
* Kolmogorov complexity
* Kolmogorov complexity
* Koomey's Law
* Koomey's Law
Line 212: Line 232:
* Krapchenko's Adder
* Krapchenko's Adder
* Kruskal's Algorithm
* Kruskal's Algorithm
* Kryder's Law
* Kung-Leiserson systolic array
* Kung-Leiserson systolic array
* Kuroda Normal Form
* Kuroda Normal Form
Line 232: Line 253:
* Liskov's Substitution Principle
* Liskov's Substitution Principle
* Lloyd's algorithm
* Lloyd's algorithm
* '''Loss-DiVincenzo machines''' are quantum computers based off electron spin as confined to quantum dots
* Luby's algorithm
* Luhn Algorithm
* Luhn Algorithm
* Luleå Algorithm
* Luleå Algorithm
Line 244: Line 267:
* Mellor-Crummey and Scott lock
* Mellor-Crummey and Scott lock
* Merkle–Damgård construction
* Merkle–Damgård construction
* Metropolis-Hastings algorithm
* The '''Metropolis-Hastings algorithm''' for MCMC obtains samples from a probability distribution that is [https://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm difficult to directly sample]
* Miller-Rabin Primality Test
* Miller-Rabin Primality Test
* Minsky-Fenichel-Yochelson Algorithm
* Minsky-Fenichel-Yochelson Algorithm
Line 262: Line 285:
* Nisan's Generator
* Nisan's Generator


* '''Ousterhout's dichotomy/fallacy''' a taxonomy of ''systems'' vs ''scripting'' languages
* Otway-Rees Protocol
* Otway-Rees Protocol


* '''Paeth-Tanaka Algorithm''' rotates images via a method of three shears
* '''Paeth Filter''' performs 2D image compression in PNG
* Peterson's Algorithm
* Peterson's Algorithm
* Petrick's method
* Petrick's method
Line 270: Line 296:
* Pollaczek–Khinchine formula
* Pollaczek–Khinchine formula
* Pollard's Kangaroo Algorithm
* Pollard's Kangaroo Algorithm
* '''Pollard's ρ Algorithm''' aka '''Pollard's rho Algorithm''' factors integers in running time expected to be proportional to the square root of the smallest prime factor of the number being factored
* Popek-Goldberg virtualization requirements
* Popek-Goldberg virtualization requirements
* Post's correspondence problem
* Post's correspondence problem
* <b>Post's Lattice</b> is the lattice of all clones on {0,1}, ordered by inclusion. It is used to prove sets of connectives to be functionally complete (e.g. NAND and NOR both generate functionally complete Boolean algebras).
* Postel's Law
* Postel's Law
* Prim's Algorithm
* Prim's Algorithm
* '''Proebsting's Law''' claims that compiler technology doubles computing power [http://proebsting.cs.arizona.edu/law.html every 18 years]
* Prüfer Coding
* Prüfer Coding
* Prüfer Sequence
* Prüfer Sequence
Line 280: Line 309:
* Quine-McLuskey algorithm
* Quine-McLuskey algorithm


* Rabin Automata
* Rabin's Information Dispersal Algorithm
* Rabin's Information Dispersal Algorithm
* Rabin-Karp Algorithm
* Rabin-Karp Algorithm
Line 285: Line 315:
* Radovic-Hagersten lock
* Radovic-Hagersten lock
* Raymond's Algorithm
* Raymond's Algorithm
* Reed-Muller code
* Reed-Solomon correction code
* Reed-Solomon correction code
* Ricart-Agrawala Algorithm
* Ricart-Agrawala Algorithm
Line 291: Line 322:
* Risch Algorithm
* Risch Algorithm
* Rivest-Shamir-Adleman Algorithm
* Rivest-Shamir-Adleman Algorithm
* '''Rocchio's Algorithm''' classifies information relevance using nearest centroids
* Ruppert's Algorithm
* Ruppert's Algorithm


* '''Sattolo's Algorithm''' generates a 1-cyclic derangement of an array (a permutation such that every element ends up in a new position)
* Savitch's Theorem
* Savitch's Theorem
* Schensted Algorithm
* Schensted Algorithm
* Schlick's approximation
* Schlick's approximation
* The '''Schönhage–Strassen algorithm''' multiplies two ''n''-digit numbers in ''O(nlgnlglgn)'' bit complexity using FFTs
* Schoof's Algorithm
* Schoof's Algorithm
* Schreier-Sims Algorithm
* Schreier-Sims Algorithm
* Schwartzian transform
* Sethi-Ullman Algorithm
* Sethi-Ullman Algorithm
* Shamir's Secret Sharing Scheme
* Shamir's Secret Sharing Scheme
Line 311: Line 346:
* Strassen's Algorithm
* Strassen's Algorithm
* Suurballe's Algorithm
* Suurballe's Algorithm
* Sweeney-Robertson-Tocher division algorithm


* Tarjan's Algorithm
* Tarjan's Algorithm
Line 321: Line 357:
* Tomasulo's Algorithm
* Tomasulo's Algorithm
* Tonelli-Shanks Algorithm
* Tonelli-Shanks Algorithm
* Toom-Cook Algorithm
* The '''Toom-Cook Algorithm''' multiplies two ''n''-digit numbers using ''n<sup>log(5)/log(3)</sup>'' single-digit mults
* Turing Degree
* Turing Degree
* Turing Machines
* Turing Machines
Line 333: Line 369:
* Viola-Jones face detection
* Viola-Jones face detection
* Volder's algorithm
* Volder's algorithm
* Von Neumann architecture
* von Neumann architecture


* Wagner-Fischer Algorithm
* Wagner-Fischer Algorithm
Line 339: Line 375:
* Wallace tree
* Wallace tree
* Warnsdorff's Algorithm
* Warnsdorff's Algorithm
* The '''Williams State Machine''' is a common [https://vt100.net/emu/dec_ansi_parser parsing automaton] for DEC virtual terminal input
* Winograd's Algorithm
* Winograd's Algorithm
* Witten-Bell smoothing
* Witten-Bell smoothing
Line 346: Line 383:


* Yao's Principle
* Yao's Principle
* Yeh's Algorithm
* '''Yeh's Algorithm''' is a two-level adaptive training algorithm designed by Yeh and Patt in 1991. A branch history register is used to maintain branch behavior for a specific pattern of branch history, and 4-bit counters are used for each BTB set.


* Zhu-Takaoka Algorithm
* Zhu-Takaoka Algorithm
* Zimmermann-Sassaman key-signing protocol
* Zimmermann-Sassaman key-signing protocol
* Zobrist hashing
* Zobrist hashing

Latest revision as of 16:42, 30 April 2022

Computer science needs more eponyms, in the vein of Mordenkainen. Collect them all, and impress your friends! I might make a project one day of summarizing these entries, but I'd likely sell the result as a book.

  • FIXME Tarjan has something like 20,004 algorithms, and all of them are outstanding

Explicitly not included in this list are: general logic (Peano and Presburger arithmetic), mathematical entities not primarily associated with computer science (Markov's inequality, Chapman-Kolmogorov equation, Young tableaux), physical theories to which computer science is merely applied (Navier-Stokes equations, Taylor-Couette flow), or statistical entities not primarily associated with computer science (Ziph's Law, Pareto efficiency). Explicitly included are: terms from computer engineering (Mead-Conway rules, Ling adders) and mathematical entities primarily associated with computer science.

UPDATE the threshold for inclusion is now: De Morgan's Laws. If you're not more computer sciency than De Morgan's Laws, you ain't gettin' in. Dank 12:25, 3 October 2011 (CDT)


  • Aanderaa–Rosenberg Conjecture suggests that non-trivial monotonicity properties of undirected graphs can only be solved by Ω(N2) algorithms on N vertices (these are all evasive decision trees on all possible edges)
  • Adam7 Algorithm is a 2D, 7-pass interlacing scheme optionally used by PNG due to Adam Costello
  • Adleman's Theorem states that P/poly contains all problems solvable in randomized polynomial time
  • Adelson-Velskii-Landis Trees are self-height-balancing binary search trees, optimizing for lookup over modification viz. red-black trees
  • Aho-Corasick Algorithm extends the Knuth-Morris-Pratt automaton to match multiple strings in one pass of a text
  • Akra-Bazzi Method generalizes the "master method" of Bentley, Haken, and Saxe for subproblems of significantly different size
  • Amdahl's Law
  • Andersen's Algorithm
  • Armstrong's axioms are a set of inference rules which generate all functional dependencies of a relational database. Similarly, an Armstrong relation satisfies all the functional dependencies in the closure F+ (and only those dependencies).
  • Backus-Naur Form
  • Bajard-Kla-Muller algorithm
  • Ball-Larus Heuristics
  • Banerjee Inequality
  • Barendregt convention
  • Barendregt-Geuvers-Klop Conjecture
  • Baskett, Chandy, Muntz and Palacios network
  • Batcher's Odd-Even Merge
  • Bayer Filter mosaics arrange RGB color filters on a square array of photosensors, and are used in a majority of single-chip image sensors. It uses twice as many green sensors as red or blue, to mimic the physiology of the human eye
  • Bélády's anomaly is the phenomenon in which increasing the number of page frames results in an increase in the number of page faults for certain memory access patterns, especially when using FIFO page replacement
  • Bell-La Padula model
  • Bellman-Ford Algorithm
  • Beneš network
  • Bentley-Ottman Algorithm
  • Berlekamp-Massey Algorithm
  • Berman–Hartmanis conjecture
  • Bernstein chaining
  • Bernstein conditions
  • Biba Integrity Model
  • Blinn-Phong shading
  • Blom's Scheme
  • Bloom filter
  • Bluestein's FFT
  • Blum's axioms
  • Blum's Speedup Theorem
  • Blum-Blum-Shub random number generator
  • Boehm-Demers-Weiser garbage collector
  • Booth's Algorithm
  • Borůvka's Algorithm
  • Bowyer-Watson Algorithm
  • Boyer-Moore Algorithm
  • Bremermann's Limit
  • Brent's Adder
  • Brent's Algorithm detects cycles using two pointers, and finds the length of the cycle directly
  • Brent's Method is a hybrid root-finding algorithm combining bisection, the secant method, and inverse quadratic interpolation
  • Brent's Theorem aka Brent's Law states that p < N processors can simulate N in T_p ≤ T_N + (T_1 - T_N)/p
  • Bresenham's Algorithm
  • Brewer's Theorem
  • Brodal Queue
  • Broder's Method
  • Bron-Kerbosch Algorithm
  • Brooks-Iyengar Algorithm
  • Buchberger Algorithm
  • Burrows-Wheeler Transform
  • Buzen's Algorithm
  • Callahan-Koblenz algorithm
  • Cannon's Algorithm
  • Cantor-Zassenhaus Algorithm
  • Carmack's Reverse
  • Chaff Algorithm
  • Chaitin's algorithm
  • Chaitin's Constant
  • Chaitin-Briggs algorithm
  • Chaitin–Kolmogorov random numbers
  • Chakravala's Algorithm
  • Chan's Algorithm
  • the Chang-Roberts Algorithm elects leaders for distributed systems.
  • Cheney's Algorithm
  • Chew's Second Algorithm
  • Chien search
  • Cholesky decomposition expands Hermitian positive-definite matrices into products of a lower triangular matrix and its conjugate transpose. solved using the Cholesky–Crout and Cholesky–Banachiewicz algorithms.
  • Chomsky Hierarchy
  • Chomsky Normal Form
  • Chomsky-Schützenberger theorem
  • Christofides Algorithm
  • Church-Rosser Theorem
  • Church-Turing Thesis
  • Clos network
  • Cobham Axioms
  • Cobham's thesis
  • Cocke-Younger-Kasami Algorithm
  • Cohen-Sutherland algorithm
  • Coffman conditions enumerate the four conditions necessary and sufficient for deadlock within a system (mutual exclusion, hold-and-wait, a lack of preemption, and circular wait)
  • Commentz-Walter Algorithm
  • Conway's Law
  • Cook reduction
  • the Cook-Levin Theorem (sometimes just Cook Theorem) proves that the Boolean satisfiability problem is NP-complete.
  • the Cooley-Tukey Algorithm is the workhorse algorithm for Fast Fourier Transforms.
  • the Coppersmith-Winograd Algorithm multiplied matrices in the least time complexity from 1990-2010, and used the "laser method" employed by all improvements since.
  • Craig, Landin and Hagersten lock
  • Cranfield method
  • (preconditioned) Crank–Nicolson Algorithm
  • Crusader’s Convergence Algorithm
  • Dadda Multiplier
  • Damerau-Levenshtein distance
  • Damm Algorithm
  • Davis-Putnam Algorithm
  • Davis-Putnam-Logemann-Loveland Algorithm
  • De Bruijn presentation
  • De Bruijn string
  • Dekker's Algorithm
  • Delaunay's Triangulation
  • Dennard Scaling
  • Diffie-Hellman Key Exchange
  • Dijkstra's Algorithm
  • Dinic's Algorithm
  • DiVincenzo's criteria specify conditions necessary for a quantum computer
  • Dolev's Algorithm
  • Doo-Sabin subdivision surface
  • Duff's Device
  • Dyck Language
  • Earley Parser
  • Edmonds's matching algorithm constructs maximum matchings on graphs in O(|E||V|²)
  • Edmonds-Karp Algorithm
  • Euclid's Algorithm
  • Fagin's Theorem states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP
  • Faugère F5 algorithm
  • Fiat-Shamir Heuristic
  • Fibonacci Heap
  • Fisher-Yates shuffle
  • Fletcher's Checksum
  • Floyd's Algorithm
  • Floyd-Steinberg dithering
  • Flynn Taxonomy
  • Ford-Fulkerson Algorithm
  • Fortune's Algorithm
  • Fox's Algorithm
  • Fredkin gate
  • Friedberg-Muchnik Theorem
  • Fruchterman-Reingold heuristic
  • Fürer's algorithm multiplies two n-digit numbers in O(nlgn*2O(lg*n))
  • Gabbay's separation theorem
  • Gabow's Algorithm
  • Gal's Accurate Tables
  • Gale-Church Algorithm
  • Gale-Shapley algorithm
  • Gilbert-Johnson-Keerthi Algorithm
  • Girard's Paradox
  • Girvan-Newman Algorithm
  • Givens rotation
  • Glushkov Automata
  • Goldreich-Goldwasser-Halevi scheme
  • Gomory-Hu Tree
  • Gordon–Newell theorem
  • Gosper's Hack
  • Gosper's Hypergeometric Algorithm
  • Gosper's Loop Detection Algorithm
  • Gouraud shading
  • The Graham Scan solves for the convex hull of a set of points in O(NlgN).
  • The Graham-Andrew Algorithm modifies the Graham Scan to solve for convex hulls in O(N) best case.
  • Graham-Denning Model
  • Gram–Schmidt process
  • Gray codes
  • Greibach Normal Form
  • Grover's Algorithm
  • Grzegorczyk hierarchy
  • Guruswami-Sudan Algorithm
  • Gustafson's Law
  • Gutmann's Method is a 35-phase recipe for destroying data on ferromagnetic drives.
  • Guttman-Rosler transform
  • Hamming code
  • Hamming distance
  • Heckel's algorithm isolates changes between files, and is the basis for diff CACM 1978
  • Hennessy-Milner Logic
  • Herlihy's wait-free hierarchy
  • Hirschberg's Algorithm
  • Hoare logic
  • Holevo's Theorem
  • Holland's schema theorem
  • Hong-Kung bound
  • Hopcroft-Karp Algorithm
  • Hopfield net
  • Horn clauses
  • Householder transformation
  • Huet's Zipper
  • Hunt-McIlroy Algorithm
  • Iliffe vector
  • Immerman–Szelepcsényi theorem
  • Jackson network
  • Jackson's theorem
  • Jaro-Winkler distance
  • Jefferson's Time Warp
  • Jelinek-Mercer smoothing
  • Jensen's Device
  • Johnson's Algorithm
  • Kabsch Algorithm
  • Kadane's Algorithm
  • Kahan Summation Algorithm
  • Kannan's Theorem
  • Karatsuba's Algorithm multiplies two n-digit numbers using nlog23 single-digit mults
  • Karger's Algorithm
  • Karn's algorithm extracts accurate TCP RTT measures, Karn-Partridge 1987
  • Karmarkar's algorithm
  • Karnaugh map
  • Karp reduction
  • Karp-Flatt metric
  • Karp-Lipton Theorem
  • Kamada-Kawai algorithm
  • Kernighan-Lin algorithm
  • Kirkpatrick-Seidel Algorithm
  • Kleene Closure
  • Kleene Plus
  • Kleene Star
  • Kleene–Rosser Paradox
  • Kneser-Ney smoothing
  • Knuth Shuffle
  • Knuth-Morris-Pratt Algorithm
  • Koenig Lookup
  • Kohonen Algorithm
  • Kohonen network
  • Kolmogorov complexity
  • Koomey's Law
  • Kosaraju's Algorithm
  • Krapchenko's Adder
  • Kruskal's Algorithm
  • Kryder's Law
  • Kung-Leiserson systolic array
  • Kuroda Normal Form
  • Ladner's Theorem
  • Lamport's Bakery Algorithm
  • Lamport's Clock
  • Lamport's Hash
  • Lee-Seung algorithm
  • Lehmer random number generator
  • Lehmer's GCD Algorithm
  • Lempel-Ziv-Welch compression
  • Levenshtein automaton
  • Levenshtein distance
  • Levin reduction
  • Liang-Barsky algorithm
  • Lin-Kernighan Heuristic
  • Linde-Buzo-Gray algorithm
  • Ling adders
  • Liskov's Substitution Principle
  • Lloyd's algorithm
  • Loss-DiVincenzo machines are quantum computers based off electron spin as confined to quantum dots
  • Luby's algorithm
  • Luhn Algorithm
  • Luleå Algorithm
  • Maekawa's Algorithm
  • Mahaney's Theorem
  • Manning algorithm
  • Marzullo algorithm
  • McFarling-style branch predictor
  • Mead-Conway Rules
  • Mealy machine
  • Mellor-Crummey and Scott lock
  • Merkle–Damgård construction
  • The Metropolis-Hastings algorithm for MCMC obtains samples from a probability distribution that is difficult to directly sample
  • Miller-Rabin Primality Test
  • Minsky-Fenichel-Yochelson Algorithm
  • Montgomery reduction
  • Moore machine
  • Moore's Law
  • Morgensen-Scott encoding
  • Möller-Trumbore algorithm
  • Nagle's algorithm
  • Nassi-Shneiderman diagram
  • Needham-Schroeder Protocol
  • Needleman-Wunsch Algorithm
  • Neuman-Stubblebine Protocol
  • Nevill-Manning algorithm
  • Nick's Class
  • Nisan's Generator
  • Ousterhout's dichotomy/fallacy a taxonomy of systems vs scripting languages
  • Otway-Rees Protocol
  • Paeth-Tanaka Algorithm rotates images via a method of three shears
  • Paeth Filter performs 2D image compression in PNG
  • Peterson's Algorithm
  • Petrick's method
  • Phong shading
  • Plotkin's Sticky Bit
  • Pollaczek–Khinchine formula
  • Pollard's Kangaroo Algorithm
  • Pollard's ρ Algorithm aka Pollard's rho Algorithm factors integers in running time expected to be proportional to the square root of the smallest prime factor of the number being factored
  • Popek-Goldberg virtualization requirements
  • Post's correspondence problem
  • Post's Lattice is the lattice of all clones on {0,1}, ordered by inclusion. It is used to prove sets of connectives to be functionally complete (e.g. NAND and NOR both generate functionally complete Boolean algebras).
  • Postel's Law
  • Prim's Algorithm
  • Proebsting's Law claims that compiler technology doubles computing power every 18 years
  • Prüfer Coding
  • Prüfer Sequence
  • Quines
  • Quine-McLuskey algorithm
  • Rabin Automata
  • Rabin's Information Dispersal Algorithm
  • Rabin-Karp Algorithm
  • Rader-Brenner Algorithm
  • Radovic-Hagersten lock
  • Raymond's Algorithm
  • Reed-Muller code
  • Reed-Solomon correction code
  • Ricart-Agrawala Algorithm
  • Rice's Theorem
  • Rice-Shapiro Theorem
  • Risch Algorithm
  • Rivest-Shamir-Adleman Algorithm
  • Rocchio's Algorithm classifies information relevance using nearest centroids
  • Ruppert's Algorithm
  • Sattolo's Algorithm generates a 1-cyclic derangement of an array (a permutation such that every element ends up in a new position)
  • Savitch's Theorem
  • Schensted Algorithm
  • Schlick's approximation
  • The Schönhage–Strassen algorithm multiplies two n-digit numbers in O(nlgnlglgn) bit complexity using FFTs
  • Schoof's Algorithm
  • Schreier-Sims Algorithm
  • Schwartzian transform
  • Sethi-Ullman Algorithm
  • Shamir's Secret Sharing Scheme
  • Shamos-Hoey Algorithm
  • Shor's Algorithm
  • Sipser–Lautemann theorem
  • Smith's Algorithm
  • Smith-Waterman algorithm
  • Solomonoff-Levin distribution
  • Steensgaard's Algorithm
  • Stehlé-Zimmermann algorithm
  • Steinhaus-Johnson-Trotter algorithm
  • Strassen's Algorithm
  • Suurballe's Algorithm
  • Sweeney-Robertson-Tocher division algorithm
  • Tarjan's Algorithm
  • Tarjan's Dynamic Tree
  • Tarjan's Least Common Ancestors Algorithm
  • Thompson Automata
  • Timsort
  • Toda's theorem
  • Todd–Coxeter algorithm
  • Tomasulo's Algorithm
  • Tonelli-Shanks Algorithm
  • The Toom-Cook Algorithm multiplies two n-digit numbers using nlog(5)/log(3) single-digit mults
  • Turing Degree
  • Turing Machines
  • Ukkonen's Algorithm
  • Valiant-Vazirani Theorem
  • Van Jacobson Channels
  • Van Wijngaarden Grammars
  • Verhoeff Algorithm
  • Viola-Jones face detection
  • Volder's algorithm
  • von Neumann architecture
  • Wagner-Fischer Algorithm
  • Wallace Multiplier
  • Wallace tree
  • Warnsdorff's Algorithm
  • The Williams State Machine is a common parsing automaton for DEC virtual terminal input
  • Winograd's Algorithm
  • Witten-Bell smoothing
  • Wu's Line Algorithm
  • Wu-Manber Algorithm
  • Wyllie's List Ranking
  • Yao's Principle
  • Yeh's Algorithm is a two-level adaptive training algorithm designed by Yeh and Patt in 1991. A branch history register is used to maintain branch behavior for a specific pattern of branch history, and 4-bit counters are used for each BTB set.
  • Zhu-Takaoka Algorithm
  • Zimmermann-Sassaman key-signing protocol
  • Zobrist hashing