Algorithms and Data Structures Glossary
(Starting with "S")

By www.nist.gov,
Gaithersburg, Maryland, U.S.A.

paul . black [at] nist . gov
http://www.nist.gov/dads

Become a member of TranslationDirectory.com at just $12 per month (paid per year)

Advertisements:

Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously

S

saguaro stack: see cactus stack

SAM: see spatial access method

saturated edge

SBB tree

scan

scapegoat tree

scatter storage: see hash table

Schorr-Waite graph marking algorithm

search

search tree

search tree property

secant search

secondary clustering

segment

Select

select and partition

selection problem: see select k^th element

selection sort

select k^th element

select mode

self-loop

self-organizing heuristic

self-organizing list

self-organizing sequential search: see transpose sequential search

semidefinite programming

separate chaining

separation theorem

sequential search: see linear search

set

set cover

set packing

shadow heap

shadow merge

shadow merge insert

shaker sort: see bidirectional bubble sort

Shannon-Fano coding

shared memory

Shell sort

Shift-Or

Shor's algorithm

shortcutting: see pointer jumping

shortest common supersequence

shortest common superstring

shortest path

shortest spanning tree: see minimum spanning tree

shuffle: see permutation

shuffle sort

sibling

sieve of Eratosthenes

sift up

signature

Simon's algorithm

simple merge

simple path

simple uniform hashing

simplex

simulated annealing

simulation theorem

single-destination shortest-path problem

single-pair shortest-path problem: see shortest path

single program multiple data

single-source shortest-path problem

singly linked list: see linked list

singularity analysis

sink

sinking sort: see bubble sort

skd-tree

skew symmetry

skip list

skip search

slope selection

Smith algorithm

Smith-Waterman algorithm

smoothsort

solvable

sort

sorted array

sorted list

sort in place: see in-place sort

soundex

source

space-constructible function

space ordering method

spanning tree

sparse graph

sparse matrix

sparsification

sparsity

spatial access method

spiral storage

splay tree

SPMD: see single program multiple data

square matrix

square root

SST: see minimum spanning tree

stable

stack

stack tree

star encoding

star-shaped polygon

start state

state

state machine

state transition: see transition

static

static Huffman coding: see Huffman coding

s-t cut

st-digraph

Steiner point

Steiner ratio

Steiner tree

Steiner vertex

Steinhaus-Johnson-Trotter: see Johnson-Trotter

Stirling's approximation

Stirling's formula

stooge sort

straight-line drawing

strand sort

strictly decreasing

strictly increasing

strictly lower triangular matrix

strictly upper triangular matrix

string

string editing problem

string matching

string matching on ordered alphabets

string matching with errors

string matching with mismatches

string searching: see string matching

strip packing

strongly connected component

strongly connected graph

strongly NP-hard

subadditive ergodic theorem

subgraph

subgraph isomorphism

sublinear time algorithm

subsequence

subset

substring

subtree

suffix

suffix array

suffix automaton

suffix tree

superimposed code

superset

supersink

supersource

symmetric

symmetrically linked list: see doubly linked list

symmetric binary B-tree: see red-black tree

symmetric set difference

symmetry breaking

saturated edge

(definition)

Definition: An edge in a flow network which has the maximum possible flow.

Author: PEB

SBB tree

(data structure)

Definition: A symmetric binary B-tree. Now known as a red-black tree.

Author: PEB

scan

(algorithm)

Definition: A parallel operation in which each element in an array or linked list receives the sum of all previous elements.

Also known as prefix sums.

Note: Also called prefix sums. From Algorithms and Theory of Computation Handbook, page 47-40, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

scapegoat tree

(algorithm)

Definition: A binary search tree that needs no balance information. Search time is logarithmic, and the amortized cost of update is logarithmic.

Note: I. Galperin and R. L. Rivest, Scapegoat trees, Proc. 4th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1993, pages 165-174.

Author: PEB

Schorr-Waite graph marking algorithm

(algorithm)

Definition: A class of algorithms to mark all reachable nodes in a directed graph by reversing pointers on the way down, then restoring them upon leaving. It uses only a few bits of extra space per node and a few work pointers.

Aggregate child (... is a part of or used in me.)
directed graph, binary tree representation of trees.

Author: PEB

Herbert Schorr and William M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, CACM, 10(8):501-506, August 1967.

There are many variants, better presentations, and proofs of correctness, such as David Gries, Schorr-Waite Graph Marking Algorithm - Developed With Style, 2007.

Historical Note
Knuth says this method was "discovered independently by Peter Deutsch and by Herbert Schorr and W. M. Waite in 1965" [Knuth97, 1:418, Sect. 2.3.5], but I cannot find any other documentation crediting Deutsch.

search

(algorithm)

Definition: To look for a value or item in a data structure. There are dozens of algorithms, data structures, and approaches.

Note: For more information, see the data structure in question or terms related to searching.

Author: PEB

search tree

(data structure)

Definition: A tree where every subtree of a node has keys less than any other subtree of the node to its right. The keys in a node are conceptually between subtrees and are greater than any keys in subtrees to its left and less than any keys in subtrees to its right.

Specialization (... is a kind of me.)
binary search tree, B-tree, (a, b)-tree, ternary search tree.

Note: A search tree that is also a binary tree is a binary search tree.

Author: PEB

search tree property

(definition)

Definition: When the key of every node of a binary tree is larger than the key of its left child and smaller than its right child.

Note: A binary tree which has this property is a binary search tree.

Author: CLK

secant search

(algorithm)

Definition: Search a sorted array by estimating the next position to check based on the values at the two previous positions checked.

Author: PEB

secondary clustering

(definition)

Definition: The tendency for some collision resolution schemes to create long run of filled slots away from a key hash position, e.g., along the probe sequence.

Note: Secondary clustering increases average search time. Even quadratic probing is susceptible to secondary clustering since keys that have the same hash value also have the same probe sequence. Clustering may be minimized with double hashing.

Author: PEB

segment

(definition)

Definition: (1) The substring of a pattern delimited by two don't cares or one don't care and beginning or end of the pattern. (2) A substring.

Note: From Algorithms and Theory of Computation Handbook, page 13-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

Select

(algorithm)

