Jump to content

User:Kakurady/Missing science topics from NIST Dictionary of Algorithms and Data Structures

From Wikipedia, the free encyclopedia

This is a copy of Wikipedia:Missing science topics/NIST Dictionary of Algorithms and Data Structures, sorted by the last word; based on the observation that there is a lot of items that are variations on some concept (for example, trees). Hopefully this will group similar things together.

A

[edit]
  1. worst-case minimum access (DADS)
  2. D-adjacent (DADS)
  3. uniform greedy algorithm (DADS)
  4. hybrid algorithm (DADS)
  5. Two Way algorithm (DADS)
  6. string matching on ordered alphabets (DADS)
  7. singularity analysis (DADS)
  8. full array (DADS)
  9. ordered array (DADS)
  10. odd shaped array (DADS)
  11. suffix automaton (DADS)

B

[edit]
  1. reduced basis (DADS)
  2. Turbo-BM (DADS)
  3. border (DADS)
  4. information theoretic bound (DADS)
  5. bridge (DADS)

C

[edit]
  1. discrete p-center (DADS)
  2. secondary clustering (DADS)
  3. coarsening (DADS)
  4. phonetic coding (DADS)
  5. Colussi (DADS)
  6. Reverse Colussi (DADS)
  7. distributional complexity (DADS)
  8. maximally connected component (DADS)
  9. prefix computation (DADS)
  10. parallel prefix computation (DADS)
  11. graph concentration (DADS)
  12. heap condition (DADS)
  13. pipelined divide and conquer (DADS)
  14. list contraction (DADS)
  15. tree contraction (DADS)
  16. optimal cost (DADS)
  17. Apostolico-Crochemore (DADS)
  18. short cutting (DADS)

D

[edit]
  1. two-terminal dag (DADS)
  2. multiway decision (DADS)
  3. regular decomposition (DADS)
  4. hash table delete (DADS)
  5. depoissonization (DADS)
  6. oblivious binary decision diagram (DADS)
  7. KV diagram (DADS)
  8. diet (DADS)
  9. layered digraph (DADS)
  10. reduced digraph (DADS)
  11. recursive doubling (DADS)
  12. grid drawing (DADS)
  13. straight-line drawing (DADS)
  14. orthogonal drawing (DADS)

E

[edit]
  1. free edge (DADS)
  2. saturated edge (DADS)
  3. work-efficient (DADS)
  4. pattern element (DADS)
  5. phonetic encoding (DADS)
  6. string matching with errors (DADS)
  7. EXCELL (DADS)
  8. moderately exponential (DADS)

F

[edit]
  1. Reverse Factor (DADS)
  2. Turbo Reverse Factor (DADS)
  3. fathoming (DADS)
  4. two-level grid file (DADS)
  5. multilayer grid file (DADS)
  6. twin grid file (DADS)
  7. R-file (DADS)
  8. Malhotra-Kumar-Maheshwari blocking flow (DADS)
  9. integer multi-commodity flow (DADS)
  10. DFS forest (DADS)

G

[edit]
  1. Galil-Giancarlo (DADS)
  2. layered graph (DADS)
  3. rough graph (DADS)
  4. triconnected graph (DADS)
  5. performance guarantee (DADS)

H

[edit]
  1. order preserving hash (DADS)
  2. dynamic hashing (DADS)
  3. incremental hashing (DADS)
  4. 2-left hashing (DADS)
  5. always-go-left hashing (DADS)
  6. multiplicative hashing (DADS)
  7. optimal hashing (DADS)
  8. order preserving minimal perfect hashing (DADS)
  9. PLOP-hashing (DADS)
  10. uniform hashing (DADS)
  11. simple uniform hashing (DADS)
  12. virtual hashing (DADS)
  13. k-ary heap (DADS)
  14. build-heap (DADS)
  15. hash heap (DADS)
  16. shadow heap (DADS)
  17. weak-heap (DADS)
  18. frequency count heuristic (DADS)
  19. self-organizing heuristic (DADS)

I

[edit]
  1. block addressing index (DADS)
  2. fully inverted index (DADS)
  3. shadow merge insert (DADS)

J

[edit]
  1. pointer jumping (DADS)

L

[edit]
  1. ordered linked list (DADS)
  2. prop list (DADS)
  3. orthogonal lists (DADS)

M

[edit]
  1. parallel random-access machine (DADS)
  2. visibility map (DADS)
  3. horizontal visibility map (DADS)
  4. vertical visibility map (DADS)
  5. K-dominant match (DADS)
  6. phonetic string match (DADS)
  7. Crochemore-Perrin string matching (DADS)
  8. uniform matrix (DADS)
  9. ideal merge (DADS)
  10. multiway merge (DADS)
  11. balanced multiway merge (DADS)
  12. nonbalanced merge (DADS)
  13. optimal merge (DADS)
  14. polyphase merge (DADS)
  15. optimal polyphase merge (DADS)
  16. shadow merge (DADS)
  17. simple merge (DADS)
  18. k-way merge (DADS)
  19. double metaphone (DADS)
  20. division method (DADS)
  21. fixed-grid method (DADS)
  22. multiplication method (DADS)
  23. optimal mismatch (DADS)
  24. string matching with mismatches (DADS)
  25. mode (DADS)
  26. select mode (DADS)
  27. work-depth model (DADS)
  28. multiprocessor model (DADS)
  29. cell probe model (DADS)
  30. MODIFIND (DADS)
  31. move (DADS)
  32. multiprefix (DADS)

N

[edit]
  1. Not So Naive (DADS)
  2. nonterminal node (DADS)

O

