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
 SchorrWaite 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
 selfloop
 selforganizing heuristic
 selforganizing list
 selforganizing 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
 ShannonFano coding
 shared memory
 Shell sort
 ShiftOr
 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
 singledestination shortestpath problem
 singlepair shortestpath problem: see shortest path
 single program multiple data
 singlesource shortestpath problem
 singly linked list: see linked list
 singularity analysis
 sink
 sinking sort: see bubble sort
 skdtree
 skew symmetry
 skip list
 skip search
 slope selection
 Smith algorithm
 SmithWaterman algorithm
 smoothsort
 solvable
 sort
 sorted array
 sorted list
 sort in place: see inplace sort
 soundex
 source
 spaceconstructible 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
 starshaped polygon
 start state
 state
 state machine
 state transition: see transition
 static
 static Huffman coding: see Huffman coding
 st cut
 stdigraph
 Steiner point
 Steiner ratio
 Steiner tree
 Steiner vertex
 SteinhausJohnsonTrotter: see JohnsonTrotter
 Stirling's approximation
 Stirling's formula
 stooge sort
 straightline 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 NPhard
 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 Btree: see redblack 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 Btree. Now known as a redblack 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 4740, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 ACMSIAM Symp. on Discrete Algorithms (SODA), 1993, pages 165174.
Author: PEB
SchorrWaite 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.
Note:
The graph must be a binary graph, that is, nodes have outdegree at most two. Any graph may be represented as a binary graph using a technique like binary tree representation of trees. This algorithm works for graphs with cycles, so is not limited to binary trees. This is used in garbage collection to mark all nodes in use. Any node still unmarked after the algorithm finishes is unused and may be collected. Although a depthfirst search to mark nodes is easy to write, it takes extra space proportional to the maximum search depth, which could be all nodes.
Author: PEB
More information
Herbert Schorr and William M. Waite, An efficient machineindependent procedure for garbage collection in various list structures, CACM, 10(8):501506, August 1967. There are many variants, better presentations, and proofs of correctness, such as David Gries, SchorrWaite 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, Btree, (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.
Note:
It is called "secant search" because it uses the secant of the function at two successive points to approximate the derivative in the NewtonRaphson formula. To find a key k in an array v with indexes from 0 to n1, begin with x_{0} = 0, x_{1} = n1, and i = 1. Compute the next position with x_{i+1} = x_{i}  (v[x_{i}]k) * (x_{i}  x_{i1})/(v[x_{i}]  v[x_{i1}]). If this lies outside the range, a different method (e.g., midpoint of the range) must be used to get the next position. Although the theoretical execution time is better than interpolation search or binary search, coding is tricky, and the gains from faster convergence are offset by higher costs per iteration. Richard Harter <cri@tiac.net> January 2001.
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 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
Select
(algorithm)
Definition:
A fourpart 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 ki^{th} element of the high side.
Note:
After [CLR90, p 190]. Sometimes called "quick select". The number of comparisons to select the i^{th} smallest of n numbers is n+min(i,ni)+o(n) or Θ(n).
Author: PEB
More information
Robert W. Floyd and Ronald L. Rivest, Expected time bounds for selection, CACM, 18(3):165172, 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[k1] ≤ 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 ...)
inplace sort.
Specialization (... is a kind of me.)
bingo sort.
Note:
Sorting can be done in place by swapping the least remaining item with the item in the next position to be filled. However, this implementation of the algorithm is not stable. If the (first) least remaining item is inserted, that is, all intervening items moved down (instead of swapping), this algorithm is stable. However, if the items are in an array, rather than, say a linked list, the number of moves is O(n²). The algorithm is then like bubble sort with a more complicated control structure. Heapsort can be seen as a variant of selection sort in which sorted items are arranged (in a heap) to quickly find the next item.
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 selectandpartition 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
selfloop
(definition)
Definition:
An edge of a graph which starts and ends at the same vertex.
Note:
Some types of graphs allow selfloops, and some do not.
Author: PEB
selforganizing 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 214, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
selforganizing list
(data structure)
Definition:
A list that reorders the elements based on some selforganizing 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 3418, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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.
Note:
The items in the list may be searched and maintained with any of the list search algorithms. Any searchable data structure may be used instead of a list. After A href="../terms.html#GBY91">[GBY91, pages 7477]
Author: PEB
More information
Francis A. Williams, Handling Identifiers as Internal Symbols in Language Processors, CACM, 2(6):2124, 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 2721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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.
 new() returns a set
 isIn(v, new()) = false
 isIn(v, add(v, S)) = true
 isIn(v, add(u, S)) = isIn(v , S) if v ≠ u
 remove(v, new()) = new()
 remove(v, add(v, S)) = remove(v, S)
 remove(v, add(u, S)) = add(u, remove(v, S)) if v ≠ u