Definition: A four-part algorithm to select the k^th smallest element of an array. Part 1) Consider the array as groups of 5 elements; sort and find the median of each group. 2) Use Select recursively to find x, the median of the medians. 3) Next partition the array around x. 4) Let i be the number of elements in the low side of the partition. If k ≤ i, use Select recursively to find the k^th element of the low side. Otherwise Select the k-i^th element of the high side.

Author: PEB

Robert W. Floyd and Ronald L. Rivest, Expected time bounds for selection, CACM, 18(3):165-172, March 1975

Robert W. Floyd and Ronald L. Rivest, Algorithm #489 SELECT, CACM, 18(3):173, March 1975

select and partition

(classic problem)

Definition: Given an array A of n elements and a positive integer k ≤ n, find the k^th smallest element of A and partition the array such that A[1], ..., A[k-1] ≤ A[k] ≤ A[k+1], ..., A[n].

Note: Algorithms to solve this problem are often used in sort algorithms or to find the median of a set. These can be easily changed to find the k^th largest element.

Author: VZ

selection sort

(algorithm)

Definition: A sort algorithm that repeatedly looks through remaining items to find the least one and moves it to its final location. The run time is Θ(n²), where n is the number of elements. The number of swaps is O(n).

Generalization (I am a kind of ...)
in-place sort.

Specialization (... is a kind of me.)
bingo sort.

Author: PEB

select k^th element

(classic problem)

Definition: Find the k^th smallest element of a set. Two approaches are a modified distribution sort or select and partition.

Also known as selection problem, find k^th least element, k^th smallest element.

Note: The select-and-partition approximately divides in half the number of elements that must be considered at each step. The modified distribution sort divides by m the number of elements at each step. The latter is faster, but the former is more generally applicable.

Author: PEB

select mode

(algorithm)

Definition: An algorithm to find the mode, or most frequently occurring value, in a group of elements.

Author: PEB

self-loop

(definition)

Definition: An edge of a graph which starts and ends at the same vertex.

Note: Some types of graphs allow self-loops, and some do not.

Author: PEB

self-organizing heuristic

(algorithmic technique)

Definition: Heuristic that reorders a list of elements according to how the elements are accessed.

Note: From Algorithms and Theory of Computation Handbook, page 2-14, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

self-organizing list

(data structure)

Definition: A list that reorders the elements based on some self-organizing heuristic to improve average access time.

Author: PEB

semidefinite programming

(definition)

Definition: A generalization of a linear program in which any subset of the variables may be constrained to form a semidefinite matrix.

Note: Used in recent results and obtaining better approximation algorithms for cut, satisfiability, and coloring problems. From Algorithms and Theory of Computation Handbook, page 34-18, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

separate chaining

(data structure)

Definition: A scheme in which each position in the hash table has a list to handle collisions. Each position may be just a link to the list (direct chaining) or may be an item and a link, essentially, the head of a list. In the latter, one item is in the table, and other colliding items are in the list.

Also known as external chaining.

Generalization (I am a kind of ...)
chaining, collision resolution scheme.

Specialization (... is a kind of me.)
direct chaining.

Aggregate parent (I am a part of or used in ...)
hash table.

Aggregate child (... is a part of or used in me.)
linked list.

Author: PEB

Francis A. Williams, Handling Identifiers as Internal Symbols in Language Processors, CACM, 2(6):21-24, June 1959. Each location in Williams' table an item and a list head.

separation theorem

(definition)

Definition: A theorem showing that two complexity classes are distinct. Most separation theorems have been proved by diagonalization.

Note: From Algorithms and Theory of Computation Handbook, page 27-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

set

(data structure)

Definition: An unordered collection of values where each value occurs at most once. A group of elements with three properties: (1) all elements belong to a universe, (2) either each element is a member of the set or it is not, and (3) the elements are unordered.

Formal Definition: As an abstract data type, a set has a single query function, isIn(v, S), which tells whether an element is a member of the set or not, and two modifier functions, add(v, S) and remove(v, S). These may be defined with axiomatic semantics as follows.

1. new() returns a set
2. isIn(v, new()) = false
3. isIn(v, add(v, S)) = true
4. isIn(v, add(u, S)) = isIn(v , S) if v ≠ u
5. remove(v, new()) = new()
6. remove(v, add(v, S)) = remove(v, S)
7. remove(v, add(u, S)) = add(u, remove(v, S)) if v ≠ u

The predicate isEmpty(S) may be defined with the following additional axioms.

8. isEmpty(new()) = true
9. isEmpty(add(v, S)) = false

Generalization (I am a kind of ...)
bag, abstract data type.

Authors: PR,PEB

set cover

(classic problem)

Definition: A set of sets whose union has all members of the union of all sets. The set cover problem is to find a minimum size set.

Formal Definition: Given a set S of sets, choose c ⊆ S such that U_i=1 c_i = U_i=1 S_i.

Author: PEB

set packing

(classic problem)

Definition: An optimization problem to find the largest number of mutually disjoint subsets that cover a given set of sets.

Author: BB

shadow heap

(data structure)

Definition: A heap, implemented in an array, adjacent to an unordered table. The shadow is the table nodes and all their (recursive) parents, by array index, in the heap.

Note: Personal communication from Chris L. Kuszmaul <fyodor@nas.nasa.gov>, January 1999.

Author: CLK

shadow merge

(algorithm)

Definition: An algorithm to merge two heaps by concatenating the smaller heap to the larger, then reordering just the concatenated nodes and their parents to restore the heap property.

Note: Personal communication from Chris L. Kuszmaul <fyodor@nas.nasa.gov>, January 1999.

Author: CLK

shadow merge insert

(algorithm)

Definition: An algorithm to insert a new node into a shadow heap. The new node is placed in the unordered table. When the table grows beyond some threshold size, table nodes and all their parents are reordered so everything is a heap.

Note: If the threshold size is O(log n), where n is the size of the heap, insertion is O(log log n), amortized. Personal communication from Chris L. Kuszmaul <fyodor@nas.nasa.gov>, January 1999.

Author: CLK

Shannon-Fano coding

(algorithm)

Definition: A variable-length coding based on the frequency of occurrence of each character. Divide the characters into two sets with the frequency of each set as close to half as possible, and assign the sets either 0 or 1 coding. Repeatedly divide the sets until each character has a unique coding.