[edit]
  1. occurrence (DADS)
  2. Shift-Or (DADS)
  3. heap ordered (DADS)
  4. priority queue ordering (DADS)

P

[edit]
  1. strip packing (DADS)
  2. PAM (DADS)
  3. planarization (DADS)
  4. poissonization (DADS)
  5. integer polyhedron (DADS)
  6. Morris-Pratt (DADS)
  7. work-preserving (DADS)
  8. partially decidable problem (DADS)
  9. forest editing problem (DADS)
  10. string editing problem (DADS)
  11. tree editing problem (DADS)
  12. fully dynamic graph problem (DADS)
  13. partially dynamic graph problem (DADS)
  14. matrix-chain multiplication problem (DADS)
  15. geometric optimization problem (DADS)
  16. critical path problem (DADS)
  17. decomposable searching problem (DADS)
  18. path system problem (DADS)
  19. optimal triangulation problem (DADS)
  20. optimal polygon triangulation problem (DADS)
  21. linear product (DADS)
  22. mixed integer linear program (DADS)

Q

[edit]
  1. qmsort (DADS)
  2. linear quadtree (DADS)
  3. binary priority queue (DADS)
  4. monotone priority queue (DADS)
  5. three-way radix quicksort (DADS)

R

[edit]
  1. performance ratio (DADS)
  2. Ratcliff/Obershelp pattern recognition (DADS)
  3. NC many-one reducibility (DADS)
  4. boundary-based representation (DADS)
  5. interior-based representation (DADS)
  6. rescalable (DADS)
  7. double left rotation (DADS)
  8. double right rotation (DADS)

S

[edit]
  1. 2-left scheme (DADS)
  2. d-random scheme (DADS)
  3. edit script (DADS)
  4. KmpSkip Search (DADS)
  5. interpolation-sequential search (DADS)
  6. self-organizing sequential search (DADS)
  7. transpose sequential search (DADS)
  8. string similarity search (DADS)
  9. parametric searching (DADS)
  10. Galil-Seiferas (DADS)
  11. Randomized-Select (DADS)
  12. slope selection (DADS)
  13. probe sequence (DADS)
  14. Maximal Shift (DADS)
  15. shortcutting (DADS)
  16. fractional solution (DADS)
  17. brick sort (DADS)
  18. merge exchange sort (DADS)
  19. flash sort (DADS)
  20. weak-heap sort (DADS)
  21. decreasing increment sort (DADS)
  22. diminishing increment sort (DADS)
  23. cascade merge sort (DADS)
  24. nonbalanced merge sort (DADS)
  25. oscillating merge sort (DADS)
  26. optimal polyphase merge sort (DADS)
  27. k-way merge sort (DADS)
  28. p-way merge sort (DADS)
  29. three-way merge sort (DADS)
  30. two-way merge sort (DADS)
  31. balanced two-way merge sort (DADS)
  32. linear probing sort (DADS)
  33. qm sort (DADS)
  34. top-down radix sort (DADS)
  35. external radix sort (DADS)
  36. restricted universe sort (DADS)
  37. sparsification (DADS)
  38. next state (DADS)
  39. spiral storage (DADS)
  40. push-down store (DADS)
  41. end-of-string (DADS)
  42. external memory data structure (DADS)
  43. passive data structure (DADS)
  44. heaviest common subsequence (DADS)
  45. prefix sums (DADS)
  46. shortest common superstring (DADS)
  47. quadtree complexity theorem (DADS)

T

[edit]
  1. cutting theorem (DADS)
  2. subadditive ergodic theorem (DADS)
  3. simulation theorem (DADS)
  4. pushdown transducer (DADS)
  5. Turing transducer (DADS)
  6. level-order traversal (DADS)
  7. perfect k-ary tree (DADS)
  8. k-d-B-tree (DADS)
  9. universal B-tree (DADS)
  10. BB(α) tree (DADS)
  11. BD-tree (DADS)
  12. LCRS binary tree (DADS)
  13. buddy tree (DADS)
  14. BV-tree (DADS)
  15. cell tree (DADS)
  16. complete tree (DADS)
  17. discrete interval encoding tree (DADS)
  18. finitary tree (DADS)
  19. GBD-tree (DADS)
  20. hB-tree (DADS)
  21. multiway tree (DADS)
  22. balanced multiway tree (DADS)
  23. P-tree (DADS)
  24. recursion tree (DADS)
  25. digital search tree (DADS)
  26. multiway search tree (DADS)
  27. skd-tree (DADS)
  28. minimal code spanning tree (DADS)
  29. multi suffix tree (DADS)
  30. threaded tree (DADS)
  31. topology tree (DADS)
  32. binary tree representation of trees (DADS)
  33. elastic-bucket trie (DADS)
  34. compact trie (DADS)
  35. quad trie (DADS)
  36. tripartition (DADS)

V

[edit]
  1. free vertex (DADS)

Source code for generating this list (section titles are manually added)

[edit]
import re

filename = "/home/nekoyasha/Documents/nistdict.txt"
output_filename = "/home/nekoyasha/Documents/nistdict-suffix.txt"

def replfunc(match):
    pass

terms = [];

def sortkey(string):
    words = string[1].replace("-", " ").lower().split(" ")
    reversed_words = [x for x in words]
    reversed_words.reverse()
    return reversed_words

for line in open(filename):
    m = re.match(r"# \[\[(.*)\]\] \(\[(.*) .*\]\)", line);
    if m is not None:
        terms.append(m.group(0, 1, 2));

terms.sort(key=sortkey)

with open(output_filename, "w") as f:
    for term in terms:
        print (term[0])
        f.write(term[0])
        f.write("\n")