Data Structures and Algorithm Analysis - Virginia Tech

1 Data Structures and AlgorithmAnalysisEdition (C++ Version)Clifford A. ShafferDepartment of Computer ScienceVirginia TechBlacksburg, VA 24061 March 28, 2013 Update a list of changes, shaffer/ 2009-2012 by Clifford A. document is made freely available in PDF form for educational andother non-commercial use. You may make copies of this file andredistribute in electronic form without charge. You may extract portions ofthis document provided that the front page, including the title, author, andthis notice are included. Any commercial use of this document requires thewritten consent of the author. The author can be reached you wish to have a printed version of this document, print copies arepublished by Dover Publications( ).Further information about this text is available shaffer/Book/.ContentsPrefacexiiiI Preliminaries11 Data Structures and Philosophy of Data Need for Data and Data Types and Data , Algorithms, and Mathematical and and Proof by by Mathematical Algorithm , Worst, and Average Faster Computer, or a Faster Algorithm ?

2 The Running Time for a Speeding Up Your Empirical Further Projects90II Fundamental Data Structures934 Lists, Stacks, and List of List Linked of Array-Based and Linked of Array-Based and Linked Binary and Full Binary Tree Binary Tree Node Tree Tree Node Node Implementation for Complete Binary Search and Priority Coding Huffman Coding and Using Huffman in Huffman Non-Binary Tree Definitions and ADT for General Tree Tree Parent Pointer Tree of Left-Child/Right-Sibling Node Left-Child/Right-Sibling Tree Sorting and Searching2297 Internal Terminology and (n2)Sorting Cost of Exchange and Radix Empirical Comparison of Sorting Bounds for Further Projects269 Contentsvii8 File Processing and External versus Secondary Drive Access and Buffer Programmer s View of Approaches to External Unsorted and Sorted Vectors for Representing of Closed Linear Tree-based 2-3 B+ B-Tree Further Projects377IV Advanced Data Structures37911 Terminology and Graph Graph Depth-First Breadth-First Topological Shortest-Paths Single-Source Shortest minimum -Cost spanning Prim s Kruskal s Further Projects41212 Lists and Arrays Matrix Memory Dynamic Storage Failure Policies and Garbage Further Projects43713 Advanced Tree Balanced The AVL The Splay Spatial Data The K-D The PR

3 Other Point Data Other Spatial Data Further Projects465V Theory of Algorithms46914 Analysis Summation Recurrence Estimating Upper and Lower Expanding Divide and Conquer Average-Case Analysis of Amortized Further Projects49315 Lower Introduction to Lower Bounds Lower Bounds on Searching Searching in Unsorted Searching in Sorted Finding the Maximum Adversarial Lower Bounds State Space Lower Bounds Finding theith Best Optimal Further Patterns of Dynamic The Knapsack All-Pairs Shortest Randomized Randomized algorithms for finding large Skip Numerical Largest Common Matrix Random The Fast Fourier Further Projects54317 Limits to Hard The Theory Coping withNP-Complete Impossible The Halting Problem Is Further Projects574 ContentsxiVI APPENDIX577A Utility Functions579 Bibliography581 Index587 PrefaceWe study data Structures so that we can learn to write more efficient why must programs be efficient when new computers are faster every year?

4 The reason is that our ambitions grow with our capabilities. Instead of renderingefficiency needs obsolete, the modern revolution in computing power and storagecapability merely raises the efficiency stakes as we attempt more complex quest for program efficiency need not and should not conflict with sounddesign 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 designis not likely to write efficient programs. Conversely, concerns related to develop-ment costs and maintainability should not be used as an excuse to justify inefficientperformance. Generality in design can and should be achieved without sacrificingperformance, but this can only be done if the designer understands how to measureperformance and does so as an integral part of the design and implementation pro-cess.

5 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 algorithmson program :This book describes many techniques for representing data. Thesetechniques are presented within the context of the following data structure and each Algorithm has costs and benefits. Practitionersneed a thorough understanding of how to assess costs and benefits to be ableto adapt to new design challenges. This requires an understanding of theprinciples of Algorithm Analysis , and also an appreciation for the significanteffects of the physical medium employed ( , data stored on disk versusmain memory). to costs and benefits is the notion of tradeoffs. For example, it is quitecommon to reduce time requirements at the expense of an increase in spacerequirements, or vice versa.