Note: Shannon-Fano is a minimal prefix code. Huffman is optimal for character coding (one character-one code word) and simple to program. Arithmetic coding is better still, since it can allocate fractional bits, but is more complicated and has patents.

Author: PEB

Debra A. Lelewer's and Daniel S. Hirschberg's survey of data compression.

shared memory

(definition)

Definition: All processors have the same global image of (and access to) all of the memory.

Aggregate parent (I am a part of or used in ...)
parallel random-access machine.

Note: From Algorithms and Theory of Computation Handbook, page 46-18, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

Shell sort

(algorithm)

Definition: The first diminishing increment sort. On each pass i sets of n/i items are sorted, typically with insertion sort. On each succeeding pass, i is reduced until it is 1 for the last pass. A good series of i values is important to efficiency.

Generalization (I am a kind of ...)
diminishing increment sort.

Aggregate child (... is a part of or used in me.)
insertion sort.

Authors: PEB,ASK

Donald Lewis Shell, A High-Speed Sorting Procedure, CACM, 2(7):30-32, July 1959.

Historical Note
This algorithm was improperly called the Shell-Metzner sort by John P. Grillo, A Comparison of Sorts, Creative Computing, 2:76-80, Nov/Dec 1976.

Grillo cites Fredric Stuart, FORTRAN Programming, John Wiley and Sons, New York, 1969, page 294. In crediting "one of the fastest" programs for sorting, Stuart says in a footnote, "Published by Marlene Metzner, Pratt & Whitney Aircraft Company. From a method described by D. L. Shell."

On 3 April 2003 Marlene Metzner Norton wrote

I had nothing to do with the sort, and my name should never have been attached to it.

So, here's the scoop.

I graduated from college in 1956 with a degree in Math. The math I took for a college degree in 1956 is pretty much all taught in high school now. I applied for a job at GE in Evendale, Cincinnati. (It was that or teach high school.) They put me to work programming an IBM 704 in an assembly language called CAGE. I don't remember what it stood for, but the GE was General Electric. Probably "Computer Assembler by General Electric". Don Shell worked in the same building, but he was manager of the Systems Analysts. I was one of the many who got several pages of equations and turned them into code that would run via punched cards. This was before Basic and Fortran. The Systems Analysts wrote assemblers, ways to create buffers to make printing faster, etc. I doubt that Don Shell even knew I who I was. About 1959 we started using Fortran -- just a little.

I think Don Shell wrote up the theory of his sorting method for the Computing Dept. newsletter. I thought it was interesting and held on to a copy.

In 1960, I bought a convertible and moved to Florida. Why? I was young, single, the field was wide open and Florida sounded like fun. Accepted a job at Pratt & Whitney in West Palm Beach. Did the same kind of programming, but Pratt had a brand new IBM 7090. They programmed in SAP. It was similar to CAGE. The logic was the same, but the instruction names differed just enough to be confusing.

Somewhere around 1961 or so, Pratt got an IBM 1620. This was a much smaller computer using punched paper tape instead of cards. Colleges used it for teaching computers. Pratt used it in the Engineering Dept. so engineers could handle smaller problems on their own instead of bringing them to the Computer Lab. I was put in charge of co-ordinating the 1620 in Engineering with the Computer Dept. IBM started a 1620 USER's group. I was sent to the first meeting. Being the only woman there, I was naturally voted in as Secretary-Treasurer. Within the first year, a company in Germany bought one so now it was the IBM 1620 INTERNATIONAL USER'S GROUP.

The User's Group put out a Newsletter. People wrote in with questions, suggestions, ideas, etc. To help fill up one of the earlier editions, I pulled out Don Shell's sort method and coded it in Fortran. Took about 10 lines of code, give or take five, and an equal amount of time. Gave Don Shell complete credit.

In 1963 I got married. In 1964 I left P & W to start a family. Taught the 1620 and the IBM 1401 at Palm Beach Junior College (now Palm Beach Community College) for a couple of years, but had no contact with P & W or the User's Group.

Now I find someone who read it started calling it Shell-Metzner. It's a wonder Don Shell didn't hunt me down and sue!

Marlene

PS. On the up side, I emailed your website to my kids. The reaction to the idea that Mom was once "smart" was worth the potential law suit.

Shift-Or

(algorithm)

Definition: A string matching algorithm which keeps an array of bits, R, showing if prefixes of the pattern don't match at the current place. Before searching, mismatch arrays are computed for each character in the alphabet and saved in an array, S. For the next position, with the character c, R = shift(R) or S[c]. If the last bit of R is 0, the pattern matches.

Author: PEB

shortest common supersequence

(classic problem)

Definition: Find the shortest string that contains two or more strings as subsequences.

Author: PEB

shortest common superstring

(classic problem)

Definition: Find the shortest string that contains two or more strings as substrings.

Author: PEB

shortest path

(classic problem)

Definition: The problem of finding the shortest path in a graph from one vertex to another. "Shortest" may be least number of edges, least total weight, etc.

Also known as single-pair shortest-path problem.

Author: PEB

shuffle sort

(algorithm)

Definition: A distribution sort algorithm that begins by removing the first 1/8 of the n items, sorting them (recursively), and putting them in an array. This creates n/8 buckets to which the remaining 7/8 of the items are distributed. Each bucket is then sorted, and the buckets are concatenated.

Generalization (I am a kind of ...)
distribution sort.

Aggregate parent (I am a part of or used in ...)
J sort.

Author: PEB

sibling

(definition)

Definition: A node in a tree that has the same parent as another node is its sibling.

Author: PEB

sieve of Eratosthenes

(algorithm)

Definition: An algorithm to find all prime numbers up to a certain N. Begin with an (unmarked) array of integers from 2 to N. The first unmarked integer, 2, is the first prime. Mark every multiple of this prime. Repeatedly take the next unmarked integer as the next prime and mark every multiple of the prime.

Author: PEB

sift up

(algorithm)

Definition: Restoring the heap property by swapping a node with its parent, and repeating the process on the parent until the root is reached or the heap property is satisfied.

Note: Insertion in a binary heap is implemented by adding a node to the end of of the array and then performing a "sift up" starting at that node. After LK.

Author: PEB

signature

(definition)

Definition: The types or domains, and order, in some representations, of inputs to and outputs from a function.