where S is a set and u and v are elements. The predicate isEmpty(S) may be defined with the following additional axioms.
 isEmpty(new()) = true
 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
ShannonFano coding
(algorithm)
Definition:
A variablelength 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:
ShannonFano is a minimal prefix code. Huffman is optimal for character coding (one characterone 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
More information
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 randomaccess machine.
Note:
From Algorithms and Theory of Computation Handbook, page 4618, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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.
Note:Comb sort does a single "bubbling" pass (ala bubble sort) over each set for each gap or increment, whereas Shell sort completely sorts each set. Donald E. Knuth extensively analyzes this algorithm in [Knuth98, vol. 3, Sect. 5.2.1]. A good set of increments is 2^{k}+1, . . ., 9, 5, 3, 1 with the first increment no more than N/3.
Authors: PEB,ASK
More information
Donald Lewis Shell, A HighSpeed Sorting Procedure, CACM, 2(7):3032, July 1959.
Historical Note
This algorithm was improperly called the ShellMetzner sort by John P. Grillo, A Comparison of Sorts, Creative Computing, 2:7680, 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 coordinating 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 SecretaryTreasurer. 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 ShellMetzner. 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.
ShiftOr
(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 singlepair shortestpath problem.
Note:
The problem is to find the weight of the shortest path. For a map, it is to produce the (shortest) road distance from one city to another city, not which roads to take. A modification to most algorithms finds the shortest path, too. In predecessor[i][j] save the immediate predecessor of the shortest path from i to j. Suppose predecessor[i][j] is k; then the shortest path ends with ... → k → j. If predecessor[i][k] is p, the shortest path ends with ... → p → k → j. Continue working backward until you reach i.
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.
Note:
Shuffle sort can be thought of as forming very wide trees, like Btree with m=n/8, to sort efficiently in many cases. Shuffle sort estimates the distribution of the items to be sorted by examining the first n/8 items. Distributive partitioning sort estimates the distribution by approximating the median and linearly interpolating from the minimum to the median and from the median to the maximum.
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.
Note:
Invented by Eratosthenes of Cyrene (276 BC  194 BC). For example, here's a beginning array.  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  Since 2 is unmarked, it is our first prime. We mark every second integer, that is, 4, 6, 8, 10, 12, etc.  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  The next unmarked integer is 3, so it is prime. We mark every third integer, i.e., 6, 9, 12, etc. Note that we mark 6, 12, 18, etc. again.  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  Now 5 is the next prime, and we mark every fifth integer. The only new integer marked in range is 25.  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  From here we find the primes 7, 11, 13, 17, 19, and 23.  When we find the prime n, we can begin marking at n². Why? Any composite less than n² is a multiple of a lesser prime, and so will have been marked earlier. As a corollary, we can stop marking when n² is greater than our range. That is, any unmarked numbers greater than the square root of the range are primes. The naive implementation is not practical for large N since the memory is Θ(N). More efficient implementations use a segmented sieve.
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 Ndimensional 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
More information
Eric W. Weisstein, Simplex, from MathWorldA 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 nearoptimal solution.
Note:
This technique stems from thermal annealing which aims to obtain perfect crystallizations by a slow enough temperature reduction to give atoms the time to attain the lowest energy state. This search tries to avoid local minima by jumping out of them early in the computation. Toward the end of the computation, when the temperature, or probability of accepting a worse solution, is nearly zero, this simply seeks the bottom of the local minimum. The chance of getting a good solution can be traded off with computation time by slowing down the cooling schedule. The slower the cooling, the higher the chance of finding the optimum solution, but the longer the run time. Thus effective use of this technique depends on finding a cooling schedule that gets good enough solutions without taking too much time. After Daniel Thiel <mouttaqu@enitiaanantes.fr>, 31 January 2000.
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 2721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
singledestination shortestpath 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 singlesource shortestpath 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 4618, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
singlesource shortestpath 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 BellmanFord algorithm handles any weights.
Note:
Equivalent to the singledestination shortestpath problem with all directions reversed.
Author: PEB
singularity analysis
(definition)
Definition:
A complex asymptotic technique for determining the asymptotics of certain algebraic functions.
Note:
From Algorithms and Theory of Computation Handbook, page 1435, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
sink
(definition)
Definition:
A vertex of a directed graph with no outgoing edges. More formally, a vertex with with outdegree 0.
Note:
Conceptually, a final destination of whatever is flowing through the graph. In UML, a consumer of data in a design.
Author: PEB
skdtree
(data structure)
Definition:
The spatial kd 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 710, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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
More information
(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):668676, 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
More information
P. D. Smith, Experiments with a very fast substring search algorithm, Software Practice & Experience, 21(10):10651074, 1991.
SmithWaterman 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
More information
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:195197, 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
More information
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 2620, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 inplace 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.  S′_{i} ≤ S′_{i+1}, 0 < i < N
(the items are in order) and  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.
Note:
Any sorting algorithm can be made stable by appending the original position to the key. When otherwiseequal keys are compared, the positions "break the tie" and the original order is maintained. Knuth notes [Knuth98, 3:1, Chap. 5] that this operation might be called "order". In standard English, "to sort" means to arrange by kind or to classify. The term "sort" came to be used in Computer Science because the earliest automated ordering procedures used punched card machines, which classified cards by their holes, to implement radix 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
More information
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 indegree 0. (2) The vertex from which an edge of a directed graph leaves.
Note:
Conceptually, an origin of whatever is directed in the graph. In UML, a producer of data in a design. (2) That is, an edge goes from the source to the target.
Author: PEB
spaceconstructible 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 2721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
space ordering method
(algorithm)
Definition:
A mapping from a discrete kdimensional space into a linear order.
Note:
A concrete version of the problem is, in what order should one visit every square in a checkerboard? Equivalently, how should one map a 2dimensional array in memory? A transversal of the mapped points in their linear order yields a spacefilling curve. There is a good survey on pages 167169 of Hanan Samet, ObjectBased and ImageBased Object Representation, ACM Computing Surveys, 36(2):159217, June 2004. The article describes several methods and reviews their properties:  row order (row major)
 rowprime order
 Morton order
 PeanoHilbert order
 Cantordiagonal order
 spiral order
 Gray order
 double Gray order
 U 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 126, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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.
Note:
A directed graph can have at most n(n1) edges, where n is the number of vertices. An undirected graph can have at most n(n1)/2 edges. There is no strict distinction between sparse and dense graphs. Bruno Preiss' definition of sparse and dense graphs has problems, but may help. First, for one graph, one can always choose a k. Second a class of graphs might be considered sparse if E = O(V^{k}) and 1 < k < 2. E is the number of edges, and V is the number of vertices.
Preiss reference from Andreas Leiser <andreas.leiser@bluewin.ch> 22 December 2003
Author: PEB
sparse matrix
(data structure)
Definition:
A matrix that has relatively few nonzero (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 nonzero entries is sparse if k << n × m. It may be faster to represent the matrix compactly as a list of the nonzero 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
More information
A picture of a sparse matrix with orthogonal lists. Yousef Saad's Iterative methods for sparse linear systems (PDF), chapters 13 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 822, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 kd tree, GBDtree, multilayer grid file, Dtree, Ptree, Rfile, R^{+}tree, R^{*}tree, Rtree, skdtree.
Note:
After [GG98]. Point access methods may not support region, overlap, enclosure, etc. searches very well.
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= Sh(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_{2}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
More information
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):446457, 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.)
movetoroot heuristic.
Author: CLK
More information
Daniel D. Sleator and Robert E. Tarjan, SelfAdjusting Binary Search Trees, Journal of the ACM, 32(3):652686, 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 longhand 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. Look at the leftmost digit(s) (6 in this case). What is the largest number whose square is less than or equal to it? It is 2, whose square is 4. Write 2 above, write the square below and subtract. __2________ \/ 6,65,64. 4  2 Now bring down the next two digits (65). The next "divisor" is double the number on top (2x2=4) and some other digit in the units position (4_). __2________ \/ 6,65,64. 4  4_ ) 265 What is the largest number that we can put in the units and multiply times the divisor and still be less than or equal to what we have? (Algebraically, what is d such that d × 4d ≤ 265?) It looks like 6 might work (since 6 * 40 = 240), but 6 is too big, since 6 * 46 = 276. __2__6_____ \/ 6,65,64. 4  46 ) 265 276 TOO BIG So try 5 instead. __2__5_____ \/ 6,65,64. 4  45 ) 265 225  40 Repeat: bring down the next two digits, and double the number on top (2x25=50) to make a "divisor", with another unit. __2__5_____ \/ 6,65,64. 4  45 ) 265 225  50_ ) 4064 It looks like 8 would work. Let's see. __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.
Note:
In computers and handheld calculators, square root, sine, cosine, and other transcendental functions are calculated with sophisticated functions, such as Taylor series, CORDIC, or NewtonRaphson method, sometimes called Newton's method. This lesson explains, for instance, possible difficulties in convergence.
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.
Note:
Many different operations, such as sort, merge, and select the minimum using a priority queue, can be stable. Suppose we need to order the following people by age: Max, age 45, Brodsky (19), David (21), Carla (45), and Liang (19). A stable sort would yield Brodsky (19), Liang (19), David (21), Max (45), and Carla (45). Note that Brodsky still precedes Liang, and Max still precedes Carla. A sort that is not stable may put Liang before or after Brodsky and Carla before or after Max. A radix sort requires each phase to be stable. Many algorithms can be turned into a stable variant by appending the original position to the key. When otherwiseequal keys are compared, the positions "break the tie" and the original order is maintained.
From Algorithms and Theory of Computation Handbook, and is Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 "lastin, firstout" or LIFO.
Formal Definition: The operations new(), push(v, S), top(S), and popoff(S) may be defined with axiomatic semantics as follows.
 new() returns a stack
 popoff(push(v, S)) = S
 top(push(v, S)) = v
