A Practical Introduction To Data Structures And Algorithm .
A Practical Introduction toData Structures and AlgorithmAnalysisThird Edition (Java)Clifford A. ShafferDepartment of Computer ScienceVirginia TechBlacksburg, VA 24061April 16, 2009Copyright c 2008 by Clifford A. Shaffer.This 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 publisher.
ContentsPrefacexiiiIPreliminaries11Data Structures and Algorithms1.1 A Philosophy of Data Structures1.1.1 The Need for Data Structures1.1.2 Costs and Benefits1.2 Abstract Data Types and Data Structures1.3 Design Patterns1.3.1 Flyweight1.3.2 Visitor1.3.3 Composite1.3.4 Strategy1.4 Problems, Algorithms, and Programs1.5 Further Reading1.6 Exercises3446812131415161719212Mathematical Preliminaries2.1 Sets and Relations2.2 Miscellaneous Notation2.3 Logarithms2.4 Summations and Recurrences2525293133iii
ivContents2.52.62.72.82.93II4RecursionMathematical Proof Techniques2.6.1 Direct Proof2.6.2 Proof by Contradiction2.6.3 Proof by Mathematical InductionEstimatingFurther ReadingExercisesAlgorithm Analysis3.1 Introduction3.2 Best, Worst, and Average Cases3.3 A Faster Computer, or a Faster Algorithm?3.4 Asymptotic Analysis3.4.1 Upper Bounds3.4.2 Lower Bounds3.4.3 Θ Notation3.4.4 Simplifying Rules3.4.5 Classifying Functions3.5 Calculating the Running Time for a Program3.6 Analyzing Problems3.7 Common Misunderstandings3.8 Multiple Parameters3.9 Space Bounds3.10 Speeding Up Your Programs3.11 Empirical Analysis3.12 Further Reading3.13 Exercises3.14 ProjectsFundamental Data StructuresLists, Stacks, and 8486899091959799
vContents4.14.24.34.44.54.64.75Lists4.1.1 Array-Based List Implementation4.1.2 Linked Lists4.1.3 Comparison of List Implementations4.1.4 Element Implementations4.1.5 Doubly Linked ListsStacks4.2.1 Array-Based Stacks4.2.2 Linked Stacks4.2.3 Comparison of Array-Based and Linked Stacks4.2.4 Implementing RecursionQueues4.3.1 Array-Based Queues4.3.2 Linked Queues4.3.3 Comparison of Array-Based and Linked QueuesDictionaries and ComparatorsFurther ReadingExercisesProjectsBinary Trees5.1 Definitions and Properties5.1.1 The Full Binary Tree Theorem5.1.2 A Binary Tree Node ADT5.2 Binary Tree Traversals5.3 Binary Tree Node Implementations5.3.1 Pointer-Based Node Implementations5.3.2 Space Requirements5.3.3 Array Implementation for Complete Binary Trees5.4 Binary Search Trees5.5 Heaps and Priority Queues5.6 Huffman Coding Trees5.6.1 Building Huffman Coding 9
viContents5.75.85.96III75.6.2 Assigning and Using Huffman CodesFurther ReadingExercisesProjectsNon-Binary Trees6.1 General Tree Definitions and Terminology6.1.1 An ADT for General Tree Nodes6.1.2 General Tree Traversals6.2 The Parent Pointer Implementation6.3 General Tree Implementations6.3.1 List of Children6.3.2 The Left-Child/Right-Sibling Implementation6.3.3 Dynamic Node Implementations6.3.4 Dynamic “Left-Child/Right-Sibling” Implementation6.4 K-ary Trees6.5 Sequential Tree Implementations6.6 Further Reading6.7 Exercises6.8 ProjectsSorting and SearchingInternal Sorting7.1 Sorting Terminology and Notation7.2 Three Θ(n2 ) Sorting Algorithms7.2.1 Insertion Sort7.2.2 Bubble Sort7.2.3 Selection Sort7.2.4 The Cost of Exchange Sorting7.3 Shellsort7.4 Mergesort7.5 0221223226226230233235236237238240241243244246249
viiContents7.67.77.87.97.107.117.12HeapsortBinsort and Radix SortAn Empirical Comparison of Sorting AlgorithmsLower Bounds for SortingFurther ReadingExercisesProjects2562592652672712722758File Processing and External Sorting8.1 Primary versus Secondary Storage8.2 Disk Drives8.2.1 Disk Drive Architecture8.2.2 Disk Access Costs8.3 Buffers and Buffer Pools8.4 The Programmer’s View of Files8.5 External Sorting8.5.1 Simple Approaches to External Sorting8.5.2 Replacement Selection8.5.3 Multiway Merging8.6 Further Reading8.7 Exercises8.8 9Searching9.1 Searching Unsorted and Sorted Arrays9.2 Self-Organizing Lists9.3 Bit Vectors for Representing Sets9.4 Hashing9.4.1 Hash Functions9.4.2 Open Hashing9.4.3 Closed Hashing9.4.4 Analysis of Closed Hashing9.4.5 Deletion317318324329330331336337346350
viiiContents9.59.69.7Further ReadingExercisesProjects35135235510 Indexing10.1 Linear Indexing10.2 ISAM10.3 Tree-based Indexing10.4 2-3 Trees10.5 B-Trees10.5.1 B -Trees10.5.2 B-Tree Analysis10.6 Further Reading10.7 Exercises10.8 nced Data Structures11 Graphs11.1 Terminology and Representations11.2 Graph Implementations11.3 Graph Traversals11.3.1 Depth-First Search11.3.2 Breadth-First Search11.3.3 Topological Sort11.4 Shortest-Paths Problems11.4.1 Single-Source Shortest Paths11.5 Minimum-Cost Spanning Trees11.5.1 Prim’s Algorithm11.5.2 Kruskal’s Algorithm11.6 Further Reading11.7 Exercises11.8 420
Contentsix12 Lists and Arrays Revisited12.1 Multilists12.2 Matrix Representations12.3 Memory Management12.3.1 Dynamic Storage Allocation12.3.2 Failure Policies and Garbage Collection12.4 Further Reading12.5 Exercises12.6 Projects42342342743043143844344444513 Advanced Tree Structures13.1 Tries13.2 Balanced Trees13.2.1 The AVL Tree13.2.2 The Splay Tree13.3 Spatial Data Structures13.3.1 The K-D Tree13.3.2 The PR quadtree13.3.3 Other Point Data Structures13.3.4 Other Spatial Data Structures13.4 Further Reading13.5 Exercises13.6 9Theory of Algorithms14 Analysis Techniques14.1 Summation Techniques14.2 Recurrence Relations14.2.1 Estimating Upper and Lower Bounds14.2.2 Expanding Recurrences14.2.3 Divide and Conquer Recurrences14.2.4 Average-Case Analysis of Quicksort481482487487491492495
xContents14.314.414.514.6Amortized AnalysisFurther ReadingExercisesProjects49649950050415 Lower Bounds15.1 Introduction to Lower Bounds Proofs15.2 Lower Bounds on Searching Lists15.2.1 Searching in Unsorted Lists15.2.2 Searching in Sorted Lists15.3 Finding the Maximum Value15.4 Adversarial Lower Bounds Proofs15.5 State Space Lower Bounds Proofs15.6 Finding the ith Best Element15.7 Optimal Sorting15.8 Further Reading15.9 2252452552716 Patterns of Algorithms16.1 Greedy Algorithms16.2 Dynamic Programming16.2.1 Knapsack Problem16.2.2 All-Pairs Shortest Paths16.3 Randomized Algorithms16.3.1 Skip Lists16.4 Numerical Algorithms16.4.1 Exponentiation16.4.2 Largest Common Factor16.4.3 Matrix Multiplication16.4.4 Random Numbers16.4.5 Fast Fourier Transform16.5 Further Reading529529530531532534536541542543543546546551
Contents16.6 Exercises16.7 Projectsxi55155217 Limits to Computation17.1 Reductions17.2 Hard Problems17.2.1 The Theory of N P-Completeness17.2.2 N P-Completeness Proofs17.2.3 Coping with N P-Complete Problems17.3 Impossible Problems17.3.1 Uncountability17.3.2 The Halting Problem Is Unsolvable17.4 Further Reading17.5 Exercises17.6 graphy585Index591
PrefaceWe study data structures so that we can learn to write more efficient programs. Butwhy must programs be efficient when new computers are faster every year? Thereason 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 computerize more complex tasks.The quest for program efficiency need not and should not conflict with sounddesign and clear coding. Creating efficient programs has little to do with “programming tricks” but rather is based on good organization of information and good algorithms. 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. 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 fundamental 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 efficiency.Approach: This book describes many techniques for representing data. Thesetechniques are presented within the context of the following principles:1. Each 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 (e.g., data stored on disk versusmain memory).xiii
xivPreface2. Related 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 ingrained.3. Programmers should know enough about common practice to avoid reinventing the wheel. Thus, programmers need to learn the commonly useddata structures, their related algorithms, and the most frequently encountereddesign patterns found in programming.4. Data 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 3.As 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 book.Using 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 included.Within 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. 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 initial introduction to data structures. Readers of this book should have programmingexperience, typically two semesters or the equivalent of a structured programminglanguage such as Pascal or C, and including at least some exposure to Java. Readers who are already familiar with recursion will have an advantage. Students of
Prefacexvdata structures will also benefit from having first completed a good course in Discrete 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. Readers may wish to refer back to the appropriate sectionsas needed when encountering unfamiliar mathematical material.A 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 selected topics from Chapter 13. That is how I use the book for my own sophomorelevel 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 covered, depending on the programming assignments selected by the instructor. Asenior-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 implement 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 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 beenwritten so that once the reader has mastered Chapters 1-6, the remaining materialhas relatively few dependencies. Clearly, external sorting depends on understanding internal sorting and disk files. Section 6.2 on the UNION/FIND algorithm isused in Kruskal’s Minimum-Cost Spanning Tree algorithm. Section 9.2 on selforganizing lists mentions the buffer replacement schemes covered in Section 8.3.Chapter 14 draws on examples from throughout the book. Section 17.2 relies onknowledge of graphs. Otherwise, most topics depend only on material presentedearlier within the same chapter.Most 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 scientist.Use of Java: The programming examples are written in JavaTM . As with anyprogramming language, Java has both advantages and disadvantages. Java is a
xviPrefacesmall language. There usually is only one way to do something, and this has thehappy tendency of encouraging a programmer toward clarity when used correctly.In this respect, it is superior to C or C . Java serves nicely for defining andusing most traditional data structures such as lists and trees. On the other hand,Java is quite poor when used to do file processing, being both cumbersome andinefficient. It is also a poor language when fine control of memory is required. Asan example, applications requiring memory management, such as those discussedin Section 12.3, are difficult to write in Java. Since I wish to stick to a singlelanguage throughout the text, like any programmer I must take the bad along withthe good. The most important issue is to get the ideas across, whether or not thoseideas are natural to a particular language of discourse. Most programmers willuse a variety of programming languages throughout their career, and the conceptsdescribed in this book should prove useful in a variety of circumstances.I do not wish to discourage those unfamiliar with Java from reading this book.I have attempted to make the examples as clear as possible while maintaining theadvantages of Java. Java is used here strictly as a tool to illustrate data structuresconcepts. Fortunately, Java is an easy language for C or Pascal programmers to readwith a minimal amount of study of the syntax related to object-oriented programming. In particular, I make use of Java’s support for hiding implementation details,including features such as classes, private class members, and interfaces. Thesefeatures of the language support the crucial concept of separating logical design, asembodied in the abstract data type, from physical implementation as embodied inthe data structure.I make no attempt to teach Java within the text. An Appendix is providedthat describes the Java syntax and concepts necessary to understand the programexamples. I also provide the actual Java code used in the text through anonymousFTP.Inheritance, a key feature of object-oriented programming, is used only sparingly in the code examples. Inheritance is an important tool that helps programmersavoid duplication, and thus minimize bugs. From a pedagogical standpoint, however, inheritance often makes code examples harder to understand since it tends tospread the description for one logical unit among several classes. Thus, some ofmy class definitions for objects such as tree or list nodes do not take full advantageof possible inheritance from earlier code examples. This does not mean that a programmer should do likewise. Avoiding code duplication and minimizing errors areimportant goals. Treat the programming examples as illustrations of data structureprinciples, but do not copy them directly into your own programs.
PrefacexviiMy Java implementations serve to provide concrete illustrations of data structure principles. They are not meant to be a series of commercial-quality Javaclass implementations. The code examples provide less parameter checking thanis sound programming practice for commercial programmers. Some parameterchecking is included in the form of calls to methods in class Assert. Thesemethods are modeled after the C standard library function assert. MethodAssert.notFalse takes a Boolean expression. If this expression evaluates tofalse, then the program terminates immediately. Method Assert.notNulltakes a reference to class Object, and terminates the program if the value of thereference is null. (To be precise, these functions throw an IllegalArgumentException, which typically results in terminating the program unless the programmer takes action to handle the exception.) Terminating a program when afunction receives a bad parameter is generally considered undesirable in real programs, but is quite adequate for understanding how a data structure is meant to operate. In real programming applications, Java’s exception handling features shouldbe used to deal with input data errors.I make a distinction in the text between “Java implementations” and “pseudocode.” Code labeled as a Java implementation has actually been compiled andtested on one or more Java compilers. Pseudocode examples often conform closelyto Java syntax, but typically contain one or more lines of higher level description.Pseudocode is used where I perceived a greater pedagogical advantage to a simpler,but less precise, description.Exercises and Projects: Proper implementation and anaysis of data structurescannot be learned simply by reading a book. You must practice by implementingreal programs, constantly comparing different techniques to see what really worksbest in a given situation.One of the most important aspects of a course in data structures is that it iswhere students really learn to program using pointers and dynamic memory allocation, by implementing data structures such as linked lists and trees. Its also wherestudents truly learn recursion. In our curriculum, this is the first course wherestudents do signific
Apr 16, 2009 · 1 Data Structures and Algorithms 3 1.1 A Philosophy of Data Structures 4 1.1.1 The Need for Data Structures 4 1.1.2 Costs and Benefits 6 1.2 Abstract Data Types and Data Structures 8 1.3 Design Patterns 12 1.3.1 Flyweight 13 1.3.2 Visitor 14 1.3.3 Composite 15 1.3.4 Strategy 16 1.4 Problems, Algorith
work/products (Beading, Candles, Carving, Food Products, Soap, Weaving, etc.) ⃝I understand that if my work contains Indigenous visual representation that it is a reflection of the Indigenous culture of my native region. ⃝To the best of my knowledge, my work/products fall within Craft Council standards and expectations with respect to
akuntansi musyarakah (sak no 106) Ayat tentang Musyarakah (Q.S. 39; 29) لًََّز ãَ åِاَ óِ îَخظَْ ó Þَْ ë Þٍجُزَِ ß ا äًَّ àَط لًَّجُرَ íَ åَ îظُِ Ûاَش
Collectively make tawbah to Allāh S so that you may acquire falāḥ [of this world and the Hereafter]. (24:31) The one who repents also becomes the beloved of Allāh S, Âَْ Èِﺑاﻮَّﺘﻟاَّﺐُّ ßُِ çﻪَّٰﻠﻟانَّاِ Verily, Allāh S loves those who are most repenting. (2:22
neric Data Modeling and Data Model Patterns in order to build data models for crime data which allows complete and consistent integration of crime data in Data Warehouses. Keywords-Relational Data Modeling; Data Warehouse; Generic Data Modeling; Police Data, Data Model Pattern existing data sets as well as new kinds of data I. INTRODUCTION The research about Business Intelligence and Data
Title: ER/Studio Data Architect 8.5.3 Evaluation Guide, 2nd Edition Author: Embarcadero Technologies, Inc. Keywords: CA ERwin data model software Data Modeler data modeler tools data modelers data modeling data modeling software data modeling tool data modeling tools data modeling with erwin data modelings data modeller data modelling software data modelling tool data modelling
Practical Numeracy is a course run from S1-S3. The Practical Numeracy course will help to develop the numeracy skills you will use in your practical STEM subjects. The numeracy skills you will use in Practical Numeracy are the same skills you will be using in all your other STEM subjects. These are called transferable skills.
City Colleges of Chicago School of Nursing Practical Nursing Program is a one-year Advanced Certificate program, preparing individuals to function in the practical nurse role. Individuals completing the practical nursing program meet the education requirements and are eligible to sit for the NCLEX-PN exam to become a licensed practical nurse (LPN).
Practical Nursing Program Practical Nursing is a 2 year program Application window opens January 3rd, 2023 - April 14th, 2023. (No senior discount available) Practical Nursing (PN) I & II - 2,700 Practical Nursing semester I & semester II is the first year of the two-year Practical Nursing pathway and is approved by the Virginia Board of .