Note: For instance, the signature of the C library function strncmp() (compare up to n characters of two strings) is int (char *, char *, int). That is, it takes two C strings and an integer, and returns an integer.

Author: PR

simple merge

(algorithm)

Definition:Merge n sorted streams into one output stream. All the stream heads are compared, and the head with the least key is removed and written to the output. This is repeated until all streams are empty.

Note: The run time is Θ(mn), where m is the total number of elements and n is the number of streams.

Author: ASK

simple path

(definition)

Definition: A path that repeats no vertex.

Author: PEB

simple uniform hashing

(definition)

Definition: The assumption or goal that items are equally likely to hash to any value.

Note: If this assumption holds, items are evenly distributed in a hash table and there are a minimum of collisions.

Author: PEB

simplex

(definition)

Definition: The simplest N-dimensional polytope. The generalization of a triangle (2D) or tetrahedron (3D).

Generalization (I am a kind of ...)
polytope.

Note: The one dimensional simplex is a line segment.

Author: PEB

Eric W. Weisstein, Simplex, from MathWorld--A Wolfram Web Resource.

simulated annealing

(algorithm)

Definition: A technique to find a good solution to an optimization problem by trying random variations of the current solution. A worse variation is accepted as the new solution with a probability that decreases as the computation proceeds. The slower the cooling schedule, or rate of decrease, the more likely the algorithm is to find an optimal or near-optimal solution.

Author: PEB

simulation theorem

(definition)

Definition: One kind of computation can be simulated by another kind within stated complexity bounds. Most known containment or equality relationships between complexity classes were proved this way.

Note: From Algorithms and Theory of Computation Handbook, page 27-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

single-destination shortest-path problem

(classic problem)

Definition: Find the shortest path from each vertex in a weighted, directed graph to a specific destination vertex.

Note: Equivalent to the single-source shortest-path problem with all directions reversed.

Author: PEB

single program multiple data

(definition)

Definition: The dominant style of parallel programming, where all processors use the same program, though each has its own data.

Also known as SPMD.

Note: From Algorithms and Theory of Computation Handbook, page 46-18, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

single-source shortest-path problem

(classic problem)

Definition: Find the shortest paths from a specific source vertex to every other vertex in a weighted, directed graph. Dijkstra's algorithm solves this if all weights are nonnegative. The Bellman-Ford algorithm handles any weights.

Note: Equivalent to the single-destination shortest-path problem with all directions reversed.

Author: PEB

singularity analysis

(definition)

Definition: A complex asymptotic technique for determining the asymptotics of certain algebraic functions.

Author: CRC-A

sink

(definition)

Definition: A vertex of a directed graph with no outgoing edges. More formally, a vertex with with out-degree 0.

Note: Conceptually, a final destination of whatever is flowing through the graph. In UML, a consumer of data in a design.

Author: PEB

skd-tree

(data structure)

Definition: The spatial k-d tree is a spatial access method where successive levels are split along different dimensions. Objects are indexed by their centroid, and the minimum bounding box of objects in a node are stored in the node.

Note: After [GG98].

Author: PEB

skew symmetry

(definition)

Definition: The property that the flow is the same amount, but reversed direction, starting from either vertex of every edge of a flow network. More formally, for an edge e=(v,w), f(v,w) = -f(w,v), where f(a,b) is the flow from a to b.

Note: From Algorithms and Theory of Computation Handbook, page 7-10, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

skip list

(data structure)

Definition: A randomized variant of an ordered linked list with additional, parallel lists. Parallel lists at higher levels skip geometrically more items. Searching begins at the highest level, to quickly get to the right part of the list, then uses progressively lower level lists. A new item is added by randomly selecting a level, then inserting it in order in the lists for that and all lower levels. With enough levels, searching is O(log n).

Generalization (I am a kind of ...)
ordered linked list.

Aggregate child (... is a part of or used in me.)
randomized algorithm.

Author: PEB

(click on Dictionaries, then Skip Lists) diagrams and explanation (and code) at ePaperPress.

William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees, CACM, 33(6):668-676, June 1990.

slope selection

(classic problem)

Definition: Given a set of points in a plane and an integer k ≤ ( n OVER  2 ), find the line between pairs of points which has the k^th smallest slope.

Note: Adapted from [AS98, page 416].

Author: PEB

Smith algorithm

(algorithm)

Definition: A string matching algorithm which computes the shift value for both the rightmost character of the window and the character preceding it, then uses the maximum of the two values.

Author: BB

P. D. Smith, Experiments with a very fast substring search algorithm, Software Practice & Experience, 21(10):1065-1074, 1991.

Smith-Waterman algorithm

(algorithm)

Definition: A means of searching protein databases to find those with the best alignment.

Aggregate child (... is a part of or used in me.)
dynamic programming.

Author: PEB

Some notes and diagrams about how it works. A few explanatory slides.

Temple F. Smith and Michael S. Waterman, Identification of Common Molecular Subsequences, J. Mol. Biol., 147:195-197, 1981.

smoothsort

(algorithm)

Definition: A variant of heapsort that takes advantage of a partially ordered table. Performance is O(n) when input is sorted and O(n log n) performance for worst case.

Note: From Lynn Milnes <trjudo@hotmail.com> August 2003

Author: PEB

Edsger W. Dijkstra, An alternative to Heapsort for sorting in situ, manuscript, June 1981. PDF.

solvable

(definition)

Definition: A computational problem that can be solved by a Turing machine. The problem may have a nonbinary output.

Note: From Algorithms and Theory of Computation Handbook, page 26-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

sort

(algorithm)

Definition: Arrange items in a predetermined order. There are dozens of algorithms, the choice of which depends on factors such as the number of items relative to working memory, knowledge of the orderliness of the items or the range of the keys, the cost of comparing keys vs. the cost of moving items, etc. Most algorithms can be implemented as an in-place sort, and many can be implemented so they are stable, too.

Formal Definition: The sort operation may be defined in terms of an initial array, S, of N items and a final array, S′, as follows.

1. S′_i ≤ S′_i+1, 0 < i < N
   (the items are in order) and
2. S′ is a permutation of S.

Generalization (I am a kind of ...)
permutation.

