[HOME] [CONTENTS]

Data Structures, Algorithms, and Performance

Derick Wood

First Edition---Full Contents

PREFACE...v

Part I--REVIEW...1

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

  • 1.1--Data-Structure Design...4
  • 1.1.1--The Top-Down, Bottom-Up Approach...4
  • 1.1.2--Levels of Refinement...4
  • 1.1.3--Abstract Data Types...7
  • 1.1.4--The Benefits of ADTs...8
  • 1.2--The Reversal Problem...8
  • 1.3--Data Abstraction Revisited...9
  • 1.4--ADT Specification...13
  • 1.4.1--The Queue ADT...14
  • 1.4.2--The Stack ADT...15
  • 1.4.3--The Reversal Problem: An ADT Solution...16
  • 1.4.4--Partial Functions in Practice...16
  • 1.4.5--ADT Specification in {Pascal}...18
  • 1.4.6--Layers of Representation and Implementation...19
  • 1.5--Queue Representations...19
  • 1.5.1--Block Representations...20
  • 1.5.2--Pointer Representations...24
  • 1.5.3--Cursor Representations...25
  • 1.5.4--Memory Management...28
  • 1.5.5--Performance Reports...31
  • 1.6--Stack Representations...31
  • 1.6.1--A Block Representation...34
  • 1.6.2--A Pointer Representation...35
  • 1.6.3--Performance Reports...35
  • 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.2.1--A Simulation...44
  • 2.2.2--Pseudorandom Numbers...48
  • 2.2.3--The Length of a Test Sequence*...51
  • 2.3--Analytical Measurement...53
  • 2.3.1--An Analytical Primer...53
  • 2.3.2--The Choice of Measures...56
  • 2.3.3--Stacks and Amortization...60
  • 2.4--Performance Comparison and Evaluation...62
  • 2.4.1--Asymptopia...63
  • 2.4.2--Big-Oh Algebra*...66
  • 2.4.3--The Random-Access--Machine Model...67
  • 2.4.4--The Direct-Access--Memory Model...68
  • 2.5--The Analysis of Recursive Subprograms...69
  • 2.5.1--The Battery-Powered--Car Problem...70
  • 2.5.2--Tabulation and Restriction*...72
  • 2.5.3--The Difference Operator*...74
  • 2.5.4--Recurrence Equations with Standard Solutions...77
  • 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.4.1--A Block Representation...97
  • 3.4.2--Pointer Representations...98
  • 3.5--The Simplist ADT...105
  • 3.5.1--Simplist Specification...105
  • 3.5.2--Pointer Reversal...106
  • 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.3.1--Lexicographically Ordered Representation...122
  • 4.3.2--Shell-Ordered Representation...126
  • 4.3.3--Extendible Representations...127
  • 4.3.4--Lazy Initialization...129
  • 4.4--Sparse-Array Representations...131
  • 4.4.1--Bit-Array Representation...132
  • 4.4.2--Orthogonally Linked List Representation...133
  • 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.1.1--Binary Trees...141
  • 5.1.2--Multiway Trees...148
  • 5.1.3--Forests and Orchards...148
  • 5.2--Bintree, Tree, and Orchard Specification...149
  • 5.3--Tree Traversals...151
  • 5.3.1--Depth-First Traversals...151
  • 5.3.2--Level-Order Traversal...153
  • 5.3.3--Traversal Analysis...155
  • 5.4--Binary-Tree Display...158
  • 5.5--Bintree Representations...160
  • 5.5.1--Block Representations...160
  • 5.5.2--Pointer Representations...166
  • 5.5.3--Threaded Trees...170
  • 5.5.4--Pointer Reversal...173
  • 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.1.1--An Introduction to Codes...186
  • 6.1.2--Morse Code...189
  • 6.1.3--Optimal Variable-Length Codes...190
  • 6.1.4--Huffman's Algorithm...193
  • 6.1.5--An Analysis of Huffman's Algorithm...198
  • 6.2--Spell Checking and Tries...198
  • 6.2.1--Use of Tries...199
  • 6.2.2--Binary Tries...201
  • 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.2.1--A Naive Approach to Pattern Matching...214
  • 7.2.2--The KMP algorithm...216
  • 7.2.3--The BMH Algorithm...220
  • 7.3--Suffix and PATRICIA Tries...223
  • 7.3.1--Suffix Tries...223
  • 7.3.2--Construction of Suffix Tries...225
  • 7.3.3--PATRICIA Tries...227
  • 7.4--Minimum Edit Distance...229
  • 7.4.1--A Naive Algorithm...230
  • 7.4.2--A Dynamic-Programming Algorithm...231
  • 7.5--Adaptive Data Compression...233
  • 7.5.1--The ZLW Encoding Algorithm...234
  • 7.5.2--The ZLW Decoding Algorithm...238
  • 7.5.3--Implementation and Data Structures...240
  • 7.6--String Representations...241
  • 7.6.1--List Representations...241
  • 7.6.2--A Chunked-Pointer Representation...241
  • 7.6.3--An External Representation...242
  • 7.6.4--Performance Reports...243
  • 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.2.1--The Characteristic Function Representation...252
  • 8.2.2--List Representations of Sets...254
  • 8.3--Table Representations...256
  • 8.3.1--Set Representations...256
  • 8.3.2--Lists and Optimal Sequential Search...256
  • 8.3.3--Adaptation and Move-to-Front...259
  • 8.3.4--An Analysis of the Move-to-Front Heuristic...260
  • 8.4--Dictionary Representations...263
  • 8.4.1--A Lower Bound for Searching...263
  • 8.4.2--Ordered Blocks and Interpolation Search...269
  • 8.5--Search Trees and Dictionaries...271
  • 8.5.1--Binary Search Trees...271
  • 8.5.2--Insertion...277
  • 8.5.3--Deletion...277
  • 8.5.4--A Cost Measure for Binary Search Trees...281
  • 8.5.5--Analysis of Binary Search Trees...284
  • 8.5.6--Predecessor and Successor Queries...288
  • 8.5.7--Range Queries...289
  • 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.1.1--Introduction to Hashing...302
  • 9.1.2--Hash Functions...304
  • 9.2--Bucketing and Separate Chaining...306
  • 9.2.1--Analysis of Separate Chaining*...308
  • 9.3--Open Addressing...311
  • 9.3.1--Linear Probing...312
  • 9.3.2--Double Hashing...315
  • 9.3.3--Uniform Hashing and Its Analysis*...316
  • 9.3.4--Dealing with Deletions...318
  • 9.4--Dynamic Tables...319
  • 9.4.1--Linear Hashing...320
  • 9.4.2--Analysis of Linear Hashing*...323
  • 9.5--External Tables...326
  • 9.5.1--ISAM...327
  • 9.5.2--Hashing with One-Disk-Access Retrieval...328
  • 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.1.1--Preliminaries...341
  • 10.1.2--A Dynamic-Programming Algorithm...345
  • 10.1.3--Analysis of the Construction Algorithm...350
  • 10.1.4--Entropy and Optimality*...352
  • 10.2--Red--Black Trees...353
  • 10.2.1--Definition and Properties of Red--Black Trees...353
  • 10.2.2--Promotions and Rotations...357
  • 10.2.3--Insertion...358
  • 10.2.4--Deletion...363
  • 10.3--Splay Search Trees...367
  • 10.3.1--Splaying...368
  • 10.3.2--Analysis of Splay Trees*...368
  • 10.4--B+ Trees...376
  • 10.4.1--Multiway Search Trees...376
  • 10.4.2--Definition and Properties of B+ Trees...378
  • 10.4.3--Insertion...382
  • 10.4.4--Deletion...386
  • 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.2.1--Dictionary-based Representations...401
  • 11.2.2--Priority Trees...403
  • 11.2.3--Heaps...405
  • 11.2.4--Fibonacci Queues...408
  • 11.2.5--Performance Reports...412
  • 11.3--Priority Search Queues...413
  • 11.3.1--Priority-Search Queue Specification...414
  • 11.3.2--Priority Search Trees...415
  • 11.3.3--Update of a Priority Search Tree...418
  • 11.3.4--Performance Reports...422
  • 11.4--Summary...422
  • 11.5--History...423
  • Exercises...423
    • Chapter 12--Sorting...425
  • 12.1--Comparison-Based Sorting...428
  • 12.1.1--Bubble Sorting...428
  • 12.1.2--Selection Sorting---Hard Split...431
  • 12.1.3--Insertion Sorting---Hard Join...436
  • 12.2--Sorting: A Lower Bound...440
  • 12.3--Digital Sorting...443
  • 12.3.1--Bucket Sorting...443
  • 12.3.2--Digital Sorting...444
  • 12.4--Adaptive Sorting...446
  • 12.5--External Sorting...448
  • 12.5.1--Multiway Merge Sort...450
  • 12.5.2--Replacement--Selection...453
  • 12.5.3--Creation of Initial Runs...453
  • 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.3.1--A Scheduling Problem...470
  • 13.3.2--Acyclicity and Traversals...472
  • 13.3.3--Topological Sorting...475
  • 13.3.4--Minimum or Shortest Paths...479
  • 13.4--Graph Algorithms...485
  • 13.4.1--Walking the Planks...485
  • 13.4.2--Path Connectedness...487
  • 13.4.3--Connected Components...487
  • 13.4.4--Minimum Spanning Trees...489
  • 13.4.5--Scatter Plots and Minimal Tours...491
  • 13.5--Memory Management...497
  • 13.5.1--A Memory-Management Model...497
  • 13.5.2--The Simple Case: Fixed-Sized Blocks...498
  • 13.5.3--Variably Sized Blocks...499
  • 13.5.4--The Buddy Systems...501
  • 13.5.5--Compaction...502
  • 13.5.6--Fixed-Sized Linked Blocks...504
  • 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.2.1--The Parent-Link Forest Representation...514
  • 14.2.2--Height Linking...516
  • 14.2.3--Halving...517
  • 14.3--Representations in General...519
  • 14.3.1--Binary Search Trees...519
  • 14.3.2--Hashing...520
  • 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.2.1--The Construction of Quad Trees...537
  • 15.2.2--Range and Co-Range Queries...538
  • 15.3--K-d Trees...540
  • 15.3.1--The Construction of 2-d Trees...543
  • 15.3.2--Partial-Match Search...543
  • 15.3.3--Nearest-Neighbor Search...545
  • 15.4--Grid Files...546
  • 15.4.1--The Definition of a Grid File...546
  • 15.4.2--Updating of a Grid File...548
  • 15.5--Segment Trees, Range Trees, and Segment Intersection...550
  • 15.5.1--The Definition of Segment Trees...550
  • 15.5.2--Updating of a Segment Tree...551
  • 15.5.3--Range Trees...553
  • 15.5.4--Segment-Intersection Search...554
  • 15.6--Hierarchical Trees and Rectangles...555
  • 15.6.1--Stabbing Search...556
  • 15.6.2--Rectangle-Intersection Search...557
  • 15.6.3--Construction of Hierarchical Trees...557
  • 15.7--Dynamization...558
  • 15.7.1--Promotions and k-d Trees...558
  • 15.7.2--Dynamic 2-d Trees...559
  • 15.8--Persistence...563
  • 15.8.1--A Few Simple Techniques...563
  • 15.8.2--Path Copying...564
  • 15.8.3--Limited-Node Copying...566
  • Exercises...567

    • REFERENCES...571

    INDEX...583

    [HOME] [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