Wikipedia:Missing science topics/NIST Dictionary of Algorithms and Data Structures

Needs updating, new entries have appeared in the source!

This is a dictionary of algorithms, algorithmic techniques, data structures, archetypical problems, and related definitions. Algorithms include common functions, such as Ackermann's function. Problems include traveling salesman and Byzantine generals. Some entries have links to implementations and more information.

• This is a unified index of all terms in the Dictionary. For instance, TSP is listed under "traveling salesman" (one "l" in "traveling"), the American spelling, and "travelling salesman" (two l's), the British spelling. Other variants are "quick sort" and "quicksort", "sort" and "sorting algorithm", and "doubly linked list" and "two-way list". Therefore, please disambiguate by creating a redirect, if possible.

• Some terms with a leading variable, such as n-way, m-dimensional, or p-branching, are under k-.

• Some definitions are copyright CRC Press, such as depoissonization. (These enties are clearly marked.) All others are public domain.

• The articles at the DADS contain some good quality references, external links (and see also section.)

• Cite with {{DADS|Ackermann's function|ackermann}}

 This article incorporates public domain material from Paul E. Black. "Ackermann's function". Dictionary of Algorithms and Data Structures. NIST.

Note: Some of these items are not defined at DADS but instead at http://www-igm.univ-mlv.fr/~lecroq/string/ - see Exact String Matching Algorithms

List

1. always-go-left hashing (DADS) (2-left hashing)
2. Apostolico-Crochemore (DADS)
3. balanced multiway merge (DADS)
4. balanced multiway tree (DADS)
5. balanced two-way merge sort (DADS)
6. BB(α) tree (DADS)
7. BD-tree (DADS)
8. binary priority queue (DADS)
9. binary tree representation of trees (DADS)
10. block addressing index (DADS)
11. border (DADS) Suitable for a glossary entry, highly relevant to string searching, esp. BMH variants
12. boundary-based representation (DADS)
13. bridge (DADS)
14. buddy tree (DADS)
15. build-heap (DADS)
16. cell probe model (DADS)
17. cell tree (DADS)
18. coarsening (DADS)
19. Colussi (DADS)
20. compact trie (DADS)
21. complete tree (DADS)
22. critical path problem (DADS)
23. Crochemore-Perrin string matching (DADS)
24. cutting theorem (DADS)
25. D-adjacent (DADS)
26. decomposable searching problem (DADS)
27. decreasing increment sort (DADS)
28. depoissonization (DADS)
29. DFS forest (DADS)
30. diet (DADS) Same as Discrete interval encoding tree.
31. digital search tree (DADS)
32. diminishing increment sort (DADS)
33. discrete interval encoding tree (DADS)
34. discrete p-center (DADS)
35. distributional complexity (DADS)
36. division method (DADS)
37. double left rotation (DADS) redirected to Left rotation - No defn. at DADS
38. double metaphone (DADS)
39. double right rotation (DADS) redirected to Right rotation - No defn. at DADS
40. d-random scheme (DADS)
41. dynamic hashing (DADS)
42. edit script (DADS)
43. elastic-bucket trie (DADS)
44. end-of-string (DADS)
45. EXCELL (DADS)
46. external memory data structure (DADS)
47. external radix sort (DADS)
48. fathoming (DADS)
49. finitary tree (DADS)
50. fixed-grid method (DADS)
51. flash sort (DADS)
52. forest editing problem (DADS)
53. fractional solution (DADS)
54. free edge (DADS)
55. free vertex (DADS)
56. frequency count heuristic (DADS)
57. full array (DADS)
58. fully dynamic graph problem (DADS)
59. fully inverted index (DADS)
60. Galil-Giancarlo (DADS)
61. Galil-Seiferas (DADS)
62. GBD-tree (DADS)
63. geometric optimization problem (DADS)
64. graph concentration (DADS)
65. grid drawing (DADS)
66. hash heap (DADS)
67. hash table delete (DADS)
68. hB-tree (DADS)
69. heap condition (DADS)
70. heap ordered (DADS)
71. heaviest common subsequence (DADS)
72. horizontal visibility map (DADS)
73. ideal merge (DADS)
74. incremental hashing (DADS)
75. information theoretic bound (DADS)
76. integer multi-commodity flow (DADS)
77. integer polyhedron (DADS)
78. interior-based representation (DADS)
79. interpolation-sequential search (DADS)
80. k-ary heap (DADS)
81. k-d-B-tree (DADS)
82. K-dominant match (DADS)
83. KmpSkip Search (DADS)
84. KV diagram (DADS)
85. k-way merge (DADS)
86. k-way merge sort (DADS)
87. layered digraph (DADS)
88. layered graph (DADS)
89. LCRS binary tree (DADS)
90. level-order traversal (DADS)
91. linear probing sort (DADS)
92. linear product (DADS)
93. linear quadtree (DADS)
94. list contraction (DADS)
95. Malhotra-Kumar-Maheshwari blocking flow (DADS)
96. matrix-chain multiplication problem (DADS)
97. maximally connected component (DADS)
98. Maximal Shift (DADS)
99. merge exchange sort (DADS)
100. minimal code spanning tree (DADS)
101. mixed integer linear program (DADS)
102. mode (DADS)
103. moderately exponential (DADS)
104. MODIFIND (DADS)
105. Morris-Pratt (DADS)
106. move (DADS)
107. multilayer grid file (DADS)
108. multiplication method (DADS)
109. multiplicative hashing (DADS)
110. multiprefix (DADS)
111. multiprocessor model (DADS)
112. multi suffix tree (DADS)
113. multiway decision (DADS)
114. multiway merge (DADS)
115. multiway search tree (DADS)
116. NC many-one reducibility (DADS)
117. next state (DADS)
118. nonbalanced merge (DADS)
119. nonbalanced merge sort (DADS)
120. nonterminal node (DADS)
121. Not So Naive (DADS)
122. oblivious binary decision diagram (DADS)
123. occurrence (DADS)
124. odd shaped array (DADS)
125. optimal cost (DADS)
126. optimal hashing (DADS)
127. optimal merge (DADS)
128. optimal mismatch (DADS)
129. optimal polygon triangulation problem (DADS)
130. optimal polyphase merge (DADS)
131. optimal polyphase merge sort (DADS)
132. optimal triangulation problem (DADS)
133. ordered array (DADS)
134. ordered linked list (DADS)
135. order preserving hash (DADS)
136. order preserving minimal perfect hashing (DADS)
137. orthogonal drawing (DADS)
138. orthogonal lists (DADS)
139. PAM (DADS)
140. parallel prefix computation (DADS)
141. parametric searching (DADS)
142. partially decidable problem (DADS)
143. partially dynamic graph problem (DADS)
144. path system problem (DADS)
145. pattern element (DADS)
146. perfect k-ary tree (DADS)
147. performance guarantee (DADS)
148. performance ratio (DADS)
149. pipelined divide and conquer (DADS)
150. planarization (DADS)
151. PLOP-hashing (DADS)
152. poissonization (DADS)
153. polyphase merge (DADS)
154. prefix computation (DADS)
155. priority queue ordering (DADS)
156. probe sequence (DADS)
157. prop list (DADS)
158. push-down store (DADS)
159. p-way merge sort (DADS)
160. qmsort (DADS)
161. qm sort (DADS)
162. quadtree complexity theorem (DADS)
163. quad trie (DADS)
164. Randomized-Select (DADS)
165. Ratcliff/Obershelp pattern recognition (DADS)
166. recursion tree (DADS)
167. reduced basis (DADS)
168. reduced digraph (DADS)
169. regular decomposition (DADS)
170. rescalable (DADS)
171. restricted universe sort (DADS)
172. Reverse Colussi (DADS)
173. Reverse Factor (DADS)
174. R-file (DADS)
175. rough graph (DADS)
176. saturated edge (DADS)
177. secondary clustering (DADS)
178. select mode (DADS)
179. self-organizing sequential search (DADS)
180. shadow merge (DADS)
181. shadow merge insert (DADS)
182. shortcutting (DADS)
183. short cutting (DADS)
184. shortest common superstring (DADS)
185. simple merge (DADS)
186. simple uniform hashing (DADS)
187. simulation theorem (DADS)
188. singularity analysis (DADS)
189. skd-tree (DADS)
190. sparsification (DADS)
191. spiral storage (DADS)
192. straight-line drawing (DADS)
193. string editing problem (DADS)
194. string matching on ordered alphabets (DADS)
195. string matching with errors (DADS)
196. string matching with mismatches (DADS)
197. string similarity search (DADS)
198. strip packing (DADS)
199. subadditive ergodic theorem (DADS)
200. threaded tree (DADS)
201. three-way merge sort (DADS)
202. top-down radix sort (DADS)
203. topology tree (DADS)
204. transpose sequential search (DADS)
205. tree editing problem (DADS)
206. triconnected graph (DADS)
207. tripartition (DADS)
208. Turbo-BM (DADS)
209. Turbo Reverse Factor (DADS)
210. Turing transducer (DADS)
211. twin grid file (DADS)
212. 2-left hashing (DADS)
213. 2-left scheme (DADS)
214. two-level grid file (DADS)
215. two-terminal dag (DADS)
216. Two Way algorithm (DADS)
217. two-way merge sort (DADS)
218. uniform greedy algorithm (DADS)
219. uniform hashing (DADS)
220. uniform matrix (DADS)
221. universal B-tree (DADS)
222. vertical visibility map (DADS)
223. virtual hashing (DADS)
224. visibility map (DADS)
225. weak-heap (DADS)
226. work-efficient (DADS)
227. work-preserving (DADS)
228. worst-case minimum access (DADS)