Algorithms and Data Structures - Links to Implementations [NIST]

Source: http://www.nist.gov/dads/termsImpl.html

Other great source of implementations:

Stony Brook Algorithm Repository (organized by area and reviewed for quality)

Guide to Available Mathematical Software or GAMS (source of implementations of mathematical functions)

---

• Ackermann’s function: History of the function and (Modula-2) code. (Lisp). (Pascal). (Miranda).
• adaptive Huffman coding: (C)
• Aho-Corasick: Bruce Watson’s SPARE Parts, a string pattern recognition toolkit (C++).
• Alpha Skip Search algorithm: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• American flag sort: It is program C (C) in the paper.
• Apostolico-Crochemore: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• Apostolico-Giancarlo algorithm: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• arithmetic coding: Jürgen Abel’s excellent Range and Arithmetic Coding resources (C, Java, C++), with links to papers, people, and implementations. Theory development and implementation (C). An explanation and implementation (C): a PDF document of section 20.5 of Numerical Recipes in C.
• array: (C). Bro. David Carlson’s search, access, complexity, etc. tutorial and code (C++). Read and write different arrays (Fortran, C++).
• AVL tree: Ben Pfaff’s explanations and code (C). Kaz Kylheku’s Austin (C) implementing sorted list, binary search tree, AVL, red-black and splay trees and conversions from any of these to any other. Maksim Goleta’s Collections (C#) implementing singly- and doubly-linked lists, binary search trees, and AVL trees. Bro. David Carlson’s tutorial and code (C++). Richard McGraw’s Navl-latest.tar.bz2 (C#). Worst-case behavior of traversal, annotated for real time (WOOP/ADA). Herbert Glarner’s implementation in (Linoleum).
• balanced binary tree: red-black tree analysis, explanation, examples, and code (C). Ben Pfaff’s AVL tree explanation (C).
• balanced merge sort: (C) using an auxiliary function to select next file (C).
• BB(α) tree: Worst-case behavior of traversal, annotated for real time (WOOP/ADA), including bibliography. insert (C and Pascal) and delete (C and Pascal) that use check root (C and Pascal) (or this one or this one?), left rotation (C and Pascal), and right rotation (C and Pascal).
• Bellman-Ford algorithm: The entry in Wikipedia (C, Assembly, and pseudocode) has a proof, too.
• Benford’s law: An implementation (Java) due to Sedgewick and Wayne (search for Benford’s law).
• bidirectional bubble sort: demonstration and source code (Java); animation and code, see cocktail sort (Java).
• binary heap: delete (C) and insert (C and Pascal) both of which use the auxiliary function siftup (C and Pascal), explanation, examples, and code (C). (Fortran)
• binary insertion sort: (C)
• binary priority queue: Gonnet and Baeza-Yates insert (C and Pascal) and delete (C and Pascal)
• binary search: Mukundan’s animation (Java). search (C) where indexes are 0 to n, inclusive. That is, n is the highest index of the 0-based array, and possible key indexes, k, are low < k <= high in the loop. (Scheme), Worst-case behavior annotated for real time (WOOP/ADA), including bibliography.
• binary search tree: Ben Pfaff’s insert, delete, search, copy, etc. (literate C); Kaz Kylheku’s Austin (C) implementing sorted list, binary search tree, AVL, red-black and splay trees and conversions from any of these to any other. Maksim Goleta’s Collections (C#) implementing singly- and doubly-linked lists, binary search trees, and AVL trees. insert (C), insert (C), search (C), and insert, search, delete, and various traversals (Modula-2) (use must be acknowledged).
• binary tree: examples, analysis, and code (C). Bro. David Carlson’s tutorial and code (C++). Worst-case behavior of traversal, annotated for real time (WOOP/ADA).
• bin packing problem: (Icon).
• bitonic sort: explanation, analysis, bibliography, etc. (Java). reference source code (C). Section from 1994 User Manual for Portable Parallel C++ (pC++).
• Bloom filter: Arash Partow’s implementations (C++, Object Pascal) (go to Download, at the bottom).
• Boyer-Moore: Christian Charras’ and Thierry Lecroq’s Boyer-Moore algorithm (C). (C) which uses Boyer-Moore preprocessing (C)
• Boyer-Moore-Horspool: Christian Charras’ and Thierry Lecroq’s Horspool algorithm (C). Gonnet and Baeza-Yates’ (C) or (Pascal)
• bozo sort: demonstration and source code (Java).
• B⁺-tree: Search the web for bplus to find implementations. More targeted searches are bplustree, “b plus tree”, or search the comp.sources groups for bplus.
• branch and bound: Arnold Neumaier’s page of branch and bound implementations (C, C++, Matlab, Fortran, executables, etc.).
• Bresenham’s algorithm: The original IBM 1401 implementation (Autocoder) from 1962.
• brick sort: Sedgewick’s Analysis of Shellsort and Related Algorithms (C)
• brute force string search: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C), (C and Pascal)
• brute force string search with mismatches: Gonnet and Baeza-Yates’ (C and Pascal)
• B-tree: tutorial of how B-trees work and code (Perl), Bro. David Carlson’s tutorial and code (C++). data structure definition (C and Pascal), insert (C and Pascal) using auxiliary functions (C and Pascal), search (C and Pascal), (Pick Basic?).
• bubble sort: demonstration and source code (Java) - but code might not render properly; (Rexx).
• bucket sort: analysis, explanation, and code (C), and (C).
• Burrows-Wheeler transform: Mark Nelson’s great Data Compression with the Burrows-Wheeler Transform (C++) explains the algorithm. Dr. Dobb’s Journal, September, 1996.
• calendar queue: In a simulation tool package (C)
• chaining: (C)
• Chinese postman problem: (C++, Mathematica and Fortran)
• clique problem: (Fortran, C, and Mathematica)
• coalesced chaining: Wikipedia article (C) (starts at the beginning of the array for empty places). insert (C) (starts at the end of the array for empty places), search (C).
• Colussi: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• combination: The Combinatorial Object Server’s information on Combinations (Pascal and C); Michael Gilleland’s CombinationGenerator class (Java).
• comb sort: (Java).
• connected components: (C++, C, Pascal, Mathematica, and Fortran)
• CORDIC: Wikipedia entry (C, MATLAB). introduction and code (C). Ken Turkowski’s Introduction to the CORDIC Technique (C).
• counting sort: Marion McCoskey’s Single Buffered Count Sort (C++). Bruno R. Preiss’ sort integers 0 to m-1 (C).
• cube root: GAMS Class C2 has many implementations of powers, roots, and reciprocals (C and Fortran).
• cutting stock problem: linear and nonlinear programming and algebra packages (C and Fortran)
• cycle: graph cycle detector (C)
• deterministic finite automata string search: description and animation (C), (C) which uses a finite automaton structure (C) and builds a recognizer (C)
• dictionary: (C++, Pascal, and Fortran). Kaz Kylheku’s Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list. Herbert Glarner’s Patricia tree (Linoleum) implementation.
• Dijkstra’s algorithm: An analysis with code (C)
• dining philosophers: code Shared Memory and Semaphores (C and C++), One example (Siefast) for the Siefast simulator.
• direct chaining: insert (C), search (C). Duane A. Bailey’s ChainedHashtable class documentation in the structure package (Java) from Java Structures: Data Structures in Java, for the Principled Programmer.
• discrete interval encoding tree: insert, delete, and member (ML), insert, delete, and member (Haskell)
• divide and conquer: how many odd numbers in an array? (C)
• double hashing: insert (C and Pascal), search (C and Pascal)
• double metaphone: Many metaphone and double metaphone (Basic, C, Perl, and C++) implementations. Apache codec implementations of soundex, Metaphone, and Double Metaphone (Java). applet for name lookup (Java). (SAS) zip archive.
• doubly linked list: Kaz Kylheku’s Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list. Maksim Goleta’s Collections (C#) implementing singly- and doubly-linked lists, binary search trees, and AVL trees.
• dynamic hashing: Charles B. Falconer’s hashlib (C) including several example applications. Kaz Kylheku’s Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list.
• dynamic programming: Mark Nelson’s tutorial to using C++ Hash Table Memoization: [for] Simplifying Dynamic Programming (C++). Oleg Kiselyov’s program to optimally lay out a page (C++) using dynamic programming.
• edge coloring: (C++, Mathematica, and C)
• edge connectivity: (Mathematica, C, and Pascal)
• enfilade: Green (C). Gold (Smalltalk).
• Euclidean Steiner tree: GeoSteiner (C) - software for computing steiner trees.
• Euclid’s algorithm: Worst-case behavior annotated for real time (WOOP/ADA), (Scheme).
• Euler cycle: (Mathematica and Fortran)
• extendible hashing: A description including a hash function (COBOL).
• external quicksort: (C)
• factorial: Peter Luschny’s fast factorial algorithms (Java and C#) including benchmarks and advice. Calum Grant’s prime sieve fast factorial (C++). (Scheme).
• fast fourier transform: Worst-case behavior annotated for real time (WOOP/ADA).
• feedback edge set: (C)
• feedback vertex set: (C)
• Fibonaccian search: Manolis Lourakis’ fibsrch (C). Worst-case behavior annotated for real time (WOOP/ADA), including bibliography. (Interpolation and secant search “guess more precisely where the key being sought falls”.)
• Fibonacci heap: John Boyer’s code for ExtractMin and DecreaseKey (C++) and fibheap.h, the include file it needs.
• Fibonacci number: Worst-case behavior to generate nth number, annotated for real time (WOOP/ADA), (Scheme).
• Find: analysis and comparison (Rexx)
• finite state machine: Jan Daciuk’s Finite state utilities (C++) including many links to other code, papers, etc. Finite State Automata Utilities (Prolog), which generate C code, minimize, visualize, etc. Page has binaries, too. For regular expressions generate NFSM, make deterministic, and optimize (Haskell). Oleg Kiselyov’s program to minimize a finite state machine (Prolog).
• finite state machine minimization: (C++ and Pascal)
• Fisher-Yates shuffle: Ben Pfaff’s answer to how can I shuffle the contents of an array? (C). An implementation (Java) due to Sedgewick and Wayne, including an explanation of unfair shuffle algorithms (search for Shuffling).
• Galil-Giancarlo: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• Galil-Seiferas: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• gnome sort: (C)
• graph: GraphEd — Graph Editor and Layout Program (C), graph manipulation (C++, C, Mathematica, and Pascal), JGraphT (Java) build, traverse, and display directed and undirected graphs, GEF - Graph Editing Framework (Java) a library to edit and display graphs. Graph generating (C, Mathematica, Pascal, C++, and Fortran), GTL - the Graph Template Library (C), BGL - the Boost Graph Library (C++) JUNG (Java), the Java Universal Network/Graph framework. JDSL (Java), the Data Structures Library in Java.
• graph drawing: draw a graph nicely (C and Mathematica), draw a graph in the plane such that no edges cross (C, C++, and Mathematica), GraphEd: Graph Editor and Layout Program (C). Graphviz: Graph Visualization Software (C), consisting of many graph drawing programs, viewers (C, Java, and TCL/TK), etc.
• graph isomorphism: (C and Mathematica)
• graph partition: (C++) explanation of problem with links to implementations. METIS is a set of programs for partitioning graphs, etc.
• Gray code: binary-to-Gray and Gray-to-binary conversion (C) with history, references, and application to genetic algorithms. Convert between binary and Gray (C): a PDF document of section 20.2 of Numerical Recipes in C. binary-to-Gray, code generation, and plotting (Maple) with applications and references.
• greatest common divisor: (Scheme)
• Grover’s algorithm: Grover’s article in Dr. Dobb’s Journal, April 2001 (C-like).
• Hamiltonian cycle: (Fortran, C, Mathematica, and C++)
• hash function: See the implementations at minimal perfect hashing (C++ and C) and Pearson’s hash (C). Bob Jenkins’ fast, parameterizable, broadly applicable hash function (C) including code for and evaluations of many other hash functions. A review and comparison of many integer hash functions (C). Austin Appleby’s fast MurmurHash (C), including avalanche diagrams for Hsieh SuperFastHash, Jenkin’s lookup3, Murmur, Bernstein, FNV, and modified FNV. Overview of different kinds of hash functions. Bret Mulvey’s great tutorial on good hash functions, including analysis of and code for FNV, Jenkin’s hashes, SHA-1, and other hash and evaluation functions (C#). Herbert Glarner’s HSH 11/13 algorithm (Linoleum), including very thorough justification. Fowler/Noll/Vo or FNV hash function (C). Arash Partow’s implementations of various General Hash Functions (C, C++, Pascal, Object Pascal, Java, Ruby, Python) and Bloom filter for strings. Hash functions for strings (C) and (C and Perl). Kazlib (C).
• hash table: direct chaining: (C). Bro. David Carlson’s tutorial and code (C++). linear probing hashing: insert (C), look up (C), Kazlib (C), direct chaining: explanations, diagrams, and code (Visual Basic). Mark Nelson’s tutorial to using C++ Hash Table Memoization: [for] Simplifying Dynamic Programming (C++). Explanation and sample problems for hashing (C) (some pages require free registration).
• heap: Bro. David Carlson’s heaps and heapsort tutorial and code (C++).
• heapsort: Lang’s definitions, explanations, diagrams, Java applet, and pseudo-code (C), (Java), (Java). Bro. David Carlson’s heaps and heapsort tutorial and code (C++). Worst-case behavior annotated for real time (WOOP/ADA), including bibliography, (Rexx).
• histogram sort: (C and Pascal).
• Huffman coding: build tree in array (C) — also computes entropy and efficiency. An explanation and implementation (C): a PDF document of section 20.4 of Numerical Recipes in C.
• independent set: (Fortran and C)
• insertion sort: (Java). An implementation (Java) due to Sedgewick and Wayne (search for Insertion sort). Other implementations may be available through the Stony Brook Algorithm Repository, Sorting; (Scheme); (Fortran).
• internal sort: (Fortran)
• interpolation search: (Java). C-like pseudo-code. annotated for real time (WOOP/ADA), including bibliography. (Pascal)
• interpolation-sequential search: (Pascal) or (Pascal)
• isomorphic: (C and Mathematica)
• Jaro-Winkler: Cohen, Ravikumar, and Fienberg have an implementation in their SecondString (Java) package.
• Johnson-Trotter: Information on Permutations (Pascal and C), look for Transposition Order.
• JSort: Demonstration and source code (Java).
• Karmarkar’s algorithm: Article with details of implementation and comparisons (Algol-like pseudo-code)
• Karnaugh map: (Java)
• Karp-Rabin: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C), description and animation (C), (C and Pascal).
• k-ary Huffman coding: animation which counts characters, finds the code, encodes, and decodes (Java),
• k-d tree: C, Pascal, or FORTRAN, insert (C), range search (C), and search (C). (C, Pascal, and Fortran)
• KmpSkip Search: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• knapsack problem: (Fortran and Pascal). GAMS Class G2c3 (Fortran).
• knight’s tour: Oleg Kiselyov’s derivation (Prolog)
• Knuth-Morris-Pratt algorithm: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C). Unix strstr implemented with KMP (C). (C and Pascal) which uses Boyer-Moore preprocessing (C)
• Kruskal’s algorithm: analysis and code (C), (pseudocode)
• k-way merge: Jordan Zimmerman’s k-way merge (Java).
• leftist tree: merge and delete (C and Pascal) which use distance (C and Pascal), insert (C and Pascal)
• left rotation: (Pascal), (C). A great series of animations explaining rotations with code (Java).
• Lempel-Ziv-Welch: Mark Nelson’s article with an explanation (C)
• Levenshtein distance: Levenshtein distance (Java, C++, Visual Basic), includes a great explanation and links to code in Perl, C, JavaScript, Python, and many more languages. Many implementations (Ada, C++, Lisp, Io, Java, OCaml, Octave, PHP, Python, Ruby, Visual Basic).
• linear probing: insert (C), search (C).
• linear probing sort: (C and Pascal).
• linear search: (C)
• linked list: explanations, examples, iterators, sorting lists, etc. (C++), Kazlib (C). Bro. David Carlson’s tutorial and code (C++). (C++)
• longest common subsequence: (C and Mathematica)
• longest common substring: (C and Mathematica)
• lower triangular matrix: (Fortran)
• matching: (Fortran, C, C++, and Pascal)
• matrix: (Fortran), (C++)
• Maximal Shift: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• maximum-flow problem: Problem explanation and development of Ford-Fulkerson (pseudocode); including solving related problems, like multi-source, vertex capacity, bipartite matching, etc. description and links to implementations (C, Fortran, C++, Pascal, and Mathematica).
• median: select kth element (Pascal and C++)
• memoization: Mark Nelson’s tutorial to using C++ Hash Table Memoization: [for] Simplifying Dynamic Programming (C++).
• merge: (Scheme)
• merge sort: (C) that needs list merge (C) or array merge (C), (Pascal) that needs list merge (Pascal) or array merge (Pascal); (Java); Demo and code of in-place and double merge sort (Java); Worst-case behavior annotated for real time (WOOP/ADA), including bibliography. John David Stone’s (Scheme). Siegfried Sielaff’s description and code of an in-place, stable variant he calls Swap Sort (C) (click the British flag for an English translation). Other implementations may be available through the Stony Brook Algorithm Repository, Sorting.
• metaphone: Many metaphone and double metaphone (Basic, C, Perl, and C++) implementations. applet for name lookup (Java), Apache codec implementations of soundex, Metaphone, and Double Metaphone (Java).
• minimal perfect hashing: Description and code for minimal perfect hashing (C), mph: minimal perfect hash function generator (C). gperf: a near-minimal perfect hashing (C++), click on GNU mirror, click on a nearby server, then gperf.
• minimum spanning tree: (C++, Pascal, Fortran, C, and Mathematica). CALGO Algorithm 613 (Fortran).
• model checking: Model checkers: Spin and SMV.
• MODIFIND: analysis and comparison (Rexx)
• Morris-Pratt algorithm: Christian Charras’ and Thierry Lecroq’s explanation, visualization, references, and implementation (C).
• multikey Quicksort: Fast Algorithms paper, demos, and code (C)
• Munkres’ assignment algorithm: Example of step-wise coding of the algorithm (Pascal) from a description.
• nearest neighbor: (C, C++, and Pascal)
• nondeterministic Turing machine: Alex Vinokur’s Turing machine simulator (C++).
• Not So Naive: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• NP-complete: Stas Busygin’s home page with QUALEX and SAT01 (C++).
• NYSIIS: (JavaScript) (in page source). (SPL). (Rexx) (reportedly buggy).
• optimal mismatch: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• optimization problem: linear and nonlinear programming and algebra packages (C and Fortran) from the Optimization Technology Center.
• ordered linked list: insert (C)
• oscillating merge sort: (Pascal)
• pagoda: delete (C and Pascal), insert (C and Pascal), and merge (C and Pascal)
• pairing heap: Darius Bacon’s functional implementation (Scheme).
• partition: generating partitions (Fortran, Mathematica, Pascal, and C), (Scheme)
• Patricia tree: Net-Patricia (Perl and C) is a C implementation with a Perl API. C prototyping tools, cprops (C), is a threaded implementation (find trie.c). py-radix (Python). insert (C), search (C). Herbert Glarner’s implementation in (Linoleum).
• Pearson’s hash: (C)
• perfect hashing: See the implementations at minimal perfect hashing (C++, C), insert (C), search (C).
• perfect shuffle: Discussion and explanation of what makes a shuffle perfect and two implementations (Haskell).
• permutation: The (Combinatorial) Object Server’s information on Permutations (Pascal and C); Michael Gilleland’s PermutationGenerator class (Java); (Pascal, Fortran, Mathematica, and C); (Fortran). Perfect shuffle (Haskell).
• planar graph: draw a planar graph such that no edges cross (C, C++, and Mathematica)
• polyphase merge sort: (C) (Error: variable some is not initialized nor reset) using an auxiliary function to select next file (C)
• Post machine: Alex Vinokur’s Post machine simulator (C++).
• preorder traversal: Mukundan’s animation (Java).
• Prim-Jarnik algorithm: explanation and implementation (pseudocode and Java bytecode)
• priority queue: Links to implementations, dozens of papers, introductory material, etc..
• pseudo-random number generator: (C++, C, and Fortran). Herbert Glarner’s Mersenne Twister MT 19937 (Linoleum). GAMS (C). Using C libraries to get random numbers in a certain range (C) is C FAQ question 13.16.
• P-tree: Implementations of P-tree (1) insert (C and Pascal), delete max (C and Pascal), and head (C and Pascal)
• qm sort: demonstration and source code (Java).
• q sort: demonstration and source code (Java).
• quadratic probing: insert (C and Pascal)
• quadtree: insert (C), search (C).
• quad trie: insert (C), search (C)
• queue: (Java). Maksim Goleta’s Collections (C#) implementing singly- and doubly-linked lists, binary search trees, and AVL trees. Bro. David Carlson’s tutorial and code (C++) using linked list. Darius Bacon’s functional implementation (Scheme).
• quick search: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• quicksort: Robert Sedgewick’s talk showing that with Bentley-McIlroy 3-way partitioning Quicksort Is Optimal (C) (pdf format) for random files possibly with duplicate keys; includes discussion and proof. Wikipedia entry with extended discussion and alternatives (C, Python, Haskell, pseudocode). Demos and code for enhanced, fast, quicksort, and quicksort with bubble sort (Java). (Java). (Scheme). In-line compare (Rexx), compare function (Rexx).
• radix sort: Explanation and code (Pascal). (C and Pascal). analysis, explanation, and code (C). tutorial with examples and code (C++).
• Raita: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• randomized binary search tree: Oleg Kiselyov’s (Scheme)
• rapid sort: Patrick Eberhart’s description and illustration (Visual Basic and C++).
• rebalance: (Pascal)
• rectangular matrix: (Fortran)
• rectilinear Steiner tree: GeoSteiner (C) - software for computing steiner trees.
• red-black tree: analysis, explanation, examples, and code (C). Ben Pfaff’s libavl (C) including pointers to other implementations. Kaz Kylheku’s Kazlib (C) implementing dictionary, dynamic hash table, red-black tree, and doubly linked list; Austin (C) implementing sorted list, binary search tree, AVL, red-black and splay trees and conversions from any of these to any other. Glenn Scheper’s RBSL (C) which sorts text lines using a red-black tree.
• repeated squaring: (C)
• Reverse Colussi: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• Reverse Factor: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• right rotation: (C and Pascal). A great series of animations explaining rotations with code (Java).
• right-threaded tree: Ben Pfaff’s explanations and code (C)
• R^*-tree: In Marios Hadjieleftheriou’s Spatial Index Library (C++)
• R-tree: (Java).
• select and partition: analysis and comparison (Rexx), (Scheme)
• selection sort: animation and code (Java); Thomas Baudel’s links to animation (Java); (Scheme); questions and example (C).
• select mode: (Pascal)
• separate chaining: insert (C), search (C).
• set: (C++ and Pascal). Darius Bacon’s functional implementation (Scheme).
• set cover: (Pascal)
• set packing: (Pascal)
• Shell sort: shell sort (Java). Sedgewick’s Analysis of Shellsort and Related Algorithms (C); Worst-case behavior annotated for real time (WOOP/ADA), including bibliography; demonstration and source code (Java); (Scheme), (Fortran), (Forth), strings (Basic), initial increment is about 1/9n and decreases by thirds (Rexx); increments are 1/2ⁿ of number of elements (Rexx); increments are multiples of 3 (Rexx).
• Shift-Or: explanation and code (C)
• shortest common superstring: (C)
• shortest path: (C, C++, Pascal, Fortran, and Mathematica)
• sieve of Eratosthenes: various implementations (C, Perl, and Java), Luschny’s (Java 5) implementation.
• Simon’s algorithm: In Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms preprocessing phase (C)
• single-destination shortest-path problem: See implementations at graph.
• single-source shortest-path problem: See implementations at graph.
• skip list: Julienne Walker’s tutorial (C). Click “Libraries”, then “Classic Skip List” for the zip’d code. Code (C) at ePaperPress.
• skip search: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• Smith algorithm: visualization and code (C)
• Smith-Waterman algorithm: Ahmed Moustafa’s implementation in JAligner (Java).
• smoothsort: Smoothsort, an alternative for sorting in situ typescript (guarded command language)
• sort: Specific implementations can be found under the specific sort routines or at (Pascal, C++, Fortran, and Mathematica).
• sorted array: Insert (C).
• sorted list: insertion (C) into an ordered linked list.
• soundex: (C). Apache codec implementations of soundex, Metaphone, and Double Metaphone (Java). (Visual Basic). (Rexx). (Cobol).
• sparse matrix: Input/output for sparse matrices stored in Harwell-Boeing Format (C)
• splay tree: Kaz Kylheku’s Austin (C) implementing sorted list, binary search tree, AVL, red-black and splay trees and conversions from any of these to any other. Danny Sleator’s (Java and C).
• square root: GAMS Class C2 has many implementations of powers, roots, and reciprocals (C and Fortran). Many variations (C and Assembler) for caching, pipelined processing, etc.
• stack: Maksim Goleta’s Collections (C#) implementing singly- and doubly-linked lists, binary search trees, and AVL trees. Bro. David Carlson’s tutorial and code (C++). (Scheme)
• star encoding: Mark Nelson’s 2002 Star-Encoding (C++), includes a similar algorithm that assigns shorter codes to more frequent words.
• Steiner tree: (C and Pascal), GeoSteiner (C) - software for computing steiner trees.
• stooge sort: demonstration and source code (Java).
• string matching: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C), (C++ and Pascal), Strmat (C) - a collection of string matching and pattern discovery programs, (Fortran), (Fortran).
• string matching on ordered alphabets: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• string matching with errors: See implementations at string matching. (C and Pascal)
• strongly connected component: (C++, C, Pascal, Mathematica, and Fortran)
• strongly connected graph: (C++, C, Pascal, Mathematica, and Fortran)
• subset: The Combinatorial Object Server’s information on subsets (Pascal and C); generating subsets (Fortran, Mathematica, and Pascal)
• suffix tree: Strmat - a variety of string matching and pattern discovery algorithms (C). Christian Kreibich’s libstree (C) including depth- and breadth-first traversal, string update, and examples like LCS. Mark Nelson’s great Fast String Searching With Suffix Trees (C++) explains Ukkonen’s linear-time algorithm. Dr. Dobb’s Journal, August, 1996. (C++ and Pascal).
• temporal logic: The SMV model checker.
• ternary search tree: papers, demos, and code (C), (C). Richard McGraw’s explanation, example, and links to other implementations (C++, Java) and his implementations called ctst-dist-0.30.tar.* (C). Ternary Search Tree Dictionary in (C#): Faster String Dictionary! by Jonathan de Halleux.
• threaded tree: Ben Pfaff’s explanations and code (C)
• top-down radix sort: (C and Pascal)
• topological sort: Eric Lippert’s narrative example and solution (JScript). (C++, Mathematica, C, and Pascal)
• tournament: Forbes D. Lewis’ essay on Order Statistics and Tournaments (C).
• towers of Hanoi: (JavaScript) Mukundan’s animation (Java).
• transitive closure: on a graph (C++ and Mathematica)
• transitive reduction: on a graph (C++ and Mathematica)
• transpose sequential search: (C)
• traveling salesman: Links to software as well as papers, preprints, reports, etc., on-line on this and related problems, (C, Fortran, Pascal, Mathematica, and C++). Approximate solver (Java).
• treap: Oleg Kiselyov’s (Scheme)
• treesort (1): (C)
• trie: insert (C) and search (C), Darius Bacon’s functional implementation (Scheme)
• Turbo-BM: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• Turbo Reverse Factor: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• Turing machine: Alex Vinokur’s Turing machine simulator (C++).
• Two Way algorithm: Christian Charras’ and Thierry Lecroq’s Exact String Matching Algorithms (C)
• union of automata: (C)
• upper triangular matrix: (Fortran)
• vertex coloring: (Fortran, C, Pascal, C++, and Mathematica)
• vertex connectivity: (Mathematica, C, and Pascal)
• vertex cover: (C, Fortran, and Mathematica)
• Vitter’s algorithm: Algorithm 673 in plain text (Pascal).
• Zeller’s congruence: Dr J R Stockton’s Zeller’s congruence, for day-of-week (Pascal, JavaScript). Includes tests and code for Easter, Zeller’s original papers (in German and English translations), etc. The following are only correct for Gregorian dates. Comp.lang.c FAQ question 17.28 (C). Mike Keith’s short day of the week expression for Gregorian dates (C). (Stockton’s page gives later, shorter versions of Keith’s expression.)
• Zhu-Takaoka: explanation, animation, and example (C)