A Practical Introduction to Data Structures and Algorithm ...

1 A Practical Introduction toData Structures and AlgorithmAnalysisThird Edition (C++ Version)Clifford A. ShafferDepartment of Computer ScienceVirginia TechBlacksburg, VA 24061 January 19, 2010 Copyrightc 2009-2010 by Clifford A. document is made freely available for educational and othernon-commercial may make copies of this file and redistribute it without may extract portions of this document provided that the front page,including the title, author, and this notice are commercial use of this document requires the written consent of author can be reached 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 Projects95II Fundamental data Structures974 Lists, Stacks, and List of List Linked of Array-Based and Linked of Array-Based and Linked and 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 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 Searching2417 Internal Terminology and (n2)Sorting Cost of Exchange and Radix Empirical Comparison of Sorting Bounds for Further Projects2838 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 Projects397IV Advanced data Structures39911 Terminology and Graph Graph Depth-First Breadth-First Topological Shortest-Paths Single-Source Shortest Minimum-Cost Spanning Prim s Kruskal s Further Projects434 Contentsix12 Lists and Arrays Matrix Memory Dynamic Storage Failure Policies and

3 Garbage Further Projects46013 Advanced Tree Balanced The AVL The Splay Spatial data The K-D The PR Other Point data Other Spatial data Further Projects489V Theory of Algorithms49314 Analysis Summation Recurrence Estimating Upper and Lower Expanding Divide and Conquer Average-Case Analysis of Amortized Further Projects51815 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 Greedy Dynamic Knapsack All-Pairs Shortest Randomized Skip Numerical Largest Common Matrix Random Fast Fourier Further Projects56617 Limits to Hard The Theory Coping withNP-Complete Impossible The Halting Problem Is Further Projects598VI APPENDIX599A Utility Functions601 Bibliography603 Index609 PrefaceWe study data Structures so that we can learn to write more efficient programs.

4 Butwhy must programs be efficient when new computers are faster every year? Thereason is that our ambitions grow with our capabilities. Instead of rendering effi-ciency needs obsolete, the modern revolution in computing power and storage ca-pability merely raises the efficiency stakes as we computerize 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, software engineering cannotbe used as an excuse to justify inefficient performance.

5 Generality in design canand should be achieved without sacrificing performance, but this can only be doneif the designer understands how to measure performance and does so as an integralpart of the design and implementation process. Most computer science curricularecognize that good programming skills begin with a strong emphasis on funda-mental software engineering principles. Then, once a programmer has learned theprinciples of clear program design and implementation, the next step is to study theeffects of data organization and algorithms on 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.

6 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. Programmers face tradeoff issues regularly in allphases 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.

7 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 introducedthe dictionary ADT and comparator classes. 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.

8 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.

9 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 the ini-tial Introduction to data Structures . Readers of this book should have programmingexperience, typically two semesters or the equivalent of a structured programminglanguage such as Pascal orC, and including at least some exposure toC++. Read-ers who are already familiar with recursion will have an advantage. Students ofPrefacexvdata Structures will also benefit from having first completed a good course in Dis-crete Mathematics. Nonetheless, Chapter 2 attempts to give a reasonably completesurvey of the prerequisite mathematical topics at the level necessary to understandtheir use in this book.

10 Readers may wish to refer back to the appropriate sectionsas needed when encountering unfamiliar mathematical 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. 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.