Check out my first novel, midnight's simulacra!

Computer science eponyms: Difference between revisions

From dankwiki
No edit summary
No edit summary
 
(26 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! I might make a project one day of [[book ideas|summarizing these entries]].
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 [[book ideas|summarizing these entries]].


*'''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, Herbrandization), 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), nor 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).


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 at least as computer sciency as '''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)




Line 18: Line 16:
* Andersen's Algorithm
* Andersen's Algorithm
* Angluin's algorithm
* Angluin's algorithm
* '''Arikan's PAC Codes''' aka polarization-adjusted convolutional [https://en.wikipedia.org/wiki/Polar_code_(coding_theory) polar coding] outperform CRC-aided and purely convolutional polar codes, approaching the theoretical channel capacity for short blocklengths.
* '''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).
* '''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).


Line 23: Line 22:
* Bajard-Kla-Muller algorithm
* Bajard-Kla-Muller algorithm
* Ball-Larus Heuristics
* Ball-Larus Heuristics
* Banerjee Inequality
* the '''Banerjee test''' can demonstrate the absence of [[Compiler_Design|control flow dependencies]] in certain types of loops
* Barendregt convention
* Barendregt convention
* Barendregt-Geuvers-Klop Conjecture
* Barendregt-Geuvers-Klop Conjecture
* Barnes-Hut simulation
* Barnes-Hut simulation
* the '''Barton-Nackman trick''' is an idiom in C++ effecting restricted template expansion
* 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
* '''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 algorithm''' is the theoretically best cache-replacement algorithm, one which discards information that will not be needed until the furthest time into the future (this is not usually knowable)
* '''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
* '''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
* the '''Bellman Equation''' specifies for a problem the necessary condition for optimality of dynamic programming
* Bellman-Ford Algorithm
* Bellman-Ford Algorithm
* Beneš network
* Beneš network
Line 53: Line 55:
* Bowyer-Watson Algorithm
* Bowyer-Watson Algorithm
* Boyer-Moore Algorithm
* Boyer-Moore Algorithm
* the <b>Brassard-Høyer-Tapp algorithm</b> solves the collision problem on a quantum computer in O(n<sup>⅓</sup>) queries
* Bremermann's Limit
* Bremermann's Limit
* '''Brent's Adder''' is logn + O(log1/2n) depth and O(nlg n) size
* '''Brent's Adder''' is logn + O(log1/2n) depth and O(nlg n) size
* '''Brent's Algorithm''' detects cycles using two pointers, and finds the length of the cycle directly
* '''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 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
* '''Brent's Theorem''' aka '''Brent's Law''' states that p < N processors can simulate N in T<sub>p</sub> T<sub>N</sub> + (T<sub>1</sub> - T<sub>N</sub>)/p
* Bresenham's Algorithm
* Bresenham's Algorithm
* Brewer's Theorem
* Brewer's Theorem
Line 79: Line 82:
* Chaitin–Kolmogorov random numbers
* Chaitin–Kolmogorov random numbers
* Chakravala's Algorithm
* Chakravala's Algorithm
* Chan's Algorithm
* '''Chan's Algorithm''' computes the optimal h-point convex hull of n 2- or 3-dimensional points in O(nlgh)
* Chandy-Lamport Algorithm
* Chandy-Lamport Algorithm
* the '''Chang-Roberts Algorithm''' elects leaders for distributed systems.
* the '''Chang-Roberts Algorithm''' elects leaders for distributed systems.
* '''Chen's Algorithm''' is an exact quantum algorithm for testing 2-junta
* '''Chen's Algorithm''' is a single-writer, multiple-reader, wait-free lock using Compare-and-Swap
* the '''Chen-Teboulle Algorithm''' solves the proximal point algorithm efficiently for certain functions
* Cheney's Algorithm
* Cheney's Algorithm
* Chew's Second Algorithm
* Chew's Second Algorithm
Line 93: Line 99:
* Church-Rosser Theorem
* Church-Rosser Theorem
* Church-Turing Thesis
* Church-Turing Thesis
* the '''[https://clifford.at/cliffords-device.html Clifford Device]''' exploits <tt>if(0)</tt> to abstract block control via macros (note that e. g. [https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3355.htm N3355] calls this "Claire's Device" following a presumed transition, but Claire still seems to call it Clifford).
* Clos network
* Clos network
* Cobham Axioms
* Cobham Axioms
Line 121: Line 128:
* Delaunay's Triangulation
* Delaunay's Triangulation
* Dennard Scaling
* Dennard Scaling
* Deutsch gate
* Diffie-Hellman Key Exchange
* Diffie-Hellman Key Exchange
* Dijkstra's Algorithm
* Dijkstra's Algorithm
Line 132: Line 140:
* Earle latch
* Earle latch
* Earley Parser
* Earley Parser
* '''Edholm's law''' predicts doubling of bandwidth every 18 months across wireless, nomadic, and wired networks (and is getting some rather heavy lift from Moore's Law IMHO)
* '''Edmonds's matching algorithm''' constructs maximum matchings on graphs in O(|E||V|²)
* '''Edmonds's matching algorithm''' constructs maximum matchings on graphs in O(|E||V|²)
* Edmonds-Karp Algorithm
* Edmonds-Karp Algorithm
Line 138: Line 147:
* van Emde Boas trees
* van Emde Boas trees
* Sieve of Eratosthenes
* Sieve of Eratosthenes
* the '''Eytzinger layout''' stores binary trees in an array in a cache-friendly manner
* Euclid's Algorithm
* Euclid's Algorithm


Line 143: Line 153:
* '''Falk diagrams''' graph various performance counters against time (typically expressed in cycles)
* '''Falk diagrams''' graph various performance counters against time (typically expressed in cycles)
* Faugère F5 algorithm
* Faugère F5 algorithm
* '''Fenwick trees''' support efficient update of elements and calculate prefix sums in a table of numbers.
* '''Fenwick trees''' support efficient update of elements and calculate prefix sums in a table of numbers
* Fiat-Shamir Heuristic
* Fiat-Shamir Heuristic
* Fibonacci Heap
* Fibonacci Heap
Line 221: Line 231:
* Jensen's Device
* Jensen's Device
* Johnson's Algorithm
* Johnson's Algorithm
* the '''Jonker-Volgenant Algorithm''' improves '''Kuhn's Algorithm''' to solve the assignment problem in O(n³), Jonker-Volgenant 1987


* Kabsch Algorithm
* Kabsch Algorithm
* Kadane's Algorithm
* Kadane's Algorithm
* Kahan Summation Algorithm
* Kahan Summation Algorithm
* '''Kahn's Algorithm''' topologically sorts a graph in O(|V| + |E|), Kahn 1962
* Kannan's Theorem
* Kannan's Theorem
* '''Karatsuba's Algorithm''' multiplies two ''n''-digit numbers using ''n<sup>log<sub>2</sub>3</sup>'' single-digit mults
* '''Karatsuba's Algorithm''' multiplies two ''n''-digit numbers using ''n<sup>log<sub>2</sub>3</sup>'' single-digit mults
Line 253: Line 265:
* Kruskal's Algorithm
* Kruskal's Algorithm
* '''Kryder's Law''' asserted that areal density doubles every thirteen months (this has not been true for some time). Also known as the ''Kryder rate''.
* '''Kryder's Law''' asserted that areal density doubles every thirteen months (this has not been true for some time). Also known as the ''Kryder rate''.
* '''Kuhn's Algorithm''' (also known as '''Kuhn-Munkres''') solves the assignment problem in polynomial time, Kuhn 1955
* Kung-Leiserson systolic array
* Kung-Leiserson systolic array
* Kuroda Normal Form
* Kuroda Normal Form
Line 267: Line 280:
* Levenshtein automaton
* Levenshtein automaton
* Levenshtein distance
* Levenshtein distance
* '''Levialdi's transform''' progressively and deterministically degrades a bitmap
* Levin reduction
* Levin reduction
* Liang-Barsky algorithm
* Liang-Barsky algorithm
Line 283: Line 297:
* Mahaney's Theorem
* Mahaney's Theorem
* Manning algorithm
* Manning algorithm
* Margolus gate
* Marzullo algorithm
* Marzullo algorithm
* McFarling-style branch predictor
* McFarling-style branch predictor
Line 306: Line 321:
* Nevill-Manning algorithm
* Nevill-Manning algorithm
* Nick's Class
* Nick's Class
* '''Nielsen's law''' predicts slower growth for home bandwidth than computing power, suggesting that user experience will remain bandwidth-bound
* '''Nielsen's usability heuristics''' are ten (rather debatable) guidelines forming a usability heuristic for interface design
* Nisan's Generator
* Nisan's Generator


* '''Ousterhout's dichotomy/fallacy''' a taxonomy of ''systems'' vs ''scripting'' languages
* '''Ogden's lemma''' extends the pumping lemma to context-free languages
* '''Otsu's Method''' is used to perform automatic image thresholding
* '''Ousterhout's dichotomy/fallacy''' is a taxonomy of ''systems'' vs ''scripting'' languages
* Otway-Rees Protocol
* Otway-Rees Protocol


Line 339: Line 358:
* Rader-Brenner Algorithm
* Rader-Brenner Algorithm
* Radovic-Hagersten lock
* Radovic-Hagersten lock
* the '''Ramer-Douglas-Peucker algorithm''' decimates a series of line segments to a similar series of fewer line segments (1973)
* Raymond's Algorithm
* Raymond's Algorithm
* Reed-Muller code
* Reed-Muller code
Line 362: Line 382:
* Shamir's Secret Sharing Scheme
* Shamir's Secret Sharing Scheme
* Shamos-Hoey Algorithm
* Shamos-Hoey Algorithm
* '''Shar's Algortihm''' is a variation on the uniform binary search of Knuth.
* Shor's Algorithm
* Shor's Algorithm
* Sipser–Lautemann theorem
* Sipser–Lautemann theorem
Line 383: Line 404:
* Toda's theorem
* Toda's theorem
* Todd–Coxeter algorithm
* Todd–Coxeter algorithm
* the '''Toffoli gate''' aka CCNOT is a 3-to-3 universal reversible gate (all other reversible gates can be constructed from it). there is no smaller universal set of reversible gates (the only reversible gates in 1 or 2 inputs are identity, NOT, and CNOT).
* Tomasulo's Algorithm
* Tomasulo's Algorithm
* Tonelli-Shanks Algorithm
* Tonelli-Shanks Algorithm

Latest revision as of 18:28, 7 October 2024

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.

Explicitly not included in this list are: general logic (Peano and Presburger arithmetic, Herbrandization), 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), nor 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).

