﻿ Algorithms and Data Structures Glossary (Starting with "S")    Home Free Glossaries Free Dictionaries Post Your Translation Job! Free Articles Jobs for Translators  #### Algorithms and Data Structures Glossary(Starting with "S")

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

paul . black [at] nist . gov

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

 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

### 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 kth element
selection sort
select kth 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
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
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
subgraph
subgraph isomorphism
sublinear time algorithm
subsequence
subset
substring
subtree
suffix
suffix array
suffix automaton
suffix tree
superimposed code
superset
supersink
supersource
symmetric
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.

Note: The graph must be a binary graph, that is, nodes have out-degree 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 depth-first 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

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.

Note: It is called "secant search" because it uses the secant of the function at two successive points to approximate the derivative in the Newton-Raphson formula.

To find a key k in an array v with indexes from 0 to n-1, begin with x0 = 0, x1 = n-1, and i = 1. Compute the next position with
xi+1 = xi - (v[xi]-k) * (xi - xi-1)/(v[xi] - v[xi-1]).
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 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 kth 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 kth element of the low side. Otherwise Select the k-ith element of the high side.

Note: After [CLR90, p 190]. Sometimes called "quick select".

The number of comparisons to select the ith smallest of n numbers is n+min(i,n-i)+o(n) or Θ(n).

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 kth smallest element of A and partition the array such that A, ..., 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 kth 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.

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 kth element

(classic problem)

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

Also known as selection problem, find kth least element, kth 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.)

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 74-77]

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
where S is a set and u and v are elements.

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

1. isEmpty(new()) = true

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 Ui=1 ci = Ui=1 Si.

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

(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

(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

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

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 2k+1, . . ., 9, 5, 3, 1 with the first increment no more than N/3.

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.

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 B-tree 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.

#### 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.

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@enitiaa-nantes.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 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.

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

#### 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 ...)

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 kth 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.

Note: Any sorting algorithm can be made stable by appending the original position to the key. When otherwise-equal 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

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.

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

#### 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.

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 2-dimensional array in memory?

A transversal of the mapped points in their linear order yields a space-filling curve.

There is a good survey on pages 167-169 of
Hanan Samet, Object-Based and Image-Based Object Representation, ACM Computing Surveys, 36(2):159-217, June 2004. The article describes several methods and reviews their properties:

• row order (row major)
• row-prime order
• Morton order
• Peano-Hilbert order
• Cantor-diagonal 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 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.

Note: A directed graph can have at most n(n-1) edges, where n is the number of vertices. An undirected graph can have at most n(n-1)/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 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.

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= S-h(k) +h(k), is computed to find the final slot, dx , where d>1 is called the growth factor. To increase the number of slots, increase S to S' and rehash any keys from dS to dS' -1.

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

Note: Choosing d=2 and S=log2N, the number of slots, every expansion retires one slot and creates two new slots. Since slots in use go from dS to dS+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.	 `
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	 `
`               __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 hand-held calculators, square root, sine, cosine, and other transcendental functions are calculated with sophisticated functions, such as Taylor series, CORDIC, or Newton-Raphson 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 otherwise-equal 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: 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
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.

1. isEmpty(new()) = true
2. 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" (*).

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

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.

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

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.

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

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

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/(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---
10--
195-

It may be more compactly represented in an array by storing entry (i,j) in location (i-1)(i-2)/2 + j (one-based 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
j
i -776
--11
---8
----

It may be more compactly represented in an array by storing entry (i,j) in location n(i-1) + j - i(i-1)/2 - i = (2n-i)(i-1)/2 - i + j (one-based 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 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.

Note: From Algorithms and Theory of Computation Handbook, page 13-18, 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: 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.

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

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

(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 ∧ ( (v1, v2)∈ E' → v1, v2∈ 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 NP-complete. After [ATCH99, page 6-21].

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

#### subset

(definition)

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

Formal Definition: S1 ⊆ S2 iff ∀ s, s ∈ S1 → s ∈ S2.

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

Note: If S1 is a subset of S2, S2 is a superset of S1.

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 11-26 and 12-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

#### 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.

Note: Consider the string "good". In lexicographical order, the suffixes are "d", "good", "od", and "ood". In one-based 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 depth-first 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 11-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

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.

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

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 S1 is a superset of another set S2 if every element in S2 is in S1. S1 may have elements which are not in S2.

Note: If S1 is a superset of S2, S2 is a subset of S1.

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

 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

Published - April 2009

Find free glossaries at TranslationDirectory.com

Find free dictionaries at TranslationDirectory.com

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

 Use More Glossaries Use Free Dictionaries Use Free Translators Submit Your Glossary Read Translation Articles Register Translation Agency Submit Your Resume Obtain Translation Jobs Subscribe to Free Newsletter Buy Database of Translators Obtain Blacklisted Agencies Vote in Polls for Translators Read News for Translators Advertise Here Read our FAQ Read Testimonials Use Site Map       