[HOME] [PREFACE] [CONTENTS]

Data Structures, Algorithms, and Performance

Derick Wood

First Edition---Background

This text is, primarily, about data structures and their performance, and, secondarily, about algorithms. It has been written for a junior- or senior-level course in data structures. My goals are to introduce students to the world of data structures, to show them how to evaluate data structures, to help them obtain insight about data structures, and to give them the basis for making wise choices of data structures in the future. I consider this book to be the second volume of a trilogy on data structures; the first volume would be on data structures and program design (CS II material) such as the text of Kruse, ``Data Structures and Program Design,'' and the third volume would emphasize the cutting edge of data-structure research, such as the text of Mehlhorn ``Data Structures and Algorithms.'' For this reason, the text is divided into three parts:

  • A review (Chapters 1 through 6) that covers the material to which I expect most students to have been exposed; it is medium paced and detailed.
  • A core (Chapters 7 through 14) that covers strings, tables, dictionaries, priority queues, sorting, graphs, and partitions; it is brisk and detailed.
  • A preview (Chapter 15) that covers, briefly, material that both is exciting and is more recent or less established than that in the core; it is very brisk and provides little detail.

    • The text has an emphasis different from that of currently available data structure texts, in that it:

  • Is down to earth, yet does not mire the reader in details.
  • Uses an ADT framework in a consistent manner.
  • Emphasizes the choice of efficient data structures for specific groups of operations or ADTs.
  • Shuns the encyclopedic study of data structures by focusing on those that are efficient, easy to implement, or have some inherent interest.
  • Covers data structures that are used to solve real-world problems.
  • Presents analyses of a number of data structures.
  • Presents material on main memory and disk data structures in an integrated manner.
  • Covers a number of recently introduced data structures (in the core are: red--black trees, splay trees, linear-hash tables, Fibonacci queues, priority-search trees, and union-deunion-find structures; in the preview are: skip lists, quad trees, k-d trees, segment trees, hierarchical trees, dynamization, and persistence).
  • Discusses three algorithms that are the basis of utilities (string-edit distance [diff], Boyer--Moore--Horspool pattern matching [grep], Ziv--Lempel--Welch compression [compress]).
  • Uses worst-case, expected-case, and amortized-case analyses throughout the text.
  • Encourages the simulational and empirical evaluation of data structures.

    • Derick Wood, May 1, 1992.

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