6 Programmers face tradeoff issues regularly in allxiiixivPrefacephases of software design and implementation, so the concept must becomedeeply should know enough about common practice to avoid rein-venting the wheel. Thus, programmers need to learn the commonly useddata Structures , their related algorithms, and the most frequently encountereddesign patterns found in Structures follow needs. Programmers must learn to assess applicationneeds first, then find a data structure with matching capabilities. To do thisrequires competence in Principles 1, 2, and I have taught data Structures through the years, I have found that designissues have played an ever greater role in my courses. This can be traced throughthe various editions of this textbook by the increasing coverage for design patternsand generic interfaces. The first edition had no mention of design patterns. Thesecond edition had limited coverage of a few example patterns, and introduced thedictionary ADT and comparator classes.

7 With the third edition, there is explicitcoverage of some design patterns that are encountered when programming the basicdata Structures and algorithms covered in the the Book in Class:Data Structures and algorithms textbooks tend to fallinto one of two categories: teaching texts or encyclopedias. Books that attempt todo both usually fail at both. This book is intended as a teaching text. I believe it ismore important for a practitioner to understand the principles required to select ordesign the data structure that will best solve some problem than it is to memorize alot of textbook implementations. Hence, I have designed this as a teaching text thatcovers most standard data Structures , but not all. A few data Structures that are notwidely adopted are included to illustrate important principles. Some relatively newdata Structures that should become widely used in the future are an undergraduate program, this textbook is designed for use in either anadvanced lower division (sophomore or junior level) data Structures course, or fora senior level algorithms course.

8 New material has been added in the third editionto support its use in an algorithms course. Normally, this text would be used in acourse beyond the standard freshman level CS2 course that often serves as theinitial introduction to data Structures . Readers of this book should typically havetwo semesters of the equivalent of programming experience, including at least someexposure toC++. Readers who are already familiar with recursion will have anadvantage. Students of data Structures will also benefit from having first completeda good course in Discrete Mathematics. Nonetheless, Chapter 2 attempts to givea reasonably complete survey of the prerequisite mathematical topics at the levelnecessary to understand their use in this book. Readers may wish to refer backto the appropriate sections as needed when encountering unfamiliar sophomore-level class where students have only a little background in basicdata Structures or Analysis (that is, background equivalent to what would be hadfrom a traditional CS2 course) might cover Chapters 1-11 in detail, as well as se-lected topics from Chapter 13.

9 That is how I use the book for my own sophomore-level class. Students with greater background might cover Chapter 1, skip mostof Chapter 2 except for reference, briefly cover Chapters 3 and 4, and then coverchapters 5-12 in detail. Again, only certain topics from Chapter 13 might be cov-ered, depending on the programming assignments selected by the instructor. Asenior-level algorithms course would focus on Chapters 11 and 13 is intended in part as a source for larger programming recommend that all students taking a data Structures course be required to im-plement some advanced tree structure, or another dynamic structure of comparabledifficulty such as the skip list or sparse matrix representations of Chapter 12. Noneof these data Structures are significantly more difficult to implement than the binarysearch tree, and any of them should be within a student s ability after completingChapter 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.

10 The book has beenwritten so that once the reader has mastered Chapters 1-6, the remaining materialhas relatively few dependencies. Clearly, external sorting depends on understand-ing internal sorting and disk files. Section on the UNION/FIND Algorithm isused in Kruskal s minimum -Cost spanning Tree Algorithm . Section on self-organizing lists mentions the buffer replacement schemes covered in Section 14 draws on examples from throughout the book. Section relies onknowledge of graphs. Otherwise, most topics depend only on material presentedearlier within the same chapters end with a section entitled Further Reading. These sectionsare not comprehensive lists of references on the topics presented. Rather, I includebooks and articles that, in my opinion, may prove exceptionally informative orentertaining to the reader. In some cases I include references to works that shouldbecome familiar to any well-rounded computer ofC++:The programming examples are written inC++, but I do not wish todiscourage those unfamiliar withC++from reading this book.