.. This file is part of the OpenDSA eTextbook project. See .. http://algoviz.org/OpenDSA for more details. .. Copyright (c) 2012-2016 by the OpenDSA Project Contributors, and .. distributed under an MIT open source license. .. OpenDSA documentation master file, created by sphinx-quickstart on Sat Mar 17 18:07:39 2012. You can adapt this file completely to your liking, but it should at least contain the root `toctree` directive. .. avmetadata:: OpenDSA Sample eTextbook :author: OpenDSA Contributors :topic: Data Structures .. chapnum:: :start: 0 :prefix: Chapter .. _index: .. raw:: html .. |--| unicode:: U+2013 .. en dash .. |---| unicode:: U+2014 .. em dash, trimming surrounding whitespace :trim: Preface ======= .. toctree:: :numbered: :maxdepth: 3 Intro Status Introduction ============ .. toctree:: :numbered: :maxdepth: 3 IntroDSA Biographies =========== .. toctree:: :numbered: :maxdepth: 3 CarlGauss FrancisBacon Programming Tutorials ===================== .. toctree:: :numbered: :maxdepth: 3 cmdline parameters eclipseparameters webcattools debugmethods debug scanning randomaccessfile junitstart junitbasic junitcoverage Design I ======== .. toctree:: :numbered: :maxdepth: 3 ADT IntroOO IntroUML IntroProcess Pointers ======== .. toctree:: :numbered: :maxdepth: 3 PointerIntro BasicPointers LocalMem HeapMem Links Mathematical Background ======================= .. toctree:: :numbered: :maxdepth: 3 MathpreIntro SetDef MiscMath Logarithms Summations RecurrenceIntro Proofs Estimation MathpreSumm Searching I =========== .. toctree:: :numbered: :maxdepth: 3 BinarySearch Algorithm Analysis ================== .. toctree:: :numbered: :maxdepth: 3 AnalChap AnalPrelim AnalIntro AnalCases AnalCompvsAlg AnalAsymptotic AnalLower AnalProgram AnalProblem AnalMisunderstanding AnalMultiple AnalSpace AnalTuning AlgAnalSummCS2 AlgAnalSummCS3 Linear Structures ================= .. toctree:: :numbered: :maxdepth: 3 ListIntro ListADT ListArray ListLinked ListAnalysis ListDouble ListElement StackArray StackLinked Freelist StackRecur Queue QueueLinked ListSumm Recursion ========= .. toctree:: :numbered: :maxdepth: 3 RecIntro Write CodeCompletionEx HarderWrite HarderCodeCompletionEx WritingEx Trace TracingEx RecSummaryEx Design II ========= .. toctree:: :numbered: :maxdepth: 3 DesignPatterns DesignAltList Comparison Dictionary Binary Trees ============ .. toctree:: :numbered: :maxdepth: 3 BinaryTreeIntro BinaryTree RecursiveDS BinaryTreeFullThm BinaryTreeTraversal WritingTraversals BinaryTreeInfFlw BinaryTreeImpl Composite BinaryTreeNodeSpace BST BSTDict BinaryTreeGuidedInfFlw MultipleBinaryTrees BSTCheck CompleteTree Heaps Huffman TreeTrie HuffProof BinaryChapSumm Sorting ======= .. toctree:: :numbered: :maxdepth: 3 InSort SortNotation InsertionSort BubbleSort SelectionSort ExchangeSort SortOpt Shellsort Mergesort MergesortImpl Quicksort Heapsort BinSort RadixSort SortingEmpirical SortingLowerBound SortSumm File Processing =============== .. toctree:: :numbered: :maxdepth: 3 FileProc Secondary Diskdrive BuffPool FileProg ExternalSort Hashing ======= .. toctree:: :numbered: :maxdepth: 3 HashIntro HashFunc HashFuncExamp OpenHash BucketHash HashCSimple HashCImproved HashAnal HashDel HashSumm Memory Management ================= .. toctree:: :numbered: :maxdepth: 3 MemmanIntro Dynamic SequentialFit FirstFit CircularFit BestFit WorstFit MMPerformance Buddy Garbage Indexing ======== .. toctree:: :numbered: :maxdepth: 3 IndexIntro LinearIndexing ISAM TreeIndexing TwoThreeTree BTree IndexingSumm General Trees ============= .. toctree:: :numbered: :maxdepth: 3 GenTreeIntro UnionFind SequentialRep Graphs ====== .. toctree:: :numbered: :maxdepth: 3 GraphIntro GraphImpl GraphTraversal GraphTopsort GraphShortest MCST Kruskal Floyd Spatial Data Structures ======================= .. toctree:: :numbered: :maxdepth: 3 Spatial PRquadtree KDtree Bintree OtherSpatial Senior Algorithms Course ======================== .. toctree:: :numbered: :maxdepth: 3 AAIntro ProblemSolving AAOverview TOH BoundsReview GrowthRate AdvSumm Recurrence Searching ========= .. toctree:: :numbered: :maxdepth: 3 SearchIntro UnsortedSearch SortedSearch SelfOrg SetSearch PerfectHash Lower Bounds ============ .. toctree:: :numbered: :maxdepth: 3 BoundMax BoundAdversary BoundState BoundiBest SortingOptimal Number Problems =============== .. toctree:: :numbered: :maxdepth: 3 Numeric FFT Probabilistic Algorithms ======================== .. toctree:: :numbered: :maxdepth: 3 Probabilistic Primes RandomNums SkipList Search Structures ================= .. toctree:: :numbered: :maxdepth: 3 BalancedTree AVL Splay RedBlack Miscellaneous ============= .. toctree:: :numbered: :maxdepth: 3 DynamicProgramming AmortAnal Knapsack EditDistance StringSearchKMP StringSearchBoyerMoore StringSearchRabinKarp GenTreeImplement Kary Limits to Computing =================== .. toctree:: :numbered: :maxdepth: 3 LimComp Reduction NPComplete circuitSAT SAT threeSAT clique independentSet vertexCover hamiltonianCycle TSP provingNPC circuitSAT_to_SAT SAT_to_threeSAT threeSAT_to_clique clique_to_independentSet independentSet_to_vertexCover threeSAT_to_hamiltonianCycle hamiltonianCycle_to_TSP NPCoping Impossible Turing Appendix ======== .. toctree:: :numbered: :maxdepth: 3 Glossary Bibliography .. toctree:: :maxdepth: 3 * :ref:`genindex` * :ref:`search`