where S is a stack and v is a value. The pop operation is a combination of top, to return the top value, and popoff, to remove the top value. The predicate isEmpty(S) may be defined with the following additional axioms.
 isEmpty(new()) = true
 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
More information
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 parenthesisfree notation, Mathematical Tables and Other Aids to Computation, 8(46):5357, April 1954, and A. Newell and J. C. Shaw, Programming the logic theory machine, Proceedings of the 1957 Western Joint Computer Conference, pages 230240, 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 nonleaf child.
Note:
This topology is used to define simple, faulttolerant, acyclic networks. See Ann T. Tai, Savio N. Chau, and Leon Alkalai, "COTSBased Fault Tolerance in Deep Space: Qualitative and Quantitative Analyses of a Bus Network Architecture," in Proceedings of the 4th International IEEE HighAssurance 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" (*).
Note:
This transformation does not compress the text, but prepares it for compression. With many runs of stars, the encoded text may be much more compressible than the original text. The sender and the receiver must communicate the dictionary somehow. The code string for a word is the same length as the word. Kruse and Mukherjee constructed a dictionary "from a large set of reference texts" and assigned codes solely by frequency. Mark Nelson built the dictionary from the input text and assigned codes based on the word.
Author: PEB
More information
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 556464, April 1998.
starshaped 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 1927, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 2026, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
st 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 721, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
stdigraph
(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, Quasiupward planarity, Algorithmica, 32:474506 (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.
Note:
Also called a Steiner vertex. Consider the three points of a triangle. The shortest tree connecting all three, called the Steiner tree, branches out from a fourth point in the middle. That middle point, which was not given initially and must be computed in order to build the shortest tree, is a Steiner point.
From Algorithms and Theory of Computation Handbook, page 1927, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
More information
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 minimumweight tree connecting a designated set of vertices, called terminals, in an undirected, weighted graph or points in a space. The tree may include nonterminals, which are called Steiner vertices or Steiner points.
Specialization (... is a kind of me.)
Euclidean Steiner tree, rectilinear Steiner tree.
Note:
This differs from the minimum spanning tree in that the set of Steiner vertices must be identified. That is, additional vertices may be used. Named for Jakob Steiner.
Some authors distinguish between Steiner trees and minimum Steiner trees.
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.
Note:
Also called a Steiner point.
Consider the three points of a triangle. The shortest tree connecting all three, called the Steiner tree, branches out from a fourth point in the middle. That middle point, which was not given initially and must be computed in order to build the shortest tree, is a Steiner point.
From Algorithms and Theory of Computation Handbook, page 1927, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
Stirling's approximation
(definition)
Definition:
For large values of n, n! ≈ (n/e)^{n} √(2nπ).
Note:
This approximation is taken directly from Stirling's formula.
Author: PEB
More information
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)^{n} √(2nπ) < n! < (n/e)^{n}(1 + 1/(12n1)) √(2nπ).
Note:
After CRC Standard Mathematical Tables, Fourteenth Edition, Samuel M. Selby, ed., page 433, 1965.
Author: PEB
More information
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 twothirds, then the top twothirds, then the bottom twothirds again.
Author: PEB
straightline 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 923, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 It may be more compactly represented in an array by storing entry (i,j) in location (i1)(i2)/2 + j (onebased indexing).
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 It may be more compactly represented in an array by storing entry (i,j) in location n(i1) + j  i(i1)/2  i = (2ni)(i1)/2  i + j (onebased indexing).
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 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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, KnuthMorrisPratt algorithm, BoyerMoore, ZhuTakaoka, quick search, deterministic finite automata string search, KarpRabin, ShiftOr, AhoCorasick, 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, JaroWinkler, Levenshtein distance, string matching with mismatches.
Note:
From Algorithms and Theory of Computation Handbook, page 1318, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC. For large collections that are searched often, it is far faster, though more complicated, to start with an inverted index or a suffix tree.
Author: CRCA
More information
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 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 NPhard.
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.)
depthfirst search.
Note:
If a graph is strongly connected, it has only one strongly connected component. The strongly connected components partition the vertices in the graph. That is, every vertex is in exactly one strongly connected component.
After Robert Caswell (caswer01@cs.uwa.edu.au), 3 May 2002.
Author: PEB
More information
Transitive closure has a link to Esko Nuutila and Eljas SoisalonSoininen, On finding the strongly connected components in a directed graph (PostScript®), Information Processing Letters 49 (1993) 914. The paper has Tarjan's algorithm, references to other algorithms, and two faster algorithms in Pascallike pseudocode.
This has a linear time algorithm for finding strongly connected components: Robert E. Tarjan, Depthfirst search and linear graph algorithms, SIAM Journal on Computing, 1(2):146160, 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 621, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
strongly NPhard
(definition)
Definition:
The complexity class of decision problems which are still NPhard even when all numbers in the input are bounded by some polynomial in the length of the input.
Generalization (I am a kind of ...)
NPhard.
Note:
From Algorithms and Theory of Computation Handbook, page 3418, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science,Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 1435, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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_{1}, v_{2})∈ E' → v_{1}, v_{2}∈ V').
Note:
In general, a subgraph need not have all possible edges. If a subgraph has every possible edge, it is an induced subgraph.
Authors: PEB,AL
subgraph isomorphism
(classic problem)
Definition:
Decide if there is a subgraph of one graph which is isomorphic to another graph.
Note:
This is known to be NPcomplete. After [ATCH99, page 621].
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.
Note:
A substring is contiguous. A subsequence need not be. From Algorithms and Theory of Computation Handbook, page 1317, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
subset
(definition)
Definition:
A set S_{1} is a subset of another set S_{2} if every element in S_{1} is in S_{2}. S_{2} may have exactly the same elements as S_{1}.
Formal Definition: S_{1} ⊆ S_{2} iff ∀ s, s ∈ S_{1} → s ∈ S_{2}.
Specialization (... is a kind of me.)
proper subset, combination.
Note:
If S_{1} is a subset of S_{2}, S_{2} is a superset of S_{1}. A combination is a subset with exactly n elements.
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.
Note:
A substring is contiguous. A subsequence need not be. From Algorithms and Theory of Computation Handbook, pages 1126 and 1221, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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 1126, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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.
Note:
Consider the string "good". In lexicographical order, the suffixes are "d", "good", "od", and "ood". In onebased indexing, the suffix array is [4, 1, 3, 2]. (For convenience, a special character is usually appended to the string.) A suffix array can be constructed in O(n log n) time, where n is the length of the string, by sorting the suffixes, or in O(n) time by building the suffix tree, then doing a depthfirst search. Many other algorithms build suffix arrays quickly. For a comprehensive survey, see Simon J. Puglisi, W. F. Smyth, and Andrew H. Turpin, A taxonomy of suffix array construction algorithms, ACM Computing Surveys, 39(2) Article #4, 2007.
From Algorithms and Theory of Computation Handbook, page 1123, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
More information
Udi Manber and Gene Myers, Suffix Arrays: A New Method for OnLine String Searches, SIAM Journal on Computing 22(5):935948, 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 1126, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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.
Note:
A suffix tree is a Patricia tree corresponding to the suffixes of a given string. A directed acyclic word graph (DAWG) is a more compact form. The newer suffix array has replaced the suffix tree as the data structure of choice in many applications.
Author: SE
More information
Edward M. McCreight, A spaceeconomical suffix tree construction algorithm, Journal of the ACM, 23:262272, 1976. Esko Ukkonen, Online construction of suffix trees, Algorithmica, 14(3):249260, 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
More information
Piotr Indyk, Deterministic Superimposed Coding with Applications to Pattern Matching, Proc. 38th FOCS, pages 127136, IEEE, 1997.
superset
(definition)
Definition:
A set S_{1} is a superset of another set S_{2} if every element in S_{2} is in S_{1}. S_{1} may have elements which are not in S_{2}.
Note:
If S_{1} is a superset of S_{2}, S_{2} is a subset of S_{1}.
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 4740, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.
Author: CRCA
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