UPDATE the threshold for inclusion is now: De Morgan's Laws. If you're not at least as computer sciency as 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
  • the Adler-32 checksum trades reliability for speed relative to CRCs of the same length, and is included in Mark Adler's zlib
  • 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
  • Angluin's algorithm
  • Arikan's PAC Codes aka polarization-adjusted convolutional polar coding outperform CRC-aided and purely convolutional polar codes, approaching the theoretical channel capacity for short blocklengths.
  • 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
  • the Banerjee test can demonstrate the absence of control flow dependencies in certain types of loops
  • Barendregt convention
  • Barendregt-Geuvers-Klop Conjecture
  • Barnes-Hut simulation
  • the Barton-Nackman trick is an idiom in C++ effecting restricted template expansion
  • 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 algorithm is the theoretically best cache-replacement algorithm, one which discards information that will not be needed until the furthest time into the future (this is not usually knowable)
  • 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
  • the Bellman Equation specifies for a problem the necessary condition for optimality of dynamic programming
  • 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
  • the Boolean data type takes on values of true or false, as do variables in George Boole's algebra
  • Booth's Algorithm
  • Borůvka's Algorithm
  • Bowyer-Watson Algorithm
  • Boyer-Moore Algorithm
  • the Brassard-Høyer-Tapp algorithm solves the collision problem on a quantum computer in O(n) queries
  • Bremermann's Limit
  • Brent's Adder is logn + O(log1/2n) depth and O(nlg n) size
  • 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 Tp ≤ TN + (T1 - TN)/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
  • Catmull-Clark subdivision surfaces
  • Chaff Algorithm
  • Chaitin's algorithm
  • Chaitin's Constant
  • Chaitin-Briggs algorithm
  • Chaitin–Kolmogorov random numbers
  • Chakravala's Algorithm
  • Chan's Algorithm computes the optimal h-point convex hull of n 2- or 3-dimensional points in O(nlgh)
  • Chandy-Lamport Algorithm
  • the Chang-Roberts Algorithm elects leaders for distributed systems.
  • Chen's Algorithm is an exact quantum algorithm for testing 2-junta
  • Chen's Algorithm is a single-writer, multiple-reader, wait-free lock using Compare-and-Swap
  • the Chen-Teboulle Algorithm solves the proximal point algorithm efficiently for certain functions
  • 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 encoding
  • Church-Rosser Theorem
  • Church-Turing Thesis
  • the Clifford Device exploits if(0) to abstract block control via macros (note that e. g. N3355 calls this "Claire's Device" following a presumed transition, but Claire still seems to call it Clifford).
  • 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
  • Curry-Howard correspondence
  • 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
  • Deutsch gate
  • 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
  • Earle latch
  • Earley Parser
  • Edholm's law predicts doubling of bandwidth every 18 months across wireless, nomadic, and wired networks (and is getting some rather heavy lift from Moore's Law IMHO)
  • Edmonds's matching algorithm constructs maximum matchings on graphs in O(|E||V|²)
  • Edmonds-Karp Algorithm
  • ElGamal encryption
  • ElGamal signatures
  • van Emde Boas trees
  • Sieve of Eratosthenes
  • the Eytzinger layout stores binary trees in an array in a cache-friendly manner
  • 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
  • Falk diagrams graph various performance counters against time (typically expressed in cycles)
  • Faugère F5 algorithm
  • Fenwick trees support efficient update of elements and calculate prefix sums in a table of numbers
  • Fiat-Shamir Heuristic
  • Fibonacci Heap
  • Fisher-Yates shuffle
  • Flajolet-Martin algorithm
  • 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
  • The weighted Gomory-Hu Tree of an undirected graph with capacities G represents the minimum s-t cuts for all s-t pairs in G, and is computable via |V|-1 maximum flow problems.
  • 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
  • Hamiltonian path problem
  • 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
  • Hindley-Milner type system
  • Hirschberg's Algorithm
  • Hoare logic
  • Holevo's Theorem
  • Holland's schema theorem
  • Hong-Kung bound
  • Hopcroft-Karp Algorithm
  • Hopfield net
  • Horn clauses
  • Hough transform
  • Householder transformation
  • Huet's Zipper
  • Huffman coding
  • 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
  • the Jonker-Volgenant Algorithm improves Kuhn's Algorithm to solve the assignment problem in O(n³), Jonker-Volgenant 1987
  • Kabsch Algorithm
  • Kadane's Algorithm
  • Kahan Summation Algorithm
  • Kahn's Algorithm topologically sorts a graph in O(|V| + |E|), Kahn 1962
  • 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 is an improvement over Brent's Adder, linear (3n + 6*2m, m=ceil(lg n)) in size and logn + O(log1/2n) depth (m + 7(2m)1/2+16, m = ceil(lg n)).
  • Kruskal's Algorithm
  • Kryder's Law asserted that areal density doubles every thirteen months (this has not been true for some time). Also known as the Kryder rate.
  • Kuhn's Algorithm (also known as Kuhn-Munkres) solves the assignment problem in polynomial time, Kuhn 1955
  • Kung-Leiserson systolic array
  • Kuroda Normal Form
  • Ladner's Theorem
  • Lamport's Bakery Algorithm
  • Lamport's Logical Clock
  • Lamport's Hash
  • Lamport timestamps
  • Lee-Seung algorithm
  • Lehmer random number generator
  • Lehmer's GCD Algorithm
  • Lempel-Ziv-Welch compression
  • Levenshtein automaton
  • Levenshtein distance
  • Levialdi's transform progressively and deterministically degrades a bitmap
  • Levin reduction
  • Liang-Barsky algorithm
  • Lin-Kernighan Heuristic
  • Linde-Buzo-Gray algorithm
  • Ling adders
  • Liskov's Substitution Principle
  • Lloyd's algorithm
  • Loop subdivision surfaces
  • 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
  • Margolus gate
  • 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
  • von Neumann architecture aka stored-program architecture keeps instructions in the same memory as data (as opposed to Harvard architecture, which keeps the two distinct). Popularized by von Neumann, but largely based on Eckert and Mauchly's work on the ENIAC.
  • Nevill-Manning algorithm
  • Nick's Class
  • Nielsen's law predicts slower growth for home bandwidth than computing power, suggesting that user experience will remain bandwidth-bound
  • Nielsen's usability heuristics are ten (rather debatable) guidelines forming a usability heuristic for interface design
  • Nisan's Generator
  • Ogden's lemma extends the pumping lemma to context-free languages
  • Otsu's Method is used to perform automatic image thresholding
  • Ousterhout's dichotomy/fallacy is 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
  • PageRank Algorithm
  • Peterson's Algorithm
  • Petri nets
  • 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
  • the Ramer-Douglas-Peucker algorithm decimates a series of line segments to a similar series of fewer line segments (1973)
  • Raymond's Algorithm
  • Reed-Muller code
  • Reed-Solomon correction code
  • Reingold's logspace Algorithm
  • 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
  • Shar's Algortihm is a variation on the uniform binary search of Knuth.
  • Shor's Algorithm
  • Sipser–Lautemann theorem
  • Smith's Algorithm hashes the program counter to n bimodal (saturating) k-bit counters for dynamic branch prediction (1981)
  • Smith-Waterman algorithm
  • Solomonoff-Levin distribution
  • Steensgaard's Algorithm
  • Stehlé-Zimmermann algorithm
  • Steiner tree problems are a class of combinatorial optimization problems involving determining the optimal interconnect of a graph under some objective function.
  • 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
  • The nondeterministic Tarski–Kuratowski algorithm produces an upper bound for the complexity of a given formula in the arithmetical hierarchy and analytical hierarchy.
  • Thompson Automata
  • Timsort
  • Toda's theorem
  • Todd–Coxeter algorithm
  • the Toffoli gate aka CCNOT is a 3-to-3 universal reversible gate (all other reversible gates can be constructed from it). there is no smaller universal set of reversible gates (the only reversible gates in 1 or 2 inputs are identity, NOT, and CNOT).
  • Tomasulo's Algorithm
  • Tonelli-Shanks Algorithm
  • The Toom-Cook Algorithm multiplies two n-digit numbers using nlog(5)/log(3) single-digit mults
  • Tupper's self-referential formula
  • Turing Degree
  • Turing Machines
  • the Turing Test, originally the "imitation game", was proposed by Turing as a means of evaluating conversational artificial intelligence via questions-and-answers on a text channel.
  • Ukkonen's Algorithm
  • Valiant-Vazirani Theorem
  • Van Jacobson Channels
  • Van Wijngaarden Grammars
  • Verhoeff Algorithm
  • Viola-Jones face detection
  • Viterbi algorithm
  • Volder's algorithm
  • Wagner-Fischer Algorithm
  • Wallace Multiplier
  • Wallace tree
  • Warnsdorff's Algorithm
  • Welford's Algorithm is a stable online algorithm for computing mean and estimated variance
  • 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