A Practical Introduction to Data Structures and Algorithm ...

1 A Practical Introduction toData Structures and AlgorithmAnalysisThird Edition (Java)Clifford A. ShafferDepartment of Computer ScienceVirginia TechBlacksburg, VA 24061 April 16, 2009 Copyrightc 2008 by Clifford A. document is the draft of a book to be published by Prentice Halland may not be duplicated without the express written consentof either the author or a representative of the Preliminaries11 Data Structures and A Philosophy of Data The Need for Data Costs and Abstract Data Types and Data Design Problems, Algorithms, and Further Exercises212 Mathematical Sets and Miscellaneous Summations and Mathematical Proof Direct Proof by Proof by Mathematical Further Exercises503 Algorithm Best, Worst, and Average A Faster Computer, or a Faster Algorithm ?

2 Asymptotic Upper Lower Simplifying Classifying Calculating the Running Time for a Analyzing Common Multiple Space Speeding Up Your Empirical Further Projects95II Fundamental Data Structures974 Lists, Stacks, and Array-Based List Linked Comparison of List Element Doubly Linked Array-Based Linked Comparison of Array-Based and Linked Implementing Array-Based Linked Comparison of Array-Based and Linked Dictionaries and Further Projects1505 Binary Definitions and The Full Binary Tree A Binary Tree Node Binary Tree Binary Tree Node Pointer-Based Node Space Array Implementation for Complete Binary Binary Search Heaps and Priority Huffman Coding Building Huffman Coding Assigning and Using Huffman Further Projects2026 Non-Binary General Tree Definitions and An ADT for General Tree General Tree The

3 Parent Pointer General Tree List of The Left-Child/Right-Sibling Dynamic Node Dynamic Left-Child/Right-Sibling Sequential Tree Further Projects230 III Sorting and Searching2337 Internal Sorting Terminology and Three (n2)Sorting Insertion Bubble Selection The Cost of Exchange Binsort and Radix An Empirical Comparison of Sorting Lower Bounds for Further Projects2758 File Processing and External Primary versus Secondary Disk Disk Drive Disk Access Buffers and Buffer The Programmer s View of External Simple Approaches to External Replacement Multiway Further Projects3159 Searching Unsorted and Sorted Self-Organizing Bit Vectors for Representing Hash Open Closed Analysis of Closed Further Projects35510 Linear Tree-based 2-3 B+ B-Tree Further Projects384IV Advanced Data Structures38711

4 Terminology and Graph Graph Depth-First Breadth-First Topological Shortest-Paths Single-Source Shortest minimum -Cost spanning Prim s Kruskal s Further Projects420 Contentsix12 Lists and Arrays Matrix Memory Dynamic Storage Failure Policies and Garbage Further Projects44513 Advanced Tree Balanced The AVL The Splay Spatial Data The K-D The PR Other Point Data Other Spatial Data Further Projects475V Theory of Algorithms47914 Analysis Summation Recurrence Estimating Upper and Lower Expanding Divide and Conquer Average-Case Analysis of Amortized Further Projects50415 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 Projects55217 Limits to Hard The Theory Coping withNP-Complete Impossible The Halting Problem Is Further Projects584 Bibliography585 Index591 PrefaceWe study data Structures so that we can learn to write more efficient programs.

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

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

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

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

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

10 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 to Java. 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.