Specialization (... is a kind of me.)
quicksort, heapsort, Shell sort, comb sort, radix sort, bucket sort, insertion sort, selection sort, merge sort, counting sort, histogram sort, strand sort, J sort, shuffle sort, American flag sort, gnome sort, bubble sort, bidirectional bubble sort, treesort (1), adaptive heap sort, multikey Quicksort, topological sort.

Author: PEB

sorted array

(data structure)

Definition: An array whose items are kept sorted, often so searching is faster.

Author: PEB

sorted list

(data structure)

Definition: A list whose items are kept sorted.

Note: Often the term "sorted list" is short for "ordered linked list".

Author: PEB

soundex

(algorithm)

Definition: An algorithm to code surnames phonetically by reducing them to the first letter and up to three digits, where each digit is one of six consonant sounds. This reduces matching problems from different spellings.

Generalization (I am a kind of ...)
phonetic coding algorithm.

Note: The algorithm was devised to code names recorded in US census records. The standard algorithm works best on European names. Variants have been devised for names from other cultures.

Author: PEB

NARA Soundex Indexing System (or GIL 55) with links to encoders and more information. Overview of Soundex.

source

(definition)

Definition: (1) A vertex of a directed graph with no incoming edges. More formally, a vertex with in-degree 0. (2) The vertex from which an edge of a directed graph leaves.

Author: PEB

space-constructible function

(definition)

Definition: A function s(n) that gives the actual space used by some Turing machine on all inputs of length n.

Note: From Algorithms and Theory of Computation Handbook, page 27-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

space ordering method

(algorithm)

Definition: A mapping from a discrete k-dimensional space into a linear order.

Author: PEB

spanning tree

(definition)

Definition: A connected, acyclic subgraph containing all the vertices of a graph.

Note: From Algorithms and Theory of Computation Handbook, page 1-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

sparse graph

(definition)

Definition: A graph in which the number of edges is much less than the possible number of edges.

Generalization (I am a kind of ...)
graph.

Author: PEB

sparse matrix

(data structure)

Definition: A matrix that has relatively few non-zero (or "interesting") entries. It may be represented in much less than n × m space.

Aggregate child (... is a part of or used in me.)
list, orthogonal lists, array, or point access method.

Note: A n × m matrix with k non-zero entries is sparse if k << n × m. It may be faster to represent the matrix compactly as a list of the non-zero entries in coordinate format (the value and its row/column position), as a list or array of lists of entries (one list for each row), two orthogonal lists (one list for each column and one list for each row), or by a point access method.

Author: PEB

A picture of a sparse matrix with orthogonal lists. Yousef Saad's Iterative methods for sparse linear systems (PDF), chapters 1-3 of a textbook covering linear algebra and types of matrices. Sparse matrix implementations, including the coordinate format, begin on page 85 (PDF page 97). Other formats and information on a newer edition.

sparsification

(algorithmic technique)

Definition: Technique for designing dynamic graph algorithms, which when applicable transform a time bound of T(n,m) onto O(T(n,n)), where m is the number of edges and n is the number of vertices of the given graph.

Note: From Algorithms and Theory of Computation Handbook, page 8-22, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

sparsity

(definition)

Definition: Instances of the longest common subsequence problem in which the number of matches is small compared to the product of the lengths of the input strings.

Note: From Algorithms and Theory of Computation Handbook, page 13-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

spatial access method

(definition)

Definition: A data structure to search for lines, polygons, etc.

Also known as SAM.

Specialization (... is a kind of me.)
cell tree, extended k-d tree, GBD-tree, multilayer grid file, D-tree, P-tree, R-file, R⁺-tree, R^*-tree, R-tree, skd-tree.

Author: PEB

spiral storage

(data structure)

Definition: A dynamic hashing table that grows a few slots at a time. It uses a hash function, h, with a range of [0,1). For a key, k, an intermediate value, x= S-h(k) +h(k), is computed to find the final slot, d^x, where d>1 is called the growth factor. To increase the number of slots, increase S to S' and rehash any keys from d^S to d^S'-1.

Generalization (I am a kind of ...)
dynamic hashing.

Note: Choosing d=2 and S=log₂N, the number of slots, every expansion retires one slot and creates two new slots. Since slots in use go from d^S to d^S+1-1, they are usually remapped to physical storage.

Author: PEB

G. N. N. Martin, Spiral storage: Incrementally augmentable hash addressed storage, Theory of Computation Rep. 27, Univ. of Warwick, England, 1979.

Per-Åke Larson, Dynamic Hash Tables, CACM 31(4):446-457, April 1988.

splay tree

(data structure)

Definition: A binary search tree in which operations that access nodes restructure the tree.

Generalization (I am a kind of ...)
binary search tree.

Aggregate child (... is a part of or used in me.)
move-to-root heuristic.

Author: CLK

Daniel D. Sleator and Robert E. Tarjan, Self-Adjusting Binary Search Trees, Journal of the ACM, 32(3):652-686, 1985.

square matrix

(data structure)

Definition: A n × n matrix, i.e., one whose size is the same in both dimensions.

Generalization (I am a kind of ...)
uniform matrix.

Author: PEB

square root

(algorithm)

Definition: This describes a "long hand" or manual method of calculating or extracting square roots. Calculation of a square root by hand is a little like long-hand division.

Suppose you need to find the square root of 66564. Set up a "division" with the number under the radical. Mark off pairs of digits, starting from the decimal point. (Here the decimal point is a period (.) and a comma (,) marks pairs of digits.)

               ___________	
             \/  6,65,64.	
 

               __2________	
             \/  6,65,64.	
                -4		
               ----		
                 2		
 

               __2________	
             \/  6,65,64.	
                -4		
                -----		
             4_ ) 265		
 

               __2__6_____	
             \/  6,65,64.	
                -4		
                -----		
             46 ) 265		
                  276   TOO BIG	
 

               __2__5_____	
             \/  6,65,64.	
                -4		
                -----		
             45 ) 265		
                 -225		
                 -------		
                   40		
 

               __2__5_____	
             \/  6,65,64.	
                -4		
                -----		
             45 ) 265		
                 -225		
                 -------		
             50_ ) 4064		
 

               __2__5__8__	
             \/  6,65,64.	
                -4		
                -----		
             45 ) 265		
                 -225		
                 -------		
             508 ) 4064		
                  -4064		
                  ------		
                      0		
 

