| Related sites for http://www.nist.gov/dads/ |
| Resources_for_the_Analysis_of_Algorithms Links to papers, conferences and other sites, maintained by Helmut Prodinger. | | Self-stabilizing_Algorithms A project to create tools for developing and testing self-stabilizing algorithms. | | Softpanorama_Virtual_Library Section on Algorithms and Data Structures. A compilation of links. | | Sourcebank_-_Computer_Science_-_Algorithms A collection of source code for various topics. | | Stony_Brook_Algorithm_Repository This is a collection of implementations for 75 fundamental algorithms problems, including data structures, numerical and combinatorial algorithms,graph algorithms, and computational geometry. Implemen | | Tree_Automata_Techniques_and_Applications An evolving web text in PostScript and PDF, with related software. | | Web_Data_Structures_and_Algorithms Lecture notes and links for a course by Godfried Toussaint. | | European_Multimedia_Forum_(EMF) The main European trade association promoting the competitiveness of the digital media industries in the global market place. | | Issues_in_Multimedia_Authoring Information about authoring metaphors, content design, visual design and technical design. | | Media_Mall Includes digital media related news, articles and reviews, covering software, hardware and general multimedia. | | Multimedia_Authoring_Guidelines Recommendations on how to use multimedia for teaching and learning, taking a project management approach to multimedia development. | | Multimedia_Authoring_Web Links and searchable resources for multimedia authors and developers. Site has ceased being updated so acts now as an archive of links. | | The_Multimedia_Library_Gazette Collection of articles, resources, and media for developers. | | Multimedia/Hypermedia Gallery of multimedia content. Features ASCII art, audio, background images, clipart, maps, MOD soundtracks, and Quicktime video clips. | | Scala_Multimedia_Directory Index to various types of multimedia resources, including articles, software, authorities, samples. | | Altair32 An open source Altair emulator for Windows. | | blueMSX An open source SVI318/328, MSX1, MSX2, MSX2+, and Turbo-R emulator for Windows. | | Chip-8_Emulator A freeware Chip-8 emulator for DOS. | | cinc An open source Bell Labs cardiac emulator for Linux and Windows/Cygwin. | | CP/M An open source CP/M-80 ver2.2 emulator for MacOS. | | Desktop_Cyber An open source CDC (Control Data Corporation) Cyber 6x00, 7x or 17x type mainframe emulator for Windows or Unix. | | Emu28 An open source HP18C/28C emulator for Windows. | | Emu51 An open source 8051 emulator for Linux and Windows. | | Emula3 Contains emulators for many different computers and calculators/PDAs for many different platforms. [English/Italian] | | Emuviews Great emulation page maintained by JoseQ, maker of the famous Rumor Mill, many downloads, great layout - some hosted sites. | | Evenson_Consulting_Services\'_SWTPc_6800/6809_Emulator Windows 9x/NT GUI emulation of SWTPc 6800 and 6809 systems. A Simulated Machine Environment (SME) emulation plus .dsk file downloads. | | Flexemu An open source EurocomII/V7 emulator for Linux and Windows. | | FunnyMu A freeware Creativision, Funvision, and Whizzard emulator for Linux/SDL. | | GXemul An open source MIPS machine emulator for Linux. | | HiRISC_Simulator A freeware emulator for Windows of a system designed specifically for the Applied Systems Programming course at the University of Akron. | | James_the_Animal_Tamer\'s_Emulators Freeware APF, Aquarius, Exidy Sorcerer, Interact Family Computer, MC-10, NEC PC-6001A, Panasonic Personal Computer, and TRS-80 emulators for Windows. | | Japanese_Computer_Emulation_Centre A site dedicated to the emulation of Japanese Machines including X68000, PC6001, PC88, PC98, MSX 1/2/R, Sharp MZ, Sharp X1, Fujitsu FM7, and Fujitsu FM Towns. | | KCemu An open source emulator of the KC85 homecomputer series for Linux and Windows. | | mic1 A Java-based simulator which implements the Mic-1 microarchitecture described in Chapter 4 of Andrew S. Tanenbaum, Structured Computer Organization, Fourth Edition. [Open source, GPL] | | Newbrain_Emulator_Pro A freeware Grundy NewBrain emulator for Windows written in Delphi. | | PearPC An open source PowerPC emulator for Unix and Windows. | | Project8080 Covers the development of a Heathkit H8 emulator on Macintosh. | | SIMH An open source collection of emulators for Windows of historical computers, including GRI-909, HP 2116/2100/21MX, IBM 1401/1620/1130/System 3, PDP-1/4/7-11/15/VAX. Also provides software kits, system | | Solace An open source Sol-20 emulator for Windows. | | SPRINT A freeware Sprinter emulator for Linux/i386 and Windows. |
|
Dictionary of Algorithms and Data Structures Dictionary of Algorithms and Data Structures This web site is hosted in part by theSoftware and Systems Division,Information Technology Laboratory.This is a dictionary of algorithms, algorithmic techniques, data structures, archetypal problems, and related definitions.Algorithms include common functions, such asAckermann's function.Problems include traveling salesman andByzantine generals.Some entries have links to implementationsand more information.Index pages list entries by area and bytype.The two-levelindex has a total download 1/20 as big as this page.Don't use this site to cheat. Teachers,contact us if we can help.To define or correct terms, please contactPaul E. Black.We need help in automata theory, combinatorics, parallel or randomizedalgorithms, heuristics, and quantum computing.We do not include algorithms particular to business data processing,communications, operating systems or distributed algorithms,programming languages, AI, graphics, or numerical analysis: it istough enough covering "general" algorithms and data structures.However, if you want to tackle one of these areas,we'll consider including them.Some terms with a leading variable, such as n-way,m-dimensional, or p-branching, are underk-.You may find terms dealing with hardware, the computerindustry, slang, etc., in theFreeOn-Line Dictionary Of Computing or inAGlossary of Computer Oriented Abbreviations and Acronyms.To look up words or phrases, enter them in the box, then click thebutton. Web DADS ABCDEFGHIJKLMNOPQRSTUVWXYZα: see inverse Ackermann functionωΩρ-approximation algorithm ΘAabsolute performance guaranteeabstract data type(a,b)-treeaccepting stateAckermann's functionactive data structureacyclic directed graph: see directed acyclic graphacyclic graphadaptive heap sortadaptive Huffman codingadaptive k-d treeadaptive sortaddress-calculation sortadjacency-list representationadjacency-matrix representationadjacentadmissible vertexADT: see abstract data typeadversaryAho-Corasickalgorithmalgorithm BSTWalgorithm FGKalgorithmically solvable: see decidable problemall pairs shortest pathall simple pathsalphabetAlpha Skip Search algorithmalternating pathalternating Turing machinealternationAmerican flag sortamortized costancestorandANSIantichainantisymmetricApostolico-CrochemoreApostolico-Giancarlo algorithmapproximate string matching: see string matching with errorsapproximation algorithmarborescencearc: see edgearithmetic codingarrayarray indexarray mergingarray searcharticulation point: see cut vertexassignment problemassociation list: see dictionaryassociativeassociative arrayasymptotically tight boundasymptotic boundasymptotic lower boundasymptotic space complexityasymptotic time complexityasymptotic upper boundaugmenting pathautomatonaverage caseaverage-case costAVL treeaxiomatic semanticsBbacktrackingbagbalancebalanced binary search treebalanced binary treebalanced k-way merge sortbalanced merge sortbalanced multiway mergebalanced multiway tree: see B-treebalanced quicksortbalanced treebalanced two-way merge sortBANG fileBatcher sort: see bitonic sortBaum Welch algorithmBB(α) treeBBP algorithmBDDBD-treeBellman-Ford algorithmBenford's lawbest casebest-case costbest-first searchbiconnected componentbiconnected graphbidirectional bubble sortbig-O notationbinary functionbinary GCDbinary heapbinary insertion sortbinary knapsack problem: see knapsack problembinary priority queuebinary relationbinary searchbinary search treebinary treebinary tree representation of treesbingo sortbinomial heapbinomial treebin packing problembin sort: see bucket sortbintreebipartite graphbipartite matchingbisectorbitonic sortbit vectorBk treeblind sortblind trieblockblock addressing indexblocking flowblock search: see jump searchBloom filterblossombogosortbooleanboolean expressionboolean functionborderBoruvka's algorithmbottleneck traveling salesmanbottom-up tree automatonboundary-based representationbounded error probability in polynomial time: see BPPbounded queuebounded stackBoyer-MooreBoyer-Moore-Horspoolbozo sortB+-treeBPPBradford's lawbranch and boundbreadth-first searchBresenham's algorithmbrick sortbridgeBritish Museum techniquebrute forcebrute force string searchbrute force string search with mismatchesBSP-treeB*-treeB-treebubble sortbucketbucket arraybucketing methodbucket sortbucket triebuddy systembuddy treebuild-heapBurrows-Wheeler transformbusy beaverBV-treeBWT: see Burrows-Wheeler transformByzantine generalsCcactus stackCalculus of Communicating Systemscalendar queuecandidate consistency testingcandidate verificationcanonical complexity classcapacitated facility locationcapacitycapacity constraintcartesian tree: see randomized binary search treecascade merge sortCaverphoneCCScell probe modelcell treecellular automatoncentroidcertificatechainchainingchildChinese postman problemChinese remainder theoremChristofides algorithmChristofides heuristic: see Christofides algorithmchromatic indexchromatic numbercircuitcircuit complexitycircuit value problemcircular listcircular queuecliqueclique problemclusteringclustering freecoalesced chainingcoarseningcocktail shaker sort: see bidirectional bubble sortcodewordcoding treeCollatz problemcollective recursioncollisioncollision resolution schemeColussicombinationcomb sortCommentz-WalterCommunicating Sequential Processescommutativecompact DAWGcompact triecomparison sortcompetitive analysiscompetitive ratiocomplementcomplete binary treecomplete graphcompletely connected graphcomplete treecomplexitycomplexity classcomputableconcave functionconcurrent flowconcurrent read, concurrent writeconcurrent read, exclusive writeconfluently persistent data structureconjunctionconnected componentsconnected graphconstant functioncontinuous knapsack problem: see fractional knapsack problemCook reductionCook's theoremCORDICcounting sortcoveringCRC: see cyclic redundancy checkCRCW: see concurrent read, concurrent writeCREW: see concurrent read, exclusive writecritical path problemCSPCTLcube rootcuckoo hashingcutcutting planecutting stock problemcutting theoremcut vertexcyclecyclic redundancy checkDD-adjacentDAG: see directed acyclic graphDAG shortest pathsdata structureDAWG: see directed acyclic word graphdecidable languagedecidable problemdecimation: see prune and searchdecision problemdecomposable searching problemdegreedense graphdepoissonizationdepthdepth-first searchdequederangementdescendantdeterministicdeterministic algorithmdeterministic finite automata string searchdeterministic finite automaton: see deterministic finite state machinedeterministic finite state machinedeterministic finite tree automatondeterministic pushdown automatondeterministic tree automatonDeutsch-Jozsa algorithmDFA: see deterministic finite state machineDFS: see depth-first searchDFS forestDFTA: see deterministic finite tree automatondiagonalizationdiameterdichotomic searchdictionarydiet: see discrete interval encoding treedifferencedigital search treedigital treedigraph: see directed graphDijkstra's algorithmdiminishing increment sortdining philosophersdirect chainingdirected acyclic graphdirected acyclic word graphdirected graphdiscrete interval encoding treediscrete p-centerdisjoint setdisjunctiondistributional complexitydistribution sortdistributive partitioning sortdivide and conquerdivide and marriage before conquestdivision methoddomaindominance tree sortdon't careDoomsday ruledouble-direction bubble sort: see bidirectional bubble sortdouble-ended priority queuedouble hashingdouble left rotationdouble metaphonedouble right rotationdoubly-chained tree: see binary tree representation of treesdoubly-ended queue: see dequedoubly linked listDPDA: see deterministic pushdown automatonD-treedualdual linear programDutch national flagdyadic tree: see binary treedynamicdynamic arraydynamic hashingdynamic Huffman coding: see adaptive Huffman codingdynamic programmingdynamization transformationEeasy split, hard mergeedgeedge coloringedge connectivityedge crossingedge-weighted graph: see weighted graphedit distance: see Levenshtein distanceedit operationedit scriptefficiency8 queenselastic-bucket trieelement uniquenessend-of-stringenfiladeERCW: see exclusive read, concurrent writeEREW: see exclusive read, exclusive writeEuclidean algorithm: see Euclid's algorithmEuclidean distanceEuclidean Steiner treeEuclidean traveling salesman problemEuclid's algorithmEuler cycleEulerian graphEulerian path: see Euler cycleexact string matching: see string matchingEXCELLexchange sort: see bubble sortexclusive or: see xorexclusive read, concurrent writeexclusive read, exclusive writeexhaustive searchexistential stateexpandable hashingexpander graphexponentialextended binary treeextended Euclid's algorithmextended k-d treeextendible hashingexternal chaining: see separate chainingexternal indexexternal memory algorithmexternal memory data structureexternal mergeexternal node: see leafexternal quicksortexternal radix sortexternal sortextrapolation search: see interpolation searchextremalextreme pointFfacility locationfactor: see substringfactorialfast fourier transformfathomingfeasible regionfeasible solutionfeedback edge setfeedback vertex setFerguson-Forcade algorithmFFT: see fast fourier transformFibonaccian searchFibonacci heapFibonacci numberFibonacci treeFIFO: see queuefilial-heir chain: see binary tree representation of treesFindfind kth least element: see select kth elementfinitary treefinite Fourier transformfinite state automaton: see finite state machinefinite state machinefinite state machine minimizationfinite state transducerfirst child-next sibling binary tree: see binary tree representation of treesfirst come, first servedfirst-in, first-outFisher-Yates shufflefixed-grid methodflash sortflowflow conservationflow functionflow networkFloyd-Warshall algorithmFord-Bellman: see Bellman-Ford algorithmFord-Fulkerson methodforestforest editing problemformal language: see languageformal methodsformal verificationforward indexfractional knapsack problemfractional solutionfree edgefree treefree vertexfrequency count heuristicfull arrayfull binary treefull inverted indexfully dynamic graph problemfully persistent data structurefully polynomial approximation schemefunctionfunctional data structure: see active data structureGGalil-GiancarloGalil-Seiferasgamma functionGBD-treeGCD: see greatest common divisorgeometric optimization problemglobal optimumgnome sortgraphgraph coloringgraph concentrationgraph drawinggraph isomorphismgraph partitionGray codegreatest common divisorgreedy algorithmgreedy heuristicgrid drawinggrid fileGrover's algorithmHhalting problemHamiltonian cycleHamiltonian pathHamming distancehard split, easy mergehashbelthash functionhash heaphash tablehash table deleteHausdorff distancehB-treeheadheapheapifyheap propertyheapsortheaviest common subsequence: see longest common subsequenceheightheight-balanced binary search treeheight-balanced treeheuristichidden Markov modelhighest common factor: see greatest common divisorhistogram sortHMM: see hidden Markov modelhomeomorphichorizontal visibility mapHorner's ruleHorspool: see Boyer-Moore-HorspoolhsadeltaHuffman codinghuge sparse arrayHungarian algorithm: see Munkres' assignment algorithmhybrid algorithmhyperedgehypergraphIideal mergeimplicationimpliesinclusion-exclusion principleinclusive or: see orincompressible stringincremental hashing: see linear hashingin-degreeindependent setindex fileinformation theoretic boundin-order traversalin-place sortinsertion sortinteger linear programinteger multi-commodity flowinteger polyhedroninteractive proof systeminterior-based representationinternal nodeinternal sortinterpolation searchinterpolation-sequential searchinterpolation sort: see histogram sortintersectioninterval treeintractableintrosort: see introspective sortintrospective sortinverse Ackermann functioninverse suffix arrayinverted file indexinverted indexirreflexiveisomorphiciterationJJaro-WinklerJohnson's algorithmJohnson-TrotterJSortJ sortjump listjump searchKKarmarkar's algorithmKarnaugh mapKarp-RabinKarp reductionk-ary heapk-ary Huffman codingk-ary treek-clusteringk-coloringk-connected graphk-d-B-treek-dimensionalK-dominant matchk-d treekeyKMP: see Knuth-Morris-Pratt algorithmKmpSkip Searchknapsack problemknight's tourKnuth-Morris-Pratt algorithmKönigsberg bridges problem: see Euler cycleKolmogorov complexityKraft's inequalityKripke structureKruskal's algorithmkth order Fibonacci numberskth shortest pathkth smallest element: see select kth elementKV diagram: see Karnaugh mapk-way mergek-way merge sortk-way tree: see k-ary treeLlabeled graphlanguagelast-in, first-outLas Vegas algorithmlatticelayered graphLCM: see least common multipleLCSleafleast common multipleleftist treeleft rotationLempel-Ziv-Welchlevel-order traversalLevenshtein distancelexicographical orderLIFO: see stacklinearlinear congruential generatorlinear hashlinear hashinglinear insertion sort: see insertion sortlinear order: see total orderlinear probinglinear probing sortlinear productlinear programlinear quadtreelinear searchlinklinked listlistlist contractionlittle-o notationLm distanceload factorlocal alignmentlocality-sensitive hashinglocal optimumlogarithmiclongest common subsequencelongest common substringLotka's lawlower boundlower triangular matrixlowest common ancestorl-reductionlucky sortLZW compression: see Lempel-Ziv-WelchMMalhotra-Kumar-Maheshwari blocking flowManhattan distancemany-one reductionmap: see dictionaryMarkov chainMarlenamarriage problem: see assignment problemMaster theoremmatched edgematched vertexmatchingmatrixmatrix-chain multiplication problemmax-heap propertymaximal independent setmaximally connected componentMaximal Shiftmaximum bipartite matching: see bipartite matchingmaximum-flow problemMAX-SNPMBB: see minimum bounding boxMealy machinemeanmedianmeldmemoizationmergemerge sortmetaheuristicmetaphonemidrangeMiller-Rabinmin-heap propertyminimal perfect hashingminimaxminimum bounding boxminimum cutminimum path coverminimum spanning treeminimum vertex cutMinkowski distance: see Lm distancemixed integer linear programmodemodel checkingmodel of computationmoderately exponentialMODIFINDmonotone priority queuemonotonically decreasingmonotonically increasingMonte Carlo algorithmMoore machineMorris-Pratt algorithmmove: see transitionmove-to-front heuristicmove-to-root heuristicMST: see minimum spanning treemulti-commodity flowmultigraphmultikey Quicksortmultilayer grid filemultiplication methodmultiprefixmultiprocessor modelmulti-set: see bagmulti suffix treemultiway decisionmultiway mergemultiway search treemultiway treeMunkres' assignment algorithmNnaive string search: see brute force string searchnandn-ary functionNC many-one reducibilitynearest neighbornegationnetwork flow: see flow functionnetwork flow problem: see maximum-flow problemnext stateNFA: see nondeterministic finite state machineNFTA: see nondeterministic finite tree automatonNISTnodenonbalanced mergenonbalanced merge sortnondeterministicnondeterministic algorithmnondeterministic finite automaton: see nondeterministic finite state machinenondeterministic finite state machinenondeterministic finite tree automatonnondeterministic polynomial time: see NPnondeterministic tree automatonnondeterministic Turing machinenonterminal node: see internal nodenornotNot So NaiveNPNP-completeNP-complete languageNP-hardn queensnullary function: see 0-ary functionnull treeNYSIISOO: see big-O notationOBDDobjective functionoblivious algorithmoccurrenceoctreeoff-line algorithmoffsetomegaomicronone-based indexingone-dimensionalon-line algorithmopen addressingoptimaloptimal cost: see best-case costoptimal hashing: see perfect hashingoptimal mergeoptimal mismatchoptimal polygon triangulation problemoptimal polyphase mergeoptimal polyphase merge sortoptimal solutionoptimal triangulation problemoptimal valueoptimization problemororacle setoracle tapeoracle Turing machineorderordered arrayordered binary decision diagram: see OBDDordered linked listordered treeorder preserving hash: see linear hashorder-preserving Huffman codingorder preserving minimal perfect hashingoriented acyclic graph: see directed acyclic graphoriented graph: see directed graphoriented tree: see rooted treeorthogonal drawingorthogonal listsorthogonally convex rectilinear polygonoscillating merge sortout-degreePPpackingpadding argumentpagodapairing heapPAM: see point access methodparallel computation thesisparallel prefix computationparallel random-access machineparametric searchingparentpartial functionpartially decidable problempartially dynamic graph problempartially ordered set: see posetpartially persistent data structurepartial orderpartial recursive functionpartitionpassive data structurepathpath coverpath system problemPatricia treepatternpattern elementP-completePCP: see Post's correspondence problemPDA: see pushdown automatonPearson's hashperfect binary treeperfect hashingperfect k-ary treeperfect matchingperfect shuffleperformance guaranteeperformance ratio: see relative performance guaranteepermutationpersistent data structurephonetic codingpigeonhole sortpilepipelined divide and conquerplanar graphplanarizationplanar straight-line graphPLOP-hashingpoint access methodpointer jumpingpointer machinepoissonizationpolychotomypolyhedronpolylogarithmicpolynomialpolynomial approximation schemepolynomial hierarchypolynomial timepolynomial-time reductionpolyphase mergepolyphase merge sortpolytopeposetpostfix traversal: see postorder traversalPost machinepostman's sortpostorder traversalPost's correspondence problempotential functionPRAM: see parallel random-access machinepredicateprefixprefix codeprefix computationprefix sums: see scanprefix traversal: see preorder traversalpreorder traversalprimary clusteringprimitive recursivePrim-Jarnik algorithmprinciple of optimalitypriority queueprisoner's dilemmaPRNG: see pseudo-random number generatorprobabilistic algorithmprobabilistically checkable proofprobabilistic Turing machineprobe sequenceprocedureprocess algebraproperproper binary tree: see full binary treeproper coloringproper subsetproperty list: see dictionaryprune and searchpseudo-random number generatorPTAS: see polynomial approximation schemepth order Fibonacci numbers: see kth order Fibonacci numbersP-treepurely functional languagepushdown automatonpushdown transducerp-way merge sort: see k-way merge sortQqm sortq sortquadratic probingquadtreequadtree complexity theoremquad triequantum computationqueuequick searchquicksortRRabin-Karp: see Karp-Rabinradix sortradix tree: see Patricia treeragged matrixRaitarandom access machinerandomizationrandomized algorithmrandomized binary search treerandomized complexityrandomized polynomial time: see RPrandomized roundingrandomized search treeRandomized-Selectrandom number generatorrandom samplingrangerange sortrankrapid sortRatcliff/Obershelp pattern recognitionRBST: see randomized binary search treereachablerebalancerecognizerrectangular matrixrectilinearrectilinear Steiner treerecurrence equations: see recurrence relationrecurrence relationrecursionrecursion terminationrecursion treerecursiverecursive data structurerecursive doubling: see pointer jumpingrecursive language: see decidable languagerecursively enumerable languagerecursively solvable: see decidable problemred-black treereduced basisreduced digraphreduced ordered binary decision diagramreductionreflexiveregular decompositionrehashing: see double hashingrelationrelational structurerelative performance guaranteerelaxationrelaxed balancerepeated squaringrescalablerestricted universe sortresult cacheReverse ColussiReverse FactorR-fileRice's methodright rotationright-threaded treeRNG: see random number generatorROBDD: see reduced ordered binary decision diagramRobin Hood hashingrootroot balance: see balancerooted treerotate left: see left rotationrotate right: see right rotationrotationrough graphRPR+-treeR*-treeR-treerun timeSsaguaro stack: see cactus stackSAM: see spatial access methodsaturated edgeSBB treescanscapegoat treescatter storage: see hash tablesearchsearch treesearch tree propertysecant searchsecondary clusteringsegmentSelectselect and partitionselection problem: see select kth elementselection sortselect kth elementselect modeself-loopself-organizing heuristicself-organizing listself-organizing sequential search: see transpose sequential searchsemidefinite programmingseparate chainingseparation theoremsequential search: see linear searchsetset coverset packingshadow heapshadow mergeshadow merge insertshaker sort: see bidirectional bubble sortShannon-Fano codingshared memoryShell sortShift-OrShor's algorithmshortcutting: see pointer jumpingshortest common supersequenceshortest common superstringshortest pathshortest spanning tree: see minimum spanning treeshuffle: see permutationshuffle sortsiblingsieve of Eratosthenessift upsignatureSimon's algorithmsimple mergesimple pathsimple uniform hashingsimplexsimulated annealingsimulation theoremsingle-destination shortest-path problemsingle-pair shortest-path problem: see shortest pathsingle program multiple datasingle-source shortest-path problemsingly linked list: see linked listsingularity analysissinksinking sort: see bubble sortskd-treeskew symmetryskip listskip searchslope selectionSmith algorithmSmith-Waterman algorithmsmoothsortsolvablesortsorted arraysorted listsort in place: see in-place sortsoundexsourcespace-constructible functionspace ordering methodspanning treesparse graphsparse matrixsparsificationsparsityspatial access methodspiral storagesplay treeSPMD: see single program multiple datasquare matrixsquare rootSST: see minimum spanning treestablestackstack treestar encodingstar-shaped polygonstart statestatestate machinestate transition: see transitionstaticstatic Huffman coding: see Huffman codings-t cutst-digraphSteiner pointSteiner ratioSteiner treeSteiner vertexSteinhaus-Johnson-Trotter: see Johnson-TrotterStirling's approximationStirling's formulastooge sortstraight-line drawingstrand sortstrictly decreasingstrictly increasingstrictly lower triangular matrixstrictly upper triangular matrixstringstring editing problemstring matchingstring matching on ordered alphabetsstring matching with errorsstring matching with mismatchesstring searching: see string matchingstrip packingstrongly connected componentstrongly connected graphstrongly NP-hardsubadditive ergodic theoremsubgraphsubgraph isomorphismsublinear time algorithmsubsequencesubsetsubstringsubtreesuffixsuffix arraysuffix automatonsuffix treesuperimposed codesupersetsupersinksupersourcesymmetricsymmetrically linked list: see doubly linked listsymmetric binary B-tree: see red-black treesymmetric set differencesymmetry breakingTtailtail recursiontargettemporal logicterminalterminal node: see leafternary search treetexttext searching: see string matchingtheta: see Θthreaded binary treethreaded treethree-dimensionalthree-way merge sortthree-way radix quicksort: see multikey Quicksorttime-constructible functiontime/space complexitytop-down radix sorttop-down tree automatontopological ordertopological sorttopology treetotal functiontotally decidable language: see decidable languagetotally decidable problem: see decidable problemtotally undecidable problemtotal ordertour: see Hamiltonian cycletournamenttournament sorttowers of Hanoitractabletransitiontransition functiontransitivetransitive closuretransitive reductiontranspose sequential searchtraveling salesmantreaptreetree automatontree contractiontree editing problemtreesort (1)treesort (2)tree traversaltriangle inequalitytriconnected graphtrietrinary functiontripartitionTSP: see traveling salesmanTST: see ternary search treeTurbo-BMTurbo Reverse FactorTuring machineTuring reductionTuring transducertwin grid file2-choice hashingtwo-dimensional2-left hashingtwo-level grid file2-3-4 tree2-3 treeTwo Way algorithmtwo-way linked list: see doubly linked listtwo-way merge sortUUB-treeUKP: see unbounded knapsack problemunary functionunbounded knapsack problemuncomputable functionuncomputable problemundecidable languageundecidable problemundirected graphuniform circuit complexityuniform circuit familyuniform hashinguniform matrixunionunion of automatauniversal B-tree: see UB-treeuniversal hashinguniversal stateuniversal Turing machineuniverseUnShuffle sortunsolvable problemunsorted listupper triangular matrixVvan Emde-Boas priority queuevehicle routing problemVeitch diagram: see Karnaugh mapVenn diagramvertexvertex coloringvertex connectivityvertex coververtical visibility mapvirtual hashingvisibility mapvisibleViterbi algorithmVitter's algorithmVRP: see vehicle routing problemWwalkweak-heapweak-heap sortweight-balanced tree: see BB(α) treeweighted, directed graphweighted graphwindowwitnessworkwork-depth modelwork-efficientwork-preservingworst caseworst-case costworst-case minimum accessXxorYYule distribution: see Zipfian distributionZZeller's congruence0-ary function0-based indexing0-1 knapsack problem: see knapsack problemZhu-TakaokaZipfian distributionZipf's lawzipperZPPWe thankthose who contributed definitionsas well as many others who offered suggestions and corrections.Here are some references on algorithms and data structures.The Stony BrookAlgorithm Repository, which has algorithms organized by type,succinct, illustrated definitions, and ratings of sites withimplementations.DataStructures and Algorithms is a wonderful site with illustrations,explanations, analysis, and code taking the student from arrays andlists through trees, graphs, and intractable problems.Eric Weisstein's Worldof Mathematics or MathWorld.The Computing Research Repository (CoRR).Bibliography[AS98]Pankaj K. Agarwal and Micha Sharir, EfficientAlgorithms for Geometric Optimization, ACM Computing Surveys,30(4):412-458, December 1998.[ATCH99] Algorithms and Theory of ComputationHandbook,Mikhail J. Atallah, ed., CRC Press LLC, 1999.[CLR90]Thomas H. Cormen, Charles E. Leiserson, and RonaldL. Rivest, Introduction to Algorithms,MIT Press, 1990.[GBY91]Gaston H. Gonnet and Ricardo Baeza-Yates,Handbook of Algorithms and Data Structures -- in Pascal and C,2nd edition, Addison-Wesley, 1991.[GCG92]P. Gupta, P. P. Chakrabarti, and S. Ghose,The Towers of Hanoi: Generalizations, Specializations, andAlgorithms, Intern. J. Computer Math., 46:149-161, Gordon and Breach Science Publishers S.A., 1992.[GG98]Volker Gaede and Oliver Günther,Multidimensional Access Methods, ACM Computing Surveys,30(2):170-231, June 1998.[GT97]Michael T. Goodrich and Roberto Tamassia,Data Structures and Algorithms in Java,2nd edition,John Wiley & Sons, 1997.[Graef06]Goetz Graefe,Implementing Sorting in Database Systems, ACM Computing Surveys,38(3), Article 10, September 2006.[Hirv01]Mika Hirvensalo, Quantum Computing,Springer-Verlag, 2001.[HS83]Ellis Horowitz and Sartaj Sahni, Fundamentals of Data Structures,Computer SciencePress, 1983.[Knuth98]Donald E. Knuth, The Art of ComputerProgramming, Addison-Wesley, volumes 1, 2, and 3, 3rdedition, 1998.[Leda98]LEDA(accessed 4 December 2002).[Sedge97]Robert Sedgewick, Algorithms in C,Addison-Wesley, 1997.[Stand98]Thomas Standish, Data Structures in Java, Addison-Wesley, 1998.[Sund98]Daniel M. Sunday, A Very Fast SubstringSearch Algorithm, Communications of the ACM, 33(8):132-142,August 1998.[Vitt01]Jeffrey Scott Vitter, External Memory Algorithmsand Data Structures: Dealing with Massive Data, ACM ComputingSurveys, 33(2):209-271, June 2001.[Wier98]Roel Wieringa, A Survey of Structured andObject-Oriented Software Specification Methods and Techniques,ACM Computing Surveys, 30(4):459-527, December 1998.Here arecitation examples and an explanationof credit.Robots, please indexall term pages, including spelling variants. PRIVACYPOLICY/SECURITY NOTICENIST is an agency of the U.S. Department of Commerce CreatedFri Sep 4 16:39:23 1998by Paul E. BlackThis TrailerUpdatedMon Dec 3 11:46:26 2007by Paul E. Black (paul.black@nist.gov)This page's URL ishttp://www.nist.gov/dads/ |
|
