# Difference between revisions of "Computer science eponyms"

(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...") |
|||

(41 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! | 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, | 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 | ||

Line 23: | Line 25: | ||

* 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 | |||

* Bell-La Padula model | * Bell-La Padula model | ||

* Bellman-Ford Algorithm | * Bellman-Ford Algorithm | ||

Line 73: | Line 76: | ||

* 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 88: | ||

* 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 | * Cook-Levin Theorem | ||

Line 91: | Line 97: | ||

* 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 113: | ||

* 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 120: | ||

* 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 138: | ||

* Fredkin gate | * Fredkin gate | ||

* Friedberg-Muchnik Theorem | * Friedberg-Muchnik Theorem | ||

* Fürer's algorithm | * '''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 157: | Line 166: | ||

* 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 201: | ||

* 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 207: | Line 220: | ||

* Koenig Lookup | * Koenig Lookup | ||

* Kohonen Algorithm | * Kohonen Algorithm | ||

* Kohonen network | |||

* Kolmogorov complexity | * Kolmogorov complexity | ||

* Koomey's Law | * Koomey's Law | ||

Line 212: | Line 226: | ||

* 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 247: | ||

* 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 261: | ||

* 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 279: | ||

* 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 274: | Line 294: | ||

* 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 301: | ||

* 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 291: | Line 313: | ||

* 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 337: | ||

* 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 348: | ||

* 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 360: | ||

* Viola-Jones face detection | * Viola-Jones face detection | ||

* Volder's algorithm | * Volder's algorithm | ||

* | * von Neumann architecture | ||

* Wagner-Fischer Algorithm | * Wagner-Fischer Algorithm | ||

Line 339: | Line 366: | ||

* 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 |

## Latest revision as of 22:32, 2 January 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*Ω(N*algorithms on^{2})*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

- 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- 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
- Brent's Theorem
- 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
- Chang-Roberts Algorithm
- 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
- Cook-Levin Theorem
- Cooley-Tukey Algorithm
- Coppersmith-Winograd Algorithm
- 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
**Fürer's algorithm**multiplies two*n*-digit numbers in*O(nlgn*2*^{O(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
- Graham Scan
- 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*n*single-digit mults^{log23}- 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
- 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
- Popek-Goldberg virtualization requirements
- Post's correspondence problem
- 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-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*n*single-digit mults^{log(5)/log(3)} - 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

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