So the square root of 66564 is 258. You can continue for as many decimal places as you need: just bring down more pairs of zeros.

Why does this work?

Consider (10A + B)² = 100A² + 2 × 10AB + B² and think about finding the area of a square. Remember that 10A + B is just the numeral with B in the units place and A in the higher position. For 42, A=4 and B=2, so 10 × 4 + 2 = 42.

The area of the two skinny rectangles is 2 × 10A × B. The tiny square is B². If we know A and the area of the square, S, what B should we choose?

We previously subtracted A² from S. To scale to 100A², we bring down two more digits (a factor of 100) of the size of S. We write down twice A (2A), but shifted one place to leave room for B (10 × 2A or 2 × 10A). Now we add B to get 2 × 10A + B. Multiplying by B gives us 2 × 10AB + B². When we subtract that from the remainder (remember we already subtracted A²), we have subtracted exactly (10A + B)². That is, we have improved our knowledge of the square root by one digit, B.

We take whatever remains, scale again by 100, by bringing down two more digits, and repeat the process.

Author: PEB

stable

(definition)

Definition: An algorithm where the relative order upon input of items with equal keys is always preserved in the output. Usually a sort algorithm.

Author: CRC-A

stack

(data structure)

Definition: A collection of items in which only the most recently added item may be removed. The latest added item is at the top. Basic operations are push and pop. Often top and isEmpty are available, too. Also known as "last-in, first-out" or LIFO.

Formal Definition: The operations new(), push(v, S), top(S), and popoff(S) may be defined with axiomatic semantics as follows.

1. new() returns a stack
2. popoff(push(v, S)) = S
3. top(push(v, S)) = v

The predicate isEmpty(S) may be defined with the following additional axioms.

4. isEmpty(new()) = true
5. isEmpty(push(v, S)) = false

Also known as LIFO.

Generalization (I am a kind of ...)
abstract data type.

Specialization (... is a kind of me.)
bounded stack, cactus stack.

Note: Other operations may include index(i, S), return the ith item in the stack, isFull(S), and rotate(i, S), move i items from top to bottom or vice versa.

Author: PEB

Examples and code. Demonstration with dynamic array and linked list implementations.

Origin is attributed to A. W. Burks, D. W. Warren, and J. B. Wright, An analysis of a logical machine using parenthesis-free notation, Mathematical Tables and Other Aids to Computation, 8(46):53-57, April 1954, and A. Newell and J. C. Shaw, Programming the logic theory machine, Proceedings of the 1957 Western Joint Computer Conference, pages 230-240, Institute of Radio Engineers, New York, February 1957.

stack tree

(definition)

Definition: A binary tree where no node, except the root, has more than one non-leaf child.

