کتاب Data Structures and Algorithms in Java
کتاب Data Structures and Algorithms in Java ویرایش ششم، چاپ سال 2014
توضیحات
بی‌شک یکی از بهترین کتاب‌های حوزه ساختمان داده و الگوریتم کتاب Data Structures and Algorithms in Java می‌باشد که با تلاش Michael T. Goodrich و همکارانش نوشته و به چاپ رسیده است. این کتاب با بررسی مطالب مختلف و توضیحات کامل نسبت به موضوعات، مطالب را بسیار شفاف و قابل درک می‌کند که از این رو درک عمیقی به ما درباره ساختمان داده و الگوریتم می‌دهد. این درک به ما کمک می‌کند که کدهای بسیار بهینه‌تر و کامل‌تری را ارائه دهیم و امروزه، مشاغل زیادی به برنامه نویسانی با این قابلیت کد زدن بهینه نیاز دارند. از این رو این کتاب بی‌نظیر می‌تواند آینده کاری شما را تغییر دهد.
پیش‌نیازها :
- دانش زبان انگلیسی
- آشنایی با یک زبان برنامه نویسی سطح بالا (High-level) مانند : java, python, C++, C{ به گفته کتاب آشنایی با زبان جاوا الزامی نیست. ولی باید به مطالب زیر احاطه داشته باشد:including :
• Variables and expressions
• Methods (also known as functions or procedures)
• Decision structures (such as if-statements and switch-statements)
• Iteration structures (for-loops and while-loops) } - ریاضیات دبیرستان (high-school mathematics)
- آشنایی با طراحی شئی‌گرا و ساختار پیوند
مشخصات کتاب Data Structures and Algorithms in Java :
زبان : انگلیسی
رنگ صفحات : رنگی
تعداد صفحات : 738
نویسندگان : Michael T. Goodrich، Roberto Tamassia، Michael H. Goldwasser
سال انتشار : 2014
نسخه : ویرایش ششم
فرمت فایل دانلودی : PDF
نکته : این کتاب هایلایت شده می‌باشد و نکاتی در داخل این کتاب هایلایت شده است ولی چیزی داخل کتاب نوشته نشده است ( نمونه صفحه‌ای در گالری محصول آمده است ).
جهت دانلود کتاب میتوانید از لینک زیر اقدام نمایید:
فصل‌ها و سرفصل‌ها :
1 Java Primer 1
1.1 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Base Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Classes and Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Creating and Using Objects . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Defining a Class . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Strings, Wrappers, Arrays, and Enum Types . . . . . . . . . . . . . 17
1.4 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4.1 Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4.2 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.3 Type Conversions . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.5 Control Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.5.1 The If and Switch Statements . . . . . . . . . . . . . . . . . . 30
1.5.2 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.5.3 Explicit Control-Flow Statements . . . . . . . . . . . . . . . . . 37
1.6 Simple Input and Output . . . . . . . . . . . . . . . . . . . . . . . . 38
1.7 An Example Program . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.8 Packages and Imports . . . . . . . . . . . . . . . . . . . . . . . . . . 44
1.9 Software Development . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.9.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.9.2 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.9.3 Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
1.9.4 Documentation and Style . . . . . . . . . . . . . . . . . . . . . 50
1.9.5 Testing and Debugging . . . . . . . . . . . . . . . . . . . . . . 53
1.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2 Object-Oriented Design 59
2.1 Goals, Principles, and Patterns . . . . . . . . . . . . . . . . . . . . 60
2.1.1 Object-Oriented Design Goals . . . . . . . . . . . . . . . . . . 60
2.1.2 Object-Oriented Design Principles . . . . . . . . . . . . . . . . 61
2.1.3 Design Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.2 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.2.1 Extending the CreditCard Class . . . . . . . . . . . . . . . . . . 65
2.2.2 Polymorphism and Dynamic Dispatch . . . . . . . . . . . . . . 68
2.2.3 Inheritance Hierarchies . . . . . . . . . . . . . . . . . . . . . . 69
2.3 Interfaces and Abstract Classes . . . . . . . . . . . . . . . . . . . . 76
2.3.1 Interfaces in Java . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.3.2 Multiple Inheritance for Interfaces . . . . . . . . . . . . . . . . 79
2.3.3 Abstract Classes . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.4 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
2.4.1 Catching Exceptions . . . . . . . . . . . . . . . . . . . . . . . . 82
2.4.2 Throwing Exceptions . . . . . . . . . . . . . . . . . . . . . . . 85
2.4.3 Java’s Exception Hierarchy . . . . . . . . . . . . . . . . . . . . 86
2.5 Casting and Generics . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2.5.1 Casting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2.5.2 Generics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
2.6 Nested Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3 Fundamental Data Structures 103
3.1 Using Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.1.1 Storing Game Entries in an Array . . . . . . . . . . . . . . . . . 104
3.1.2 Sorting an Array . . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.1.3 java.util Methods for Arrays and Random Numbers . . . . . . . 112
3.1.4 Simple Cryptography with Character Arrays . . . . . . . . . . . 115
3.1.5 Two-Dimensional Arrays and Positional Games . . . . . . . . . 118
3.2 Singly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
3.2.1 Implementing a Singly Linked List Class . . . . . . . . . . . . . 126
3.3 Circularly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . 128
3.3.1 Round-Robin Scheduling . . . . . . . . . . . . . . . . . . . . . 128
3.3.2 Designing and Implementing a Circularly Linked List . . . . . . 129
3.4 Doubly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
3.4.1 Implementing a Doubly Linked List Class . . . . . . . . . . . . 135
3.5 Equivalence Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.5.1 Equivalence Testing with Arrays . . . . . . . . . . . . . . . . . 139
3.5.2 Equivalence Testing with Linked Lists . . . . . . . . . . . . . . 140
3.6 Cloning Data Structures . . . . . . . . . . . . . . . . . . . . . . . . 141
3.6.1 Cloning Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3.6.2 Cloning Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . 144
3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4 Algorithm Analysis 149
4.1 Experimental Studies . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.1.1 Moving Beyond Experimental Analysis . . . . . . . . . . . . . . 154
4.2 The Seven Functions Used in This Book . . . . . . . . . . . . . . . 156
4.2.1 Comparing Growth Rates . . . . . . . . . . . . . . . . . . . . . 163
4.3 Asymptotic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.3.1 The “Big-Oh” Notation . . . . . . . . . . . . . . . . . . . . . . 164
4.3.2 Comparative Analysis . . . . . . . . . . . . . . . . . . . . . . . 168
4.3.3 Examples of Algorithm Analysis . . . . . . . . . . . . . . . . . 170
4.4 Simple Justification Techniques . . . . . . . . . . . . . . . . . . . . 178
4.4.1 By Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
4.4.2 The “Contra” Attack . . . . . . . . . . . . . . . . . . . . . . . 178
4.4.3 Induction and Loop Invariants . . . . . . . . . . . . . . . . . . 179
4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
5 Recursion 189
5.1 Illustrative Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 191
5.1.1 The Factorial Function . . . . . . . . . . . . . . . . . . . . . . 191
5.1.2 Drawing an English Ruler . . . . . . . . . . . . . . . . . . . . . 193
5.1.3 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
5.1.4 File Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
5.2 Analyzing Recursive Algorithms . . . . . . . . . . . . . . . . . . . . 202
5.3 Further Examples of Recursion . . . . . . . . . . . . . . . . . . . . . 206
5.3.1 Linear Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . 206
5.3.2 Binary Recursion . . . . . . . . . . . . . . . . . . . . . . . . . 211
5.3.3 Multiple Recursion . . . . . . . . . . . . . . . . . . . . . . . . 212
5.4 Designing Recursive Algorithms . . . . . . . . . . . . . . . . . . . . 214
5.5 Recursion Run Amok . . . . . . . . . . . . . . . . . . . . . . . . . . 215
5.5.1 Maximum Recursive Depth in Java . . . . . . . . . . . . . . . . 218
5.6 Eliminating Tail Recursion . . . . . . . . . . . . . . . . . . . . . . . 219
5.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
6 Stacks, Queues, and Deques 225
6.1 Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
6.1.1 The Stack Abstract Data Type . . . . . . . . . . . . . . . . . . 227
6.1.2 A Simple Array-Based Stack Implementation . . . . . . . . . . 230
6.1.3 Implementing a Stack with a Singly Linked List . . . . . . . . . 233
6.1.4 Reversing an Array Using a Stack . . . . . . . . . . . . . . . . 234
6.1.5 Matching Parentheses and HTML Tags . . . . . . . . . . . . . 235
6.2 Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
6.2.1 The Queue Abstract Data Type . . . . . . . . . . . . . . . . . 239
6.2.2 Array-Based Queue Implementation . . . . . . . . . . . . . . . 241
6.2.3 Implementing a Queue with a Singly Linked List . . . . . . . . . 245
6.2.4 A Circular Queue . . . . . . . . . . . . . . . . . . . . . . . . . 246
6.3 Double-Ended Queues . . . . . . . . . . . . . . . . . . . . . . . . . . 248
6.3.1 The Deque Abstract Data Type . . . . . . . . . . . . . . . . . 248
6.3.2 Implementing a Deque . . . . . . . . . . . . . . . . . . . . . . 250
6.3.3 Deques in the Java Collections Framework . . . . . . . . . . . . 251
6.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
7 List and Iterator ADTs 257
7.1 The List ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
7.2 Array Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
7.2.1 Dynamic Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . 263
7.2.2 Implementing a Dynamic Array . . . . . . . . . . . . . . . . . . 264
7.2.3 Amortized Analysis of Dynamic Arrays . . . . . . . . . . . . . . 265
7.2.4 Java’s StringBuilder class . . . . . . . . . . . . . . . . . . . . . 269
7.3 Positional Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
7.3.1 Positions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
7.3.2 The Positional List Abstract Data Type . . . . . . . . . . . . . 272
7.3.3 Doubly Linked List Implementation . . . . . . . . . . . . . . . . 276
7.4 Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
7.4.1 The Iterable Interface and Java’s For-Each Loop . . . . . . . . 283
7.4.2 Implementing Iterators . . . . . . . . . . . . . . . . . . . . . . 284
7.5 The Java Collections Framework . . . . . . . . . . . . . . . . . . . 288
7.5.1 List Iterators in Java . . . . . . . . . . . . . . . . . . . . . . . 289
7.5.2 Comparison to Our Positional List ADT . . . . . . . . . . . . . 290
7.5.3 List-Based Algorithms in the Java Collections Framework . . . . 291
7.6 Sorting a Positional List . . . . . . . . . . . . . . . . . . . . . . . . 293
7.7 Case Study: Maintaining Access Frequencies . . . . . . . . . . . . 294
7.7.1 Using a Sorted List . . . . . . . . . . . . . . . . . . . . . . . . 294
7.7.2 Using a List with the Move-to-Front Heuristic . . . . . . . . . . 297
7.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
8 Trees 307
8.1 General Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
8.1.1 Tree Definitions and Properties . . . . . . . . . . . . . . . . . . 309
8.1.2 The Tree Abstract Data Type . . . . . . . . . . . . . . . . . . 312
8.1.3 Computing Depth and Height . . . . . . . . . . . . . . . . . . . 314
8.2 Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
8.2.1 The Binary Tree Abstract Data Type . . . . . . . . . . . . . . . 319
8.2.2 Properties of Binary Trees . . . . . . . . . . . . . . . . . . . . 321
8.3 Implementing Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
8.3.1 Linked Structure for Binary Trees . . . . . . . . . . . . . . . . . 323
8.3.2 Array-Based Representation of a Binary Tree . . . . . . . . . . 331
8.3.3 Linked Structure for General Trees . . . . . . . . . . . . . . . . 333
8.4 Tree Traversal Algorithms . . . . . . . . . . . . . . . . . . . . . . . 334
8.4.1 Preorder and Postorder Traversals of General Trees . . . . . . . 334
8.4.2 Breadth-First Tree Traversal . . . . . . . . . . . . . . . . . . . 336
8.4.3 Inorder Traversal of a Binary Tree . . . . . . . . . . . . . . . . 337
8.4.4 Implementing Tree Traversals in Java . . . . . . . . . . . . . . 339
8.4.5 Applications of Tree Traversals . . . . . . . . . . . . . . . . . . 343
8.4.6 Euler Tours . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
8.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
9 Priority Queues 359
9.1 The Priority Queue Abstract Data Type . . . . . . . . . . . . . . . 360
9.1.1 Priorities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
9.1.2 The Priority Queue ADT . . . . . . . . . . . . . . . . . . . . . 361
9.2 Implementing a Priority Queue . . . . . . . . . . . . . . . . . . . . 362
9.2.1 The Entry Composite . . . . . . . . . . . . . . . . . . . . . . . 362
9.2.2 Comparing Keys with Total Orders . . . . . . . . . . . . . . . . 363
9.2.3 The AbstractPriorityQueue Base Class . . . . . . . . . . . . . . 364
9.2.4 Implementing a Priority Queue with an Unsorted List . . . . . . 366
9.2.5 Implementing a Priority Queue with a Sorted List . . . . . . . . 368
9.3 Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
9.3.1 The Heap Data Structure . . . . . . . . . . . . . . . . . . . . . 370
9.3.2 Implementing a Priority Queue with a Heap . . . . . . . . . . . 372
9.3.3 Analysis of a Heap-Based Priority Queue . . . . . . . . . . . . . 379
9.3.4 Bottom-Up Heap Construction ⋆ . . . . . . . . . . . . . . . . 380
9.3.5 Using the java.util.PriorityQueue Class . . . . . . . . . . . . . . 384
9.4 Sorting with a Priority Queue . . . . . . . . . . . . . . . . . . . . . 385
9.4.1 Selection-Sort and Insertion-Sort . . . . . . . . . . . . . . . . . 386
9.4.2 Heap-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
9.5 Adaptable Priority Queues . . . . . . . . . . . . . . . . . . . . . . . 390
9.5.1 Location-Aware Entries . . . . . . . . . . . . . . . . . . . . . . 391
9.5.2 Implementing an Adaptable Priority Queue . . . . . . . . . . . 392
9.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
10 Maps, Hash Tables, and Skip Lists 401
10.1 Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
10.1.1 The Map ADT . . . . . . . . . . . . . . . . . . . . . . . . . . 403
10.1.2 Application: Counting Word Frequencies . . . . . . . . . . . . . 405
10.1.3 An AbstractMap Base Class . . . . . . . . . . . . . . . . . . . 406
10.1.4 A Simple Unsorted Map Implementation . . . . . . . . . . . . . 408
10.2 Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
10.2.1 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 411
10.2.2 Collision-Handling Schemes . . . . . . . . . . . . . . . . . . . . 417
10.2.3 Load Factors, Rehashing, and Efficiency . . . . . . . . . . . . . 420
10.2.4 Java Hash Table Implementation . . . . . . . . . . . . . . . . . 422
10.3 Sorted Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
10.3.1 Sorted Search Tables . . . . . . . . . . . . . . . . . . . . . . . 429
10.3.2 Two Applications of Sorted Maps . . . . . . . . . . . . . . . . 433
10.4 Skip Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
10.4.1 Search and Update Operations in a Skip List . . . . . . . . . . 438
10.4.2 Probabilistic Analysis of Skip Lists ⋆ . . . . . . . . . . . . . . . 442
10.5 Sets, Multisets, and Multimaps . . . . . . . . . . . . . . . . . . . . 445
10.5.1 The Set ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
10.5.2 The Multiset ADT . . . . . . . . . . . . . . . . . . . . . . . . 447
10.5.3 The Multimap ADT . . . . . . . . . . . . . . . . . . . . . . . . 448
10.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
11 Search Trees 459
11.1 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
11.1.1 Searching Within a Binary Search Tree . . . . . . . . . . . . . . 461
11.1.2 Insertions and Deletions . . . . . . . . . . . . . . . . . . . . . . 463
11.1.3 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 466
11.1.4 Performance of a Binary Search Tree . . . . . . . . . . . . . . . 470
11.2 Balanced Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . 472
11.2.1 Java Framework for Balancing Search Trees . . . . . . . . . . . 475
11.3 AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
11.3.1 Update Operations . . . . . . . . . . . . . . . . . . . . . . . . 481
11.3.2 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 486
11.4 Splay Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
11.4.1 Splaying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
11.4.2 When to Splay . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
11.4.3 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 494
11.4.4 Amortized Analysis of Splaying ⋆ . . . . . . . . . . . . . . . . 495
11.5 (2,4) Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
11.5.1 Multiway Search Trees . . . . . . . . . . . . . . . . . . . . . . 500
11.5.2 (2,4)-Tree Operations . . . . . . . . . . . . . . . . . . . . . . . 503
11.6 Red-Black Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510
11.6.1 Red-Black Tree Operations . . . . . . . . . . . . . . . . . . . . 512
11.6.2 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 522
11.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525
12 Sorting and Selection 531
12.1 Merge-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532
12.1.1 Divide-and-Conquer . . . . . . . . . . . . . . . . . . . . . . . . 532
12.1.2 Array-Based Implementation of Merge-Sort . . . . . . . . . . . 537
12.1.3 The Running Time of Merge-Sort . . . . . . . . . . . . . . . . 538
12.1.4 Merge-Sort and Recurrence Equations ⋆ . . . . . . . . . . . . . 540
12.1.5 Alternative Implementations of Merge-Sort . . . . . . . . . . . 541
12.2 Quick-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
12.2.1 Randomized Quick-Sort . . . . . . . . . . . . . . . . . . . . . . 551
12.2.2 Additional Optimizations for Quick-Sort . . . . . . . . . . . . . 553
12.3 Studying Sorting through an Algorithmic Lens . . . . . . . . . . . 556
12.3.1 Lower Bound for Sorting . . . . . . . . . . . . . . . . . . . . . 556
12.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort . . . . . . . . 558
12.4 Comparing Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . 561
12.5 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
12.5.1 Prune-and-Search . . . . . . . . . . . . . . . . . . . . . . . . . 563
12.5.2 Randomized Quick-Select . . . . . . . . . . . . . . . . . . . . . 564
12.5.3 Analyzing Randomized Quick-Select . . . . . . . . . . . . . . . 565
12.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566
13 Text Processing 573
13.1 Abundance of Digitized Text . . . . . . . . . . . . . . . . . . . . . . 574
13.1.1 Notations for Character Strings . . . . . . . . . . . . . . . . . . 575
13.2 Pattern-Matching Algorithms . . . . . . . . . . . . . . . . . . . . . 576
13.2.1 Brute Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
13.2.2 The Boyer-Moore Algorithm . . . . . . . . . . . . . . . . . . . 578
13.2.3 The Knuth-Morris-Pratt Algorithm . . . . . . . . . . . . . . . . 582
13.3 Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586
13.3.1 Standard Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . 586
13.3.2 Compressed Tries . . . . . . . . . . . . . . . . . . . . . . . . . 590
13.3.3 Suffix Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
13.3.4 Search Engine Indexing . . . . . . . . . . . . . . . . . . . . . . 594
13.4 Text Compression and the Greedy Method . . . . . . . . . . . . . 595
13.4.1 The Huffman Coding Algorithm . . . . . . . . . . . . . . . . . 596
13.4.2 The Greedy Method . . . . . . . . . . . . . . . . . . . . . . . . 597
13.5 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . 598
13.5.1 Matrix Chain-Product . . . . . . . . . . . . . . . . . . . . . . . 598
13.5.2 DNA and Text Sequence Alignment . . . . . . . . . . . . . . . 601
13.6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises
14 Graph Algorithms 611
14.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
14.1.1 The Graph ADT . . . . . . . . . . . . . . . . . . . . . . . . . . 618
14.2 Data Structures for Graphs . . . . . . . . . . . . . . . . . . . . . . . 619
14.2.1 Edge List Structure . . . . . . . . . . . . . . . . . . . . . . . . 620
14.2.2 Adjacency List Structure . . . . . . . . . . . . . . . . . . . . . 622
14.2.3 Adjacency Map Structure . . . . . . . . . . . . . . . . . . . . . 624
14.2.4 Adjacency Matrix Structure . . . . . . . . . . . . . . . . . . . . 625
14.2.5 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 626
14.3 Graph Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 630
14.3.1 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . 631
14.3.2 DFS Implementation and Extensions . . . . . . . . . . . . . . . 636
14.3.3 Breadth-First Search . . . . . . . . . . . . . . . . . . . . . . . 640
14.4 Transitive Closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643
14.5 Directed Acyclic Graphs . . . . . . . . . . . . . . . . . . . . . . . . 647
14.5.1 Topological Ordering . . . . . . . . . . . . . . . . . . . . . . . 647
14.6 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
14.6.1 Weighted Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 651
14.6.2 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 653
14.7 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . 662
14.7.1 Prim-Jarn´ık Algorithm . . . . . . . . . . . . . . . . . . . . . . 664
14.7.2 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 667
14.7.3 Disjoint Partitions and Union-Find Structures . . . . . . . . . . 672
14.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677
15 Memory Management and B-Trees 687
15.1 Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . 688
15.1.1 Stacks in the Java Virtual Machine . . . . . . . . . . . . . . . . 688
15.1.2 Allocating Space in the Memory Heap . . . . . . . . . . . . . . 691
15.1.3 Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . . 693
15.2 Memory Hierarchies and Caching . . . . . . . . . . . . . . . . . . . 695
15.2.1 Memory Systems . . . . . . . . . . . . . . . . . . . . . . . . . 695
15.2.2 Caching Strategies . . . . . . . . . . . . . . . . . . . . . . . . 696
15.3 External Searching and B-Trees . . . . . . . . . . . . . . . . . . . . 701
15.3.1 (a,b) Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702
15.3.2 B-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704
15.4 External-Memory Sorting . . . . . . . . . . . . . . . . . . . . . . . . 705
15.4.1 Multiway Merging . . . . . . . . . . . . . . . . . . . . . . . . . 706
15.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707
Bibliography 710
Index 714
1.1 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1.1 Base Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Classes and Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2.1 Creating and Using Objects . . . . . . . . . . . . . . . . . . . . 6
1.2.2 Defining a Class . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Strings, Wrappers, Arrays, and Enum Types . . . . . . . . . . . . . 17
1.4 Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4.1 Literals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4.2 Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.3 Type Conversions . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.5 Control Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.5.1 The If and Switch Statements . . . . . . . . . . . . . . . . . . 30
1.5.2 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.5.3 Explicit Control-Flow Statements . . . . . . . . . . . . . . . . . 37
1.6 Simple Input and Output . . . . . . . . . . . . . . . . . . . . . . . . 38
1.7 An Example Program . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.8 Packages and Imports . . . . . . . . . . . . . . . . . . . . . . . . . . 44
1.9 Software Development . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.9.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1.9.2 Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.9.3 Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
1.9.4 Documentation and Style . . . . . . . . . . . . . . . . . . . . . 50
1.9.5 Testing and Debugging . . . . . . . . . . . . . . . . . . . . . . 53
1.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2 Object-Oriented Design 59
2.1 Goals, Principles, and Patterns . . . . . . . . . . . . . . . . . . . . 60
2.1.1 Object-Oriented Design Goals . . . . . . . . . . . . . . . . . . 60
2.1.2 Object-Oriented Design Principles . . . . . . . . . . . . . . . . 61
2.1.3 Design Patterns . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.2 Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.2.1 Extending the CreditCard Class . . . . . . . . . . . . . . . . . . 65
2.2.2 Polymorphism and Dynamic Dispatch . . . . . . . . . . . . . . 68
2.2.3 Inheritance Hierarchies . . . . . . . . . . . . . . . . . . . . . . 69
2.3 Interfaces and Abstract Classes . . . . . . . . . . . . . . . . . . . . 76
2.3.1 Interfaces in Java . . . . . . . . . . . . . . . . . . . . . . . . . 76
2.3.2 Multiple Inheritance for Interfaces . . . . . . . . . . . . . . . . 79
2.3.3 Abstract Classes . . . . . . . . . . . . . . . . . . . . . . . . . . 80
2.4 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
2.4.1 Catching Exceptions . . . . . . . . . . . . . . . . . . . . . . . . 82
2.4.2 Throwing Exceptions . . . . . . . . . . . . . . . . . . . . . . . 85
2.4.3 Java’s Exception Hierarchy . . . . . . . . . . . . . . . . . . . . 86
2.5 Casting and Generics . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2.5.1 Casting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2.5.2 Generics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
2.6 Nested Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3 Fundamental Data Structures 103
3.1 Using Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
3.1.1 Storing Game Entries in an Array . . . . . . . . . . . . . . . . . 104
3.1.2 Sorting an Array . . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.1.3 java.util Methods for Arrays and Random Numbers . . . . . . . 112
3.1.4 Simple Cryptography with Character Arrays . . . . . . . . . . . 115
3.1.5 Two-Dimensional Arrays and Positional Games . . . . . . . . . 118
3.2 Singly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
3.2.1 Implementing a Singly Linked List Class . . . . . . . . . . . . . 126
3.3 Circularly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . 128
3.3.1 Round-Robin Scheduling . . . . . . . . . . . . . . . . . . . . . 128
3.3.2 Designing and Implementing a Circularly Linked List . . . . . . 129
3.4 Doubly Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
3.4.1 Implementing a Doubly Linked List Class . . . . . . . . . . . . 135
3.5 Equivalence Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
3.5.1 Equivalence Testing with Arrays . . . . . . . . . . . . . . . . . 139
3.5.2 Equivalence Testing with Linked Lists . . . . . . . . . . . . . . 140
3.6 Cloning Data Structures . . . . . . . . . . . . . . . . . . . . . . . . 141
3.6.1 Cloning Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
3.6.2 Cloning Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . 144
3.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
4 Algorithm Analysis 149
4.1 Experimental Studies . . . . . . . . . . . . . . . . . . . . . . . . . . 151
4.1.1 Moving Beyond Experimental Analysis . . . . . . . . . . . . . . 154
4.2 The Seven Functions Used in This Book . . . . . . . . . . . . . . . 156
4.2.1 Comparing Growth Rates . . . . . . . . . . . . . . . . . . . . . 163
4.3 Asymptotic Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.3.1 The “Big-Oh” Notation . . . . . . . . . . . . . . . . . . . . . . 164
4.3.2 Comparative Analysis . . . . . . . . . . . . . . . . . . . . . . . 168
4.3.3 Examples of Algorithm Analysis . . . . . . . . . . . . . . . . . 170
4.4 Simple Justification Techniques . . . . . . . . . . . . . . . . . . . . 178
4.4.1 By Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
4.4.2 The “Contra” Attack . . . . . . . . . . . . . . . . . . . . . . . 178
4.4.3 Induction and Loop Invariants . . . . . . . . . . . . . . . . . . 179
4.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
5 Recursion 189
5.1 Illustrative Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 191
5.1.1 The Factorial Function . . . . . . . . . . . . . . . . . . . . . . 191
5.1.2 Drawing an English Ruler . . . . . . . . . . . . . . . . . . . . . 193
5.1.3 Binary Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
5.1.4 File Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
5.2 Analyzing Recursive Algorithms . . . . . . . . . . . . . . . . . . . . 202
5.3 Further Examples of Recursion . . . . . . . . . . . . . . . . . . . . . 206
5.3.1 Linear Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . 206
5.3.2 Binary Recursion . . . . . . . . . . . . . . . . . . . . . . . . . 211
5.3.3 Multiple Recursion . . . . . . . . . . . . . . . . . . . . . . . . 212
5.4 Designing Recursive Algorithms . . . . . . . . . . . . . . . . . . . . 214
5.5 Recursion Run Amok . . . . . . . . . . . . . . . . . . . . . . . . . . 215
5.5.1 Maximum Recursive Depth in Java . . . . . . . . . . . . . . . . 218
5.6 Eliminating Tail Recursion . . . . . . . . . . . . . . . . . . . . . . . 219
5.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
6 Stacks, Queues, and Deques 225
6.1 Stacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
6.1.1 The Stack Abstract Data Type . . . . . . . . . . . . . . . . . . 227
6.1.2 A Simple Array-Based Stack Implementation . . . . . . . . . . 230
6.1.3 Implementing a Stack with a Singly Linked List . . . . . . . . . 233
6.1.4 Reversing an Array Using a Stack . . . . . . . . . . . . . . . . 234
6.1.5 Matching Parentheses and HTML Tags . . . . . . . . . . . . . 235
6.2 Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238
6.2.1 The Queue Abstract Data Type . . . . . . . . . . . . . . . . . 239
6.2.2 Array-Based Queue Implementation . . . . . . . . . . . . . . . 241
6.2.3 Implementing a Queue with a Singly Linked List . . . . . . . . . 245
6.2.4 A Circular Queue . . . . . . . . . . . . . . . . . . . . . . . . . 246
6.3 Double-Ended Queues . . . . . . . . . . . . . . . . . . . . . . . . . . 248
6.3.1 The Deque Abstract Data Type . . . . . . . . . . . . . . . . . 248
6.3.2 Implementing a Deque . . . . . . . . . . . . . . . . . . . . . . 250
6.3.3 Deques in the Java Collections Framework . . . . . . . . . . . . 251
6.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 252
7 List and Iterator ADTs 257
7.1 The List ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
7.2 Array Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
7.2.1 Dynamic Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . 263
7.2.2 Implementing a Dynamic Array . . . . . . . . . . . . . . . . . . 264
7.2.3 Amortized Analysis of Dynamic Arrays . . . . . . . . . . . . . . 265
7.2.4 Java’s StringBuilder class . . . . . . . . . . . . . . . . . . . . . 269
7.3 Positional Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
7.3.1 Positions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
7.3.2 The Positional List Abstract Data Type . . . . . . . . . . . . . 272
7.3.3 Doubly Linked List Implementation . . . . . . . . . . . . . . . . 276
7.4 Iterators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
7.4.1 The Iterable Interface and Java’s For-Each Loop . . . . . . . . 283
7.4.2 Implementing Iterators . . . . . . . . . . . . . . . . . . . . . . 284
7.5 The Java Collections Framework . . . . . . . . . . . . . . . . . . . 288
7.5.1 List Iterators in Java . . . . . . . . . . . . . . . . . . . . . . . 289
7.5.2 Comparison to Our Positional List ADT . . . . . . . . . . . . . 290
7.5.3 List-Based Algorithms in the Java Collections Framework . . . . 291
7.6 Sorting a Positional List . . . . . . . . . . . . . . . . . . . . . . . . 293
7.7 Case Study: Maintaining Access Frequencies . . . . . . . . . . . . 294
7.7.1 Using a Sorted List . . . . . . . . . . . . . . . . . . . . . . . . 294
7.7.2 Using a List with the Move-to-Front Heuristic . . . . . . . . . . 297
7.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
8 Trees 307
8.1 General Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
8.1.1 Tree Definitions and Properties . . . . . . . . . . . . . . . . . . 309
8.1.2 The Tree Abstract Data Type . . . . . . . . . . . . . . . . . . 312
8.1.3 Computing Depth and Height . . . . . . . . . . . . . . . . . . . 314
8.2 Binary Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
8.2.1 The Binary Tree Abstract Data Type . . . . . . . . . . . . . . . 319
8.2.2 Properties of Binary Trees . . . . . . . . . . . . . . . . . . . . 321
8.3 Implementing Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 323
8.3.1 Linked Structure for Binary Trees . . . . . . . . . . . . . . . . . 323
8.3.2 Array-Based Representation of a Binary Tree . . . . . . . . . . 331
8.3.3 Linked Structure for General Trees . . . . . . . . . . . . . . . . 333
8.4 Tree Traversal Algorithms . . . . . . . . . . . . . . . . . . . . . . . 334
8.4.1 Preorder and Postorder Traversals of General Trees . . . . . . . 334
8.4.2 Breadth-First Tree Traversal . . . . . . . . . . . . . . . . . . . 336
8.4.3 Inorder Traversal of a Binary Tree . . . . . . . . . . . . . . . . 337
8.4.4 Implementing Tree Traversals in Java . . . . . . . . . . . . . . 339
8.4.5 Applications of Tree Traversals . . . . . . . . . . . . . . . . . . 343
8.4.6 Euler Tours . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348
8.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
9 Priority Queues 359
9.1 The Priority Queue Abstract Data Type . . . . . . . . . . . . . . . 360
9.1.1 Priorities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
9.1.2 The Priority Queue ADT . . . . . . . . . . . . . . . . . . . . . 361
9.2 Implementing a Priority Queue . . . . . . . . . . . . . . . . . . . . 362
9.2.1 The Entry Composite . . . . . . . . . . . . . . . . . . . . . . . 362
9.2.2 Comparing Keys with Total Orders . . . . . . . . . . . . . . . . 363
9.2.3 The AbstractPriorityQueue Base Class . . . . . . . . . . . . . . 364
9.2.4 Implementing a Priority Queue with an Unsorted List . . . . . . 366
9.2.5 Implementing a Priority Queue with a Sorted List . . . . . . . . 368
9.3 Heaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370
9.3.1 The Heap Data Structure . . . . . . . . . . . . . . . . . . . . . 370
9.3.2 Implementing a Priority Queue with a Heap . . . . . . . . . . . 372
9.3.3 Analysis of a Heap-Based Priority Queue . . . . . . . . . . . . . 379
9.3.4 Bottom-Up Heap Construction ⋆ . . . . . . . . . . . . . . . . 380
9.3.5 Using the java.util.PriorityQueue Class . . . . . . . . . . . . . . 384
9.4 Sorting with a Priority Queue . . . . . . . . . . . . . . . . . . . . . 385
9.4.1 Selection-Sort and Insertion-Sort . . . . . . . . . . . . . . . . . 386
9.4.2 Heap-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
9.5 Adaptable Priority Queues . . . . . . . . . . . . . . . . . . . . . . . 390
9.5.1 Location-Aware Entries . . . . . . . . . . . . . . . . . . . . . . 391
9.5.2 Implementing an Adaptable Priority Queue . . . . . . . . . . . 392
9.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
10 Maps, Hash Tables, and Skip Lists 401
10.1 Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
10.1.1 The Map ADT . . . . . . . . . . . . . . . . . . . . . . . . . . 403
10.1.2 Application: Counting Word Frequencies . . . . . . . . . . . . . 405
10.1.3 An AbstractMap Base Class . . . . . . . . . . . . . . . . . . . 406
10.1.4 A Simple Unsorted Map Implementation . . . . . . . . . . . . . 408
10.2 Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410
10.2.1 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 411
10.2.2 Collision-Handling Schemes . . . . . . . . . . . . . . . . . . . . 417
10.2.3 Load Factors, Rehashing, and Efficiency . . . . . . . . . . . . . 420
10.2.4 Java Hash Table Implementation . . . . . . . . . . . . . . . . . 422
10.3 Sorted Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428
10.3.1 Sorted Search Tables . . . . . . . . . . . . . . . . . . . . . . . 429
10.3.2 Two Applications of Sorted Maps . . . . . . . . . . . . . . . . 433
10.4 Skip Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
10.4.1 Search and Update Operations in a Skip List . . . . . . . . . . 438
10.4.2 Probabilistic Analysis of Skip Lists ⋆ . . . . . . . . . . . . . . . 442
10.5 Sets, Multisets, and Multimaps . . . . . . . . . . . . . . . . . . . . 445
10.5.1 The Set ADT . . . . . . . . . . . . . . . . . . . . . . . . . . . 445
10.5.2 The Multiset ADT . . . . . . . . . . . . . . . . . . . . . . . . 447
10.5.3 The Multimap ADT . . . . . . . . . . . . . . . . . . . . . . . . 448
10.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
11 Search Trees 459
11.1 Binary Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . 460
11.1.1 Searching Within a Binary Search Tree . . . . . . . . . . . . . . 461
11.1.2 Insertions and Deletions . . . . . . . . . . . . . . . . . . . . . . 463
11.1.3 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 466
11.1.4 Performance of a Binary Search Tree . . . . . . . . . . . . . . . 470
11.2 Balanced Search Trees . . . . . . . . . . . . . . . . . . . . . . . . . 472
11.2.1 Java Framework for Balancing Search Trees . . . . . . . . . . . 475
11.3 AVL Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479
11.3.1 Update Operations . . . . . . . . . . . . . . . . . . . . . . . . 481
11.3.2 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 486
11.4 Splay Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
11.4.1 Splaying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 488
11.4.2 When to Splay . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
11.4.3 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 494
11.4.4 Amortized Analysis of Splaying ⋆ . . . . . . . . . . . . . . . . 495
11.5 (2,4) Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 500
11.5.1 Multiway Search Trees . . . . . . . . . . . . . . . . . . . . . . 500
11.5.2 (2,4)-Tree Operations . . . . . . . . . . . . . . . . . . . . . . . 503
11.6 Red-Black Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510
11.6.1 Red-Black Tree Operations . . . . . . . . . . . . . . . . . . . . 512
11.6.2 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 522
11.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525
12 Sorting and Selection 531
12.1 Merge-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532
12.1.1 Divide-and-Conquer . . . . . . . . . . . . . . . . . . . . . . . . 532
12.1.2 Array-Based Implementation of Merge-Sort . . . . . . . . . . . 537
12.1.3 The Running Time of Merge-Sort . . . . . . . . . . . . . . . . 538
12.1.4 Merge-Sort and Recurrence Equations ⋆ . . . . . . . . . . . . . 540
12.1.5 Alternative Implementations of Merge-Sort . . . . . . . . . . . 541
12.2 Quick-Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
12.2.1 Randomized Quick-Sort . . . . . . . . . . . . . . . . . . . . . . 551
12.2.2 Additional Optimizations for Quick-Sort . . . . . . . . . . . . . 553
12.3 Studying Sorting through an Algorithmic Lens . . . . . . . . . . . 556
12.3.1 Lower Bound for Sorting . . . . . . . . . . . . . . . . . . . . . 556
12.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort . . . . . . . . 558
12.4 Comparing Sorting Algorithms . . . . . . . . . . . . . . . . . . . . . 561
12.5 Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
12.5.1 Prune-and-Search . . . . . . . . . . . . . . . . . . . . . . . . . 563
12.5.2 Randomized Quick-Select . . . . . . . . . . . . . . . . . . . . . 564
12.5.3 Analyzing Randomized Quick-Select . . . . . . . . . . . . . . . 565
12.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566
13 Text Processing 573
13.1 Abundance of Digitized Text . . . . . . . . . . . . . . . . . . . . . . 574
13.1.1 Notations for Character Strings . . . . . . . . . . . . . . . . . . 575
13.2 Pattern-Matching Algorithms . . . . . . . . . . . . . . . . . . . . . 576
13.2.1 Brute Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
13.2.2 The Boyer-Moore Algorithm . . . . . . . . . . . . . . . . . . . 578
13.2.3 The Knuth-Morris-Pratt Algorithm . . . . . . . . . . . . . . . . 582
13.3 Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586
13.3.1 Standard Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . 586
13.3.2 Compressed Tries . . . . . . . . . . . . . . . . . . . . . . . . . 590
13.3.3 Suffix Tries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
13.3.4 Search Engine Indexing . . . . . . . . . . . . . . . . . . . . . . 594
13.4 Text Compression and the Greedy Method . . . . . . . . . . . . . 595
13.4.1 The Huffman Coding Algorithm . . . . . . . . . . . . . . . . . 596
13.4.2 The Greedy Method . . . . . . . . . . . . . . . . . . . . . . . . 597
13.5 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . 598
13.5.1 Matrix Chain-Product . . . . . . . . . . . . . . . . . . . . . . . 598
13.5.2 DNA and Text Sequence Alignment . . . . . . . . . . . . . . . 601
13.6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Exercises
14 Graph Algorithms 611
14.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
14.1.1 The Graph ADT . . . . . . . . . . . . . . . . . . . . . . . . . . 618
14.2 Data Structures for Graphs . . . . . . . . . . . . . . . . . . . . . . . 619
14.2.1 Edge List Structure . . . . . . . . . . . . . . . . . . . . . . . . 620
14.2.2 Adjacency List Structure . . . . . . . . . . . . . . . . . . . . . 622
14.2.3 Adjacency Map Structure . . . . . . . . . . . . . . . . . . . . . 624
14.2.4 Adjacency Matrix Structure . . . . . . . . . . . . . . . . . . . . 625
14.2.5 Java Implementation . . . . . . . . . . . . . . . . . . . . . . . 626
14.3 Graph Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 630
14.3.1 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . 631
14.3.2 DFS Implementation and Extensions . . . . . . . . . . . . . . . 636
14.3.3 Breadth-First Search . . . . . . . . . . . . . . . . . . . . . . . 640
14.4 Transitive Closure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 643
14.5 Directed Acyclic Graphs . . . . . . . . . . . . . . . . . . . . . . . . 647
14.5.1 Topological Ordering . . . . . . . . . . . . . . . . . . . . . . . 647
14.6 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
14.6.1 Weighted Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 651
14.6.2 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 653
14.7 Minimum Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . 662
14.7.1 Prim-Jarn´ık Algorithm . . . . . . . . . . . . . . . . . . . . . . 664
14.7.2 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 667
14.7.3 Disjoint Partitions and Union-Find Structures . . . . . . . . . . 672
14.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677
15 Memory Management and B-Trees 687
15.1 Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . 688
15.1.1 Stacks in the Java Virtual Machine . . . . . . . . . . . . . . . . 688
15.1.2 Allocating Space in the Memory Heap . . . . . . . . . . . . . . 691
15.1.3 Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . . 693
15.2 Memory Hierarchies and Caching . . . . . . . . . . . . . . . . . . . 695
15.2.1 Memory Systems . . . . . . . . . . . . . . . . . . . . . . . . . 695
15.2.2 Caching Strategies . . . . . . . . . . . . . . . . . . . . . . . . 696
15.3 External Searching and B-Trees . . . . . . . . . . . . . . . . . . . . 701
15.3.1 (a,b) Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 702
15.3.2 B-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704
15.4 External-Memory Sorting . . . . . . . . . . . . . . . . . . . . . . . . 705
15.4.1 Multiway Merging . . . . . . . . . . . . . . . . . . . . . . . . . 706
15.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707
Bibliography 710
Index 714
نظرات (0)
.فقط مشتریانی که این محصول را خریداری کرده اند و وارد سیستم شده اند میتوانند برای این محصول دیدگاه(نظر) ارسال کنند.
نقد و بررسی‌ها
هیچ دیدگاهی برای این محصول نوشته نشده است.