A Practical Introduction to Data Structures and Algorithm Analysis Edition 3. Shaffer Department of Computer Science Virginia Tech Blacksburg, VA 24061 March 28, 2013 Update 3.10 For a list of changes, see http://people.edu/˜shaffer/Book/errata.html Copyright © 2009-2012 by Clifford A. This document is made freely available in PDF form for educational and other non-commercial use. You may make copies of this file and redistribute in electronic form without charge.
You may extract portions of this document provided that the front page, including the title, author, and this notice are included. Any commercial use of this document requires the written consent of the author. The author can be reached at shaffer@cs. If you wish to have a printed version of this document, print copies are published by Dover Publications (see http://store.
Further information about this text is available at http://people.edu/˜shaffer/Book/. Contents Preface xiii I Preliminaries 1 1 Data Structures and Algorithms 3 1.1 A Philosophy of Data Structures 4 1.1 The Need for Data Structures 4 1.2 Costs and Benefits 6 1.2 Abstract Data Types and Data Structures 8 1.4 Problems, Algorithms, and Programs 16 1.6 Exercises 20 2 Mathematical Preliminaries 25 2.1 Sets and Relations 25 2.4 Summations and Recurrences 32 2.6 Mathematical Proof Techniques 38 iii iv Contents 2.2 Proof by Contradiction 39 2.3 Proof by Mathematical Induction 40 2.9 Exercises 48 3 Algorithm Analysis 55 3.2 Best, Worst, and Average Cases 61 3.3 A Faster Computer, or a Faster Algorithm? 62 3.5 Calculating the Running Time for a Program 71 3.10 Speeding Up Your Programs 82 3.14 Projects 90 II Fundamental Data Structures 93 4 Lists, Stacks, and Queues 95 4.1 Array-Based List Implementation 100 4.3 Comparison of List Implementations 112 Contents v 4.5 Doubly Linked Lists 115 4.1 Array-Based Stacks 121 4.3 Comparison of Array-Based and Linked Stacks 123 4.1 Array-Based Queues 128 4.3 Comparison of Array-Based and Linked Queues 133 4.7 Projects 148 5 Binary Trees 151 5.1 Definitions and Properties 151 5.1 The Full Binary Tree Theorem 153 5.2 A Binary Tree Node ADT 155 5.2 Binary Tree Traversals 155 5.3 Binary Tree Node Implementations 160 5.1 Pointer-Based Node Implementations 160 5.3 Array Implementation for Complete Binary Trees 168 5.4 Binary Search Trees 168 5.5 Heaps and Priority Queues 178 5.6 Huffman Coding Trees 185 5.1 Building Huffman Coding Trees 186 5.2 Assigning and Using Huffman Codes 192 5.3 Search in Huffman Trees 195 5.9 Projects 200 6 Non-Binary Trees 203 vi Contents 6.1 General Tree Definitions and Terminology 203 6.1 An ADT for General Tree Nodes 204 6.2 General Tree Traversals 205 6.2 The Parent Pointer Implementation 207 6.3 General Tree Implementations 213 6.1 List of Children 214 6.2 The Left-Child/Right-Sibling Implementation 215 6.3 Dynamic Node Implementations 215 6.4 Dynamic “Left-Child/Right-Sibling” Implementation 218 6.5 Sequential Tree Implementations 219 6.8 Projects 226 III Sorting and Searching 229 7 Internal Sorting 231 7.1 Sorting Terminology and Notation 232 7.2 Three Θ(n2 ) Sorting Algorithms 233 7.4 The Cost of Exchange Sorting 238 7.7 Binsort and Radix Sort 252 7.8 An Empirical Comparison of Sorting Algorithms 259 7.9 Lower Bounds for Sorting 261 7.12 Projects 269 Contents vii 8 File Processing and External Sorting 273 8.1 Primary versus Secondary Storage 273 8.1 Disk Drive Architecture 276 8.2 Disk Access Costs 280 8.3 Buffers and Buffer Pools 282 8.4 The Programmer’s View of Files 290 8.1 Simple Approaches to External Sorting 294 8.1 Searching Unsorted and Sorted Arrays 312 9.2 Self-Organizing Lists 317 9.3 Bit Vectors for Representing Sets 323 9.4 Analysis of Closed Hashing 339 9.3 Tree-based Indexing 358 10.1 B+ -Trees 368 viii Contents 10.8 Projects 377 IV Advanced Data Structures 379 11 Graphs 381 11.1 Terminology and Representations 382 11.1 Depth-First Search 393 11.2 Breadth-First Search 394 11.4 Shortest-Paths Problems 399 11.1 Single-Source Shortest Paths 400 11.5 Minimum-Cost Spanning Trees 402 11.8 Projects 412 12 Lists and Arrays Revisited 415 12.1 Dynamic Storage Allocation 424 12.2 Failure Policies and Garbage Collection 431 12.6 Projects 437 13 Advanced Tree Structures 439 13.1 Tries 439 Contents ix 13.1 The AVL Tree 445 13.2 The Splay Tree 447 13.3 Spatial Data Structures 450 13.2 The PR quadtree 457 13.3 Other Point Data Structures 461 13.4 Other Spatial Data Structures 463 13.6 Projects 465 V Theory of Algorithms 469 14 Analysis Techniques 471 14.1 Estimating Upper and Lower Bounds 477 14.3 Divide and Conquer Recurrences 482 14.4 Average-Case Analysis of Quicksort 484 14.6 Projects 493 15 Lower Bounds 495 15.1 Introduction to Lower Bounds Proofs 496 15.2 Lower Bounds on Searching Lists 498 15.1 Searching in Unsorted Lists 498 15.2 Searching in Sorted Lists 500 15.3 Finding the Maximum Value 501 15.4 Adversarial Lower Bounds Proofs 503 15.5 State Space Lower Bounds Proofs 506 15.6 Finding the ith Best Element 509 x Contents 15.10Projects 517 16 Patterns of Algorithms 519 16.1 The Knapsack Problem 521 16.2 All-Pairs Shortest Paths 523 16.1 Randomized algorithms for finding large values 525 16.2 Largest Common Factor 533 16.5 The Fast Fourier Transform 537 16.6 Projects 543 17 Limits to Computation 545 17.1 The Theory of N P-Completeness 553 17.3 Coping with N P-Complete Problems 562 17.2 The Halting Problem Is Unsolvable 569 17.6 Projects 574 Contents xi VI APPENDIX 577 A Utility Functions 579 Bibliography 581 Index 587 Preface We study data structures so that we can learn to write more efficient programs. But why must programs be efficient when new computers are faster every year? The reason is that our ambitions grow with our capabilities. Instead of rendering efficiency needs obsolete, the modern revolution in computing power and storage capability merely raises the efficiency stakes as we attempt more complex tasks.
The quest for program efficiency need not and should not conflict with sound design and clear coding. Creating efficient programs has little to do with “program- ming tricks” but rather is based on good organization of information and good al- gorithms. A programmer who has not mastered the basic principles of clear design is not likely to write efficient programs. Conversely, concerns related to develop- ment costs and maintainability should not be used as an excuse to justify inefficient performance.
Generality in design can and should be achieved without sacrificing performance, but this can only be done if the designer understands how to measure performance and does so as an integral part of the design and implementation pro- cess. Most computer science curricula recognize that good programming skills be- gin with a strong emphasis on fundamental software engineering principles. Then, once a programmer has learned the principles of clear program design and imple- mentation, the next step is to study the effects of data organization and algorithms on program efficiency. Approach: This book describes many techniques for representing data.
These techniques are presented within the context of the following principles: 1. Each data structure and each algorithm has costs and benefits. Practitioners need a thorough understanding of how to assess costs and benefits to be able to adapt to new design challenges. This requires an understanding of the principles of algorithm analysis, and also an appreciation for the significant effects of the physical medium employed (e., data stored on disk versus main memory).
Related to costs and benefits is the notion of tradeoffs. For example, it is quite common to reduce time requirements at the expense of an increase in space requirements, or vice versa. Programmers face tradeoff issues regularly in all xiii xiv Preface phases of software design and implementation, so the concept must become deeply ingrained. Programmers should know enough about common practice to avoid rein- venting the wheel.
Thus, programmers need to learn the commonly used data structures, their related algorithms, and the most frequently encountered design patterns found in programming. Data structures follow needs. Programmers must learn to assess application needs first, then find a data structure with matching capabilities. To do this requires competence in Principles 1, 2, and 3.
As I have taught data structures through the years, I have found that design issues have played an ever greater role in my courses. This can be traced through the various editions of this textbook by the increasing coverage for design patterns and generic interfaces. The first edition had no mention of design patterns. The second edition had limited coverage of a few example patterns, and introduced the dictionary ADT and comparator classes.
With the third edition, there is explicit coverage of some design patterns that are encountered when programming the basic data structures and algorithms covered in the book. Using the Book in Class: Data structures and algorithms textbooks tend to fall into one of two categories: teaching texts or encyclopedias. Books that attempt to do both usually fail at both. This book is intended as a teaching text.
I believe it is more important for a practitioner to understand the principles required to select or design the data structure that will best solve some problem than it is to memorize a lot of textbook implementations. Hence, I have designed this as a teaching text that covers most standard data structures, but not all. A few data structures that are not widely adopted are included to illustrate important principles. Some relatively new data structures that should become widely used in the future are included.
Within an undergraduate program, this textbook is designed for use in either an advanced lower division (sophomore or junior level) data structures course, or for a senior level algorithms course. New material has been added in the third edition to support its use in an algorithms course. Normally, this text would be used in a course beyond the standard freshman level “CS2” course that often serves as the initial introduction to data structures. Readers of this book should typically have two semesters of the equivalent of programming experience, including at least some exposure to C++.
Readers who are already familiar with recursion will have an advantage. Students of data structures will also benefit from having first completed a good course in Discrete Mathematics. Nonetheless, Chapter 2 attempts to give a reasonably complete survey of the prerequisite mathematical topics at the level necessary to understand their use in this book. Readers may wish to refer back to the appropriate sections as needed when encountering unfamiliar mathematical material.
Preface xv A sophomore-level class where students have only a little background in basic data structures or analysis (that is, background equivalent to what would be had from a traditional CS2 course) might cover Chapters 1-11 in detail, as well as se- lected topics from Chapter 13. That is how I use the book for my own sophomore- level class. Students with greater background might cover Chapter 1, skip most of Chapter 2 except for reference, briefly cover Chapters 3 and 4, and then cover chapters 5-12 in detail. Again, only certain topics from Chapter 13 might be cov- ered, depending on the programming assignments selected by the instructor.
A senior-level algorithms course would focus on Chapters 11 and 14-17. Chapter 13 is intended in part as a source for larger programming exercises. I recommend that all students taking a data structures course be required to im- plement some advanced tree structure, or another dynamic structure of comparable difficulty such as the skip list or sparse matrix representations of Chapter 12. None of these data structures are significantly more difficult to implement than the binary search tree, and any of them should be within a student’s ability after completing Chapter 5.
While I have attempted to arrange the presentation in an order that makes sense, instructors should feel free to rearrange the topics as they see fit. The book has been written so that once the reader has mastered Chapters 1-6, the remaining material has relatively few dependencies. Clearly, external sorting depends on understand- ing internal sorting and disk files.2 on the UNION/FIND algorithm is used in Kruskal’s Minimum-Cost Spanning Tree algorithm.2 on self- organizing lists mentions the buffer replacement schemes covered in Section 8. Chapter 14 draws on examples from throughout the book.