Note: This topology is used to define simple, fault-tolerant, acyclic networks. See Ann T. Tai, Savio N. Chau, and Leon Alkalai, "COTS-Based Fault Tolerance in Deep Space: Qualitative and Quantitative Analyses of a Bus Network Architecture," in Proceedings of the 4th International IEEE High-Assurance Systems Engineering Symposium (HASE '99), November 1999, Washington, D.C., pages 97 - 104.

Author: PEB

star encoding

(algorithm)

Definition: Using a fixed dictionary, encode words in text with strings having many repeated characters, typically an asterisk or "star" (*).

Author: PEB

Holger Kruse and Amar Mukherjee, Data compression using text encryption, Proc. Data Compression Conference, Snowbird, Utah, USA, pp 447-, March 1997.
Holger Kruse and Amar Mukherjee Preprocessing text to improve compression ratios, Proc. Data Compression Conference, Snowbird, Utah, USA, pp 556-464, April 1998.

star-shaped polygon

(definition)

Definition: A polygon P in which there exists an interior point p such that all the boundary points of P are visible from p.

Note: From Algorithms and Theory of Computation Handbook, page 19-27, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

start state

(definition)

Definition: An initial state or condition of a finite state machine or Turing machine. Informally, how the memory is initially set.

Author: PEB

state

(definition)

Definition: The condition of a finite state machine or Turing machine at a certain time. Informally, the content of memory.

Author: PEB

state machine

(definition)

Definition: A model of computation consisting of a (possibly infinite) set of states, a set of start states, an input alphabet, and a transition function which maps input symbols and current states to a next state. Usually understood to be a finite state machine.

Generalization (I am a kind of ...)
model of computation.

Specialization (... is a kind of me.)
finite state machine.

Author: PEB

static

(definition)

Definition: When the problem domain does not change.

Note: From Algorithms and Theory of Computation Handbook, page 20-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

s-t cut

(definition)

Definition: A partitioning of the vertices of a flow network into S and T such that the source is in S and the sink is in T.

Note: From Algorithms and Theory of Computation Handbook, page 7-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

st-digraph

(data structure)

Definition: A directed acyclic graph with two specially marked nodes, the source s and the sink t.

Note: After P. Bertolazzi, G. Di Battista, and W. Didimo, Quasi-upward planarity, Algorithmica, 32:474-506 (2002).

Author: PEB

Steiner point

(definition)

Definition: (1) A point that is not part of the input set of points, for instance, a point computed to construct a Steiner tree. (2) A point with a particular geometric relation to a triangle.

Author: CRC-A

Named for Jakob Steiner. See the following for the geometric (classical) definition of a Steiner Point.

Steiner ratio

(definition)

Definition: For a given variant of the Steiner tree problem, the maximum possible ratio of the length of a minimum spanning tree of a set of terminals to the length of an optimal Steiner tree of the same set of terminals. Usually written ρ (rho).

Note: In graphs ρ = 2. In the Euclidean metric, ρ = 2/ √(3). In the rectilinear metric, ρ = 3/2.

Author: JLG

Steiner tree

(definition)

Definition: A minimum-weight tree connecting a designated set of vertices, called terminals, in an undirected, weighted graph or points in a space. The tree may include non-terminals, which are called Steiner vertices or Steiner points.

Specialization (... is a kind of me.)
Euclidean Steiner tree, rectilinear Steiner tree.

Author: JLG

Steiner vertex

(definition)

Definition: A point that is not part of the input set of points, for instance, a point computed to construct a Steiner tree.

Author: CRC-A

Stirling's approximation

(definition)

Definition: For large values of n, n! ≈ (n/e)ⁿ √(2nπ).

Note: This approximation is taken directly from Stirling's formula.

Author: PEB

Peter Luschny lists and evaluates many approximation formulas for n!. See Eric W. Weisstein, Stirling's Approximation for a derivation and other approximations. A slightly different approximation and relative errors.

Stirling's formula

(definition)

Definition: For large values of n, (n/e)ⁿ √(2nπ) < n! < (n/e)ⁿ(1 + 1/(12n-1)) √(2nπ).

Note: After CRC Standard Mathematical Tables, Fourteenth Edition, Samuel M. Selby, ed., page 433, 1965.

Author: PEB

Peter Luschny lists and evaluates many approximation formulas for n!. See Eric W. Weisstein, Stirling's Approximation for a derivation and other approximations.

stooge sort

(algorithm)

Definition: A terribly inefficient sort algorithm that swaps the top and bottom items if needed, then (recursively) sorts the bottom two-thirds, then the top two-thirds, then the bottom two-thirds again.

Author: PEB

straight-line drawing

(definition)

Definition: A graph drawing in which each edge is represented by a straight line segment.

Note: From Algorithms and Theory of Computation Handbook, page 9-23, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

strand sort

(algorithm)

Definition: A sort algorithm that works well if many items are in order. First, begin a sublist by moving the first item from the original list to the sublist. For each subsequent item in the original list, if it is greater than the last item of the sublist, remove it from the original list and append it to the sublist. Merge the sublist into a final, sorted list. Repeatedly extract and merge sublists until all items are sorted. Handle two or fewer items as special cases.

Generalization (I am a kind of ...)
distribution sort.

Aggregate parent (I am a part of or used in ...)
J sort.

Note: This works especially well with linked lists.

Author: PEB

strictly decreasing

(definition)

Definition: A function from a partially ordered domain to a partially ordered range such that x < y implies f(x) > f(y).

Note: After [CLR90, page 32].

Author: PEB

strictly increasing

(definition)

Definition: A function from a partially ordered domain to a partially ordered range such that x < y implies f(x) < f(y).

Note: After [CLR90, page 32].

Author: PEB

strictly lower triangular matrix

(data structure)

Definition: A matrix that is only defined at (i,j) when i > j.

Generalization (I am a kind of ...)
lower triangular matrix.

Note: For example

	j
i	-	-	-	-
	7	-	-	-
	1	0	-	-
	1	9	5	-

Author: PEB

strictly upper triangular matrix

(data structure)

Definition: A matrix that is only defined at (i,j) when i < j.

Generalization (I am a kind of ...)
upper triangular matrix.

Note: For example

	j
i	-	7	7	6
	-	-	1	1
	-	-	-	8
	-	-	-	-

Author: PEB

string

(data structure)

Definition: A list of characters, usually implemented as an array. Informally a word, phrase, sentence, etc. Since text processing is so common, a special type with substring operations is often available.

Note: The term string usually refers to a small sequence of characters, such as a name or a sentence. The term text usually refers to a large sequence of characters, such as an article or a book.

Author: PEB

string editing problem

(definition)

Definition: The problem of finding an edit script of minimum cost which transforms a given string into another given string.

Note: From Algorithms and Theory of Computation Handbook, page 13-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

string matching

(classic problem)

Definition: The problem of finding occurrence(s) of a pattern string within another string or body of text. There are many different algorithms for efficient searching.

Also known as exact string matching, string searching, text searching.

Specialization (... is a kind of me.)
brute force string search, Knuth-Morris-Pratt algorithm, Boyer-Moore, Zhu-Takaoka, quick search, deterministic finite automata string search, Karp-Rabin, Shift-Or, Aho-Corasick, Smith algorithm.

Note: For large collections that are searched often, it may be far faster, though more complicated, to start with an inverted index. The name "exact string matching" is in contrast to string matching with errors.

Author: PEB

string matching with errors

(algorithm)

Definition: Searching for approximate (e.g., up to a predefined number of symbol mismatches, insertions, and deletions) occurrences of a pattern string in a text string. Preprocessing, e.g., building an index, may or may not be allowed.

Also known as approximate string matching.

Specialization (... is a kind of me.)
Ratcliff/Obershelp pattern recognition, phonetic coding, Jaro-Winkler, Levenshtein distance, string matching with mismatches.

Author: CRC-A

Qi Xiao Yang, Sung Sam Yuan, Lu Chun, Li Zhao, and Sun Peng, Faster Algorithm of String Comparison 2001.

string matching with mismatches

(algorithm)

Definition: The special case of string matching with errors where mismatches are the only type of error allowed.

Generalization (I am a kind of ...)
string matching with errors.

Specialization (... is a kind of me.)
brute force string search with mismatches.

Note: From Algorithms and Theory of Computation Handbook, page 13-17, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

strip packing

(classic problem)

Definition: Pack a set of rectangles into a strip of width 1 to minimize the height used. Rectangles may not overlap or be rotated. Without loss of generality, the height of rectangles is at most 1. This is NP-hard.

Generalization (I am a kind of ...)
optimization problem.

Note: Rectangles must have widths at most 1, otherwise they wouldn't fit in the strip. If any height is greater than 1, all heights can be scaled to no more than 1.

Author: PEB

strongly connected component

(definition)

Definition: A strongly connected subgraph, S, of a directed graph, D, such that no vertex of D can be added to S and it still be strongly connected. Informally, a maximal subgraph in which every vertex is reachable from every other vertex.

Generalization (I am a kind of ...)
maximally connected component, strongly connected graph, connected graph.

Aggregate child (... is a part of or used in me.)
depth-first search.

Author: PEB

Transitive closure has a link to Esko Nuutila and Eljas Soisalon-Soininen, On finding the strongly connected components in a directed graph (PostScript®), Information Processing Letters 49 (1993) 9-14. The paper has Tarjan's algorithm, references to other algorithms, and two faster algorithms in Pascal-like pseudo-code.

This has a linear time algorithm for finding strongly connected components:
Robert E. Tarjan, Depth-first search and linear graph algorithms, SIAM Journal on Computing, 1(2):146-160, 1972.

strongly connected graph

(definition)

Definition: A directed graph that has a path from each vertex to every other vertex.

Formal Definition: A directed graph D=(V, E) such that for all pairs of vertices u, v ∈ V, there is a path from u to v and from v to u.

Note: From Algorithms and Theory of Computation Handbook, page 6-21, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

strongly NP-hard

(definition)

Definition: The complexity class of decision problems which are still NP-hard even when all numbers in the input are bounded by some polynomial in the length of the input.

Generalization (I am a kind of ...)
NP-hard.

Note: From Algorithms and Theory of Computation Handbook, page 34-18, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science,Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

subadditive ergodic theorem

(definition)

Definition: If a stationary and ergodic process satisfies the subadditive inequality, it grows almost surely linearly in time.

Note: From Algorithms and Theory of Computation Handbook, page 14-35, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

subgraph

(definition)

Definition: A graph whose vertices and edges are subsets of another graph.

Formal Definition: A graph G'=(V', E') is a subgraph of another graph G=(V, E) iff

• V'⊆ V, and
• E'⊆ E ∧ ( (v₁, v₂)∈ E' → v₁, v₂∈ V').

Authors: PEB,AL

subgraph isomorphism

(classic problem)

Definition: Decide if there is a subgraph of one graph which is isomorphic to another graph.

Author: PEB

sublinear time algorithm

(definition)

Definition: A algorithm whose execution time, f(n), grows slower than the size of the problem, n, but only gives an approximate or probably correct answer.

Generalization (I am a kind of ...)
polynomial time algorithm with k < 1, probabilistic algorithm.

Specialization (... is a kind of me.)
logarithmic time algorithm.

Aggregate parent (I am a part of or used in ...)
quicksort: finding the pivot is a sublinear time algorithm for finding the median.

Note: A sublinear time algorithm doesn't even have the time to consider all the input; it can only sample the input. Binary search is not considered a sublinear time algorithm because the ordering property allows an accurate algorithm in less than linear time.

Author: PEB

subsequence

(definition)

Definition: Any string that can be obtained by deleting zero or more symbols from a given string.

Author: CRC-A

subset

(definition)

Definition: A set S₁ is a subset of another set S₂ if every element in S₁ is in S₂. S₂ may have exactly the same elements as S₁.

Formal Definition: S₁ ⊆ S₂ iff ∀ s, s ∈ S₁ → s ∈ S₂.

Specialization (... is a kind of me.)
proper subset, combination.

Author: PR

substring

(definition)

Definition: A string v is a substring of a string u if u=u′ vu″ for some prefix u′ and suffix u″.

Also known as factor.

Author: CRC-A

subtree

(definition)

Definition: The tree which is a child of a node.

Note: The name emphasizes that everything which is a descendant of a tree node is a tree, too, and is a subset of the larger tree.

Author: PEB

suffix

(definition)

Definition: The end characters of a string. More formally a string v is a suffix of a string u if u=u'v for some string u'.

Note: From Algorithms and Theory of Computation Handbook, page 11-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

suffix array

(data structure)

Definition: An array of all starting positions of suffixes of a string arranged in lexicographical order. This allows a binary search or fast substring search.

Generalization (I am a kind of ...)
array.

Aggregate child (... is a part of or used in me.)
suffix, binary search.

Author: CRC-A

Udi Manber and Gene Myers, Suffix Arrays: A New Method for On-Line String Searches, SIAM Journal on Computing 22(5):935-948, 1993.

suffix automaton

(definition)

Definition: The smallest automaton accepting all suffixes of a string. The states form a directed acyclic word graph or DAWG.

Note: From Algorithms and Theory of Computation Handbook, page 11-26, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

suffix tree

(data structure)

Definition: A compact representation of a trie corresponding to the suffixes of a given string where all nodes with one child are merged with their parents.

Generalization (I am a kind of ...)
Patricia tree, trie.

Specialization (... is a kind of me.)
multi suffix tree.

Author: SE

Edward M. McCreight, A space-economical suffix tree construction algorithm, Journal of the ACM, 23:262-272, 1976.

Esko Ukkonen, On-line construction of suffix trees, Algorithmica, 14(3):249-260, September 1995.
A linear time, forward construction algorithm. See Wikipedia entry for links to PDF of Ukkonen's paper.

superimposed code

(definition)

Definition: A set of bit vectors such that no vector is a subset of a bitwise or of a small number of others.

Author: PEB

Piotr Indyk, Deterministic Superimposed Coding with Applications to Pattern Matching, Proc. 38th FOCS, pages 127-136, IEEE, 1997.

superset

(definition)

Definition: A set S₁ is a superset of another set S₂ if every element in S₂ is in S₁. S₁ may have elements which are not in S₂.

Note: If S₁ is a superset of S₂, S₂ is a subset of S₁.

Author: PEB

supersink

(definition)

Definition: A vertex of a directed graph which is reachable from all other vertices.

Note: Usually added to convert a graph with multiple sinks into a graph with a single sink.

Author: JM

supersource

(definition)

Definition: A vertex of a directed graph from which all other vertices are reachable.

Note: Usually added to convert a graph with multiple sources into a graph with a single source.

Author: JM

symmetric

(definition)

Definition: A binary relation R for which a R b implies b R a.

Note: The relation "not equal to" is symmetric: if a ≠ b, then b ≠ a. However, "loves" is not symmetric since love might not be reciprocated. The relation "is married to" is symmetric, but not antisymmetric: if Paul is married to Marlena, then Marlena is married to Paul (symmetric), but that does not mean that Paul and Marlena are the same person.

Author: PEB

symmetric set difference

(definition)

Definition: Members which are in either set, but not in both. That is, for sets A and B, it is (A - B) ∪ (B - A).

12 Note: {2, 3, 5} Δ {7, 5} = {2, 3, 7}.

Author: PEB

symmetry breaking

(algorithmic technique)

Definition: To differentiate parts of a structure, such as a graph, which locally look the same to all vertices. Usually implemented with randomization.

Note: From Algorithms and Theory of Computation Handbook, page 47-40, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

Published - April 2009

Find free glossaries at TranslationDirectory.com

Find free dictionaries at TranslationDirectory.com

Subscribe to free TranslationDirectory.com newsletter

Need more translation jobs from translation agencies? Click here!

Translation agencies are welcome to register here - Free!

Freelance translators are welcome to register here - Free!

Submit your glossary or dictionary for publishing at TranslationDirectory.com

Free Newsletter

Menu

Advertisements