[HOME] [FULL CONTENTS]

Data Structures, Algorithms, and Performance

Derick Wood

First Edition---Contents

PREFACE...v

Part I--REVIEW...1

Chapter 1--Data Structures and Data Types...3

  • 1.1--Data-Structure Design...4
  • 1.2--The Reversal Problem...8
  • 1.3--Data Abstraction Revisited...9
  • 1.4--ADT Specification...13
  • 1.5--Queue Representations...19
  • 1.6--Stack Representations...31
  • 1.7--Summary...36
  • 1.8--History...37
  • Exercises...38
    • Chapter 2--Performance Measurement...41
  • 2.1--Empirical Measurement...42
  • 2.2--Simulational Measurement...43
  • 2.3--Analytical Measurement...53
  • 2.4--Performance Comparison and Evaluation...62
  • 2.5--The Analysis of Recursive Subprograms...69
  • 2.6--Summary...78
  • 2.7--History...79
  • Exercises...80
    • Chapter 3--Lists...87
  • 3.1--List Specification...88
  • 3.2--Copying and Equality Testing...90
  • 3.3--Polynomial Manipulation...93
  • 3.4--List Representations...97
  • 3.5--The Simplist ADT...105
  • 3.6--Performance Reports...110
  • 3.7--Element and Window Assumptions...112
  • 3.8--Summary...112
  • 3.9--History...113
  • Exercises...113
    • Chapter 4--Maps and Arrays...117
  • 4.1--Map and Array Specification...118
  • 4.2--Map Representations...119
  • 4.3--Array Representations...122
  • 4.4--Sparse-Array Representations...131
  • 4.5--Performance Reports...134
  • 4.6--Summary...135
  • 4.7--History...136
  • Exercises...136

    • Part II--DATA STRUCTURES AND DATA TYPES...139

    Chapter 5--Trees and Forests...141

  • 5.1--Tree Definitions...141
  • 5.2--Bintree, Tree, and Orchard Specification...149
  • 5.3--Tree Traversals...151
  • 5.4--Binary-Tree Display...158
  • 5.5--Bintree Representations...160
  • 5.6--Tree Representations...174
  • 5.7--Performance Reports...175
  • 5.8--Summary...177
  • 5.9--History...178
  • Exercises...178
    • Chapter 6--Applications of Trees...185
  • 6.1--Text, Codes, and Compression...186
  • 6.2--Spell Checking and Tries...198
  • 6.3--Arrays Defined at Execution-Time ...203
  • 6.4--Summary...207
  • 6.5--History...207
  • Exercises...208
    • Chapter 7--Strings...211
  • 7.1--String Specification...212
  • 7.2--Pattern Matching...213
  • 7.3--Suffix and PATRICIA Tries...223
  • 7.4--Minimum Edit Distance...229
  • 7.5--Adaptive Data Compression...233
  • 7.6--String Representations...241
  • 7.7--Summary...244
  • 7.8--History...245
  • Exercises...246
    • Chapter 8--Sets, Tables, and Dictionaries...249
  • 8.1--Set, Table, and Dictionary Specifications...250
  • 8.2--Set Representations...252
  • 8.3--Table Representations...256
  • 8.4--Dictionary Representations...263
  • 8.5--Search Trees and Dictionaries...271
  • 8.6--Performance Reports...292
  • 8.7--Summary...295
  • 8.8--History...296
  • Exercises...297
    • Chapter 9--Tables and Hashing...301
  • 9.1--Hashed Representations of Table...302
  • 9.2--Bucketing and Separate Chaining...306
  • 9.3--Open Addressing...311
  • 9.4--Dynamic Tables...319
  • 9.5--External Tables...326
  • 9.6--Performance Reports...333
  • 9.7--Summary...334
  • 9.8--History...335
  • Exercises...336
    • Chapter 10--Dictionaries and Search Trees...339
  • 10.1--Optimal Binary Search Trees...340
  • 10.2--Red--Black Trees...353
  • 10.3--Splay Search Trees...367
  • 10.4--B+ Trees...376
  • 10.5--Performance Reports...391
  • 10.6--Summary...392
  • 10.7--History...393
  • Exercises...393
    • Chapter 11--Priority Searching...399
  • 11.1--Priority Queue Specification...400
  • 11.2--Priority Queue Representations...401
  • 11.3--Priority Search Queues...413
  • 11.4--Summary...422
  • 11.5--History...423
  • Exercises...423
    • Chapter 12--Sorting...425
  • 12.1--Comparison-Based Sorting...428
  • 12.2--Sorting: A Lower Bound...440
  • 12.3--Digital Sorting...443
  • 12.4--Adaptive Sorting...446
  • 12.5--External Sorting...448
  • 12.6--Performance Reports...457
  • 12.7--Summary...458
  • 12.8--History...459
  • Exercises...460
    • Chapter 13--Graphs and Digraphs...463
  • 13.1--Graph and Digraph Specifications...464
  • 13.2--Graph and Digraph Representations...467
  • 13.3--Digraph Algorithms...469
  • 13.4--Graph Algorithms...485
  • 13.5--Memory Management...497
  • 13.6--Performance Reports...504
  • 13.7--Summary...506
  • 13.8--History...506
  • Exercises...507
    • Chapter 14--Partition...511
  • 14.1--Partition Specification...513
  • 14.2--Representations in Particular...514
  • 14.3--Representations in General...519
  • 14.4--Back to the Past...520
  • 14.5--Performance Reports...523
  • 14.6--Summary...524
  • 14.7--History...524
  • Exercises...524

    • Part III--PREVIEW...527

    Chapter 15--Further Topics...529

  • 15.1--Skip Lists...531
  • 15.2--Quad Trees...534
  • 15.3--K-d Trees...540
  • 15.4--Grid Files...546
  • 15.5--Segment Trees, Range Trees, and Segment Intersection...550
  • 15.6--Hierarchical Trees and Rectangles...555
  • 15.7--Dynamization...558
  • 15.8--Persistence...563
  • Exercises...567

    REFERENCES...571

    INDEX...583

    [HOME] [FULL CONTENTS]
    http://www.cs.ust.hk/~dwood/.dsap
    dwood@cs.ust.hk
    Computer Science Department
    The Hong Kong University of Science and Technology
    Clear Water Bay, Kowloon
    HONG KONG