1.1 Classes, Types, and Objects, 3
How Classes Are Declared, 4
Class Modifiers, 5
1.1.1 Base Types, 6
1.1.2 Objects, 6
Number Objects, 7
String Objects, 8
Instance Variables, 9
Variable Modifiers, 10
1.2 Methods, 11
Declaring Methods, 11
Method Modifiers, 12
Return Types, 12
Parameters, 13
Constructor Methods, 13
The main Method, 14
Statement Blocks and Local Variables, 15
1.3 Expressions, 17
1.3.1 Literals, 17
1.3.2 Operators, 17
The Assignment Operator, 18
The Dot Operator, 18
Arithmetic Operators, 19
Increment and Decrement Operators, 20
Logical Operators, 20
Bitwise Operators, 21
Operational Assignment Operators, 21
String Concatenation, 21
Operator Precedence, 22
1.3.3 Casting in Expressions, 23
Ordinary Casting, 23
Casting with Operators, 23
Implicit Casting, 24
Implicit Casting with String Objects, 24
1.4 Control Flow, 25
1.4.1 The If and Switch Statements, 25
The If Statement, 25
Switch Statements, 26
1.4.2 Loops, 27
For Loops, 27
While Loops, 28
Do-While Loops, 29
1.4.3 Explicit Control-Flow Statements, 29
Returning from a Method, 29
The break Statement, 30
The continue Statement, 31
1.5 Arrays, 32
1.6 Simple Input and Output, 33
Output Methods, 34
Input Methods, 34
1.7 An Example Program, 36
The CreditCard Class, 36
The Test Class, 36
1.8 Packages, 40
Using Other Packages, 40
The Import Command, 40
Importing a Whole Package, 41
1.9 Writing a Java Program, 42
1.9.1 Design, 42
1.9.2 Coding, 43
Javadoc, 44
Readability and Style, 46
1.9.3 Testing and Debugging, 47
Testing, 47
Debugging, 48
1.10 Utilities in the java.lang Package, 49
The Math Class, 49
String Conversions, 50
Big Numbers, 50
1.11 Exercises, 51
2.1 Goals and Principles, 56
2.1.1 Object-Oriented Design Goals, 57
Robustness, 57
Adaptability, 58
Reusability, 58
2.1.2 Object-Oriented Design Principles, 59
Abstraction, 59
Encapsulation, 60
Modularity, 61
2.2 Inheritance and Polymorphism, 62
2.2.1 Inheritance, 62
Object Creation and Referencing, 64
Dynamic Dispatch, 64
2.2.2 Polymorphism, 65
2.2.3 Using Inheritance in Java, 66
Class Inheritance in Java, 66
Types of Method Overriding, 66
The Keyword this, 67
An Illustration of Inheritance in Java, 68
An Arithmetic Progression Class, 70
A Geometric Progression Class, 72
A Fibonacci Progression Class, 73
2.3 Exceptions, 76
2.3.1 Throwing Exceptions, 76
The Throws Clause, 76
Kinds of Throwables, 77
2.3.2 Catching Exceptions, 78
2.4 Interfaces and Abstract Classes, 80
2.4.1 Implementing Interfaces, 80
2.4.2 Multiple Inheritance in Interfaces, 83
2.4.3 Abstract Classes, 84
2.5 Casting, 84
2.5.1 Casting in an Inheritance Hierarchy, 85
2.5.2 Casting with Interfaces, 86
2.6 Design Patterns, 89
2.6.1 The Adapter Pattern, 90
2.7 Exercises, 92
3.1 What Is Running Time Anyway?, 98
3.1.1 Requirements for a General Analysis Methodology, 99
3.2 Pseudo-Code, 100
3.2.1 An Example of Pseudo-Code, 100
3.2.2 What Is Pseudo-Code?, 102
3.3 A Quick Mathematical Review, 103
3.3.1 Logarithms and Exponents, 103
3.3.2 Summations, 105
3.4 Simple Justification Techniques *, 106
3.4.1 By Example, 107
3.4.2 The ``Contra'' Attack, 107
3.4.3 Induction and Loop Invariants, 108
Induction, 108
Loop Invariants, 109
3.5 Analysis of Algorithms, 111
3.5.1 Primitive Operations, 111
Counting Primitive Operations, 112
3.5.2 Average-Case and Worst-Case Analysis, 113
3.6 Asymptotic Notation, 114
Simplifying the Analysis Further, 115
3.6.1 The ``Big-Oh'' Notation, 115
3.6.2 ``Relatives'' of the Big-Oh, 118
``Distant Cousins'' of the Big-Oh, 119
3.7 Asymptotic Analysis, 120
3.7.1 Using the Big-Oh Notation, 122
Some Words of Caution, 122
3.7.2 Examples of Asymptotic Algorithm Analysis, 123
A Quadratic-Time Algorithm, 124
A Linear-Time Algorithm, 125
3.8 Exercises, 126
4.1 Stacks, 136
4.1.1 The Stack Abstract Data Type, 137
A Stack Interface in Java, 138
4.1.2 A Simple Array-Based Implementation, 140
Casting with a Generic Stack, 144
4.1.3 Stacks in the Java Virtual Machine, 145
The Java Method Stack, 146
Recursion, 148
The Operand Stack, 149
4.2 Queues, 149
4.2.1 The Queue Abstract Data Type, 149
A Queue Interface in Java, 151
Example Applications, 152
4.2.2 A Simple Array-Based Implementation, 152
4.2.3 Memory Allocation in Java, 155
4.2.4 Java Threads *, 157
4.3 Linked Lists, 159
4.3.1, Singly Linked Lists 159
4.3.2 Implementing a Stack with a Singly Linked List, 163
4.3.3 Implementing a Queue with a Singly Linked List, 165
4.4 Double-Ended Queues, 166
4.4.1 The Deque Abstract Data Type, 166
4.4.2 Implementing a Deque with a Doubly Linked List, 167
4.4.3 Implementing Stacks and Queues with Deques, 171
4.4.4 The Adapter Pattern, 173
4.5 Sample Case Study Application, 173
4.5.1 A Quadratic-Time Algorithm, 174
4.5.2 A Linear-Time Algorithm, 175
4.5.3 Java Implementation, 176
4.6 Exercises, 179
5.1 Vectors, 185
5.1.1 The Vector Abstract Data Type, 186
5.1.2 A Simple Array-Based Implementation, 187
5.1.3 An Extendable Array Implementation, 189
5.1.4 The java.util.ArrayList and java.util.Vector Classes, 192
5.2 Lists, 194
5.2.1 Node-Based Operations, 194
5.2.2 Positions, 195
5.2.3 The List Abstract Data Type, 195
5.2.4 Doubly Linked List Implementation, 198
5.3 Sequences, 206
5.3.1 The Sequence Abstract Data Type, 206
5.3.2 Implementing a Sequence with a Doubly Linked List, 206
5.3.3 Implementing a Sequence with an Array, 209
5.3.4 Comparing Sequence Implementations, 210
5.4 Case Study: Bubble-Sort on a Sequence, 211
5.4.1 The Bubble-Sort Algorithm, 211
5.4.2 A Sequence-Based Analysis of Bubble-Sort, 212
5.5 Iterators, 214
5.6 A Hierarchy of Sequence ADTs, 216
5.6.1 Methods of a Container, 216
5.6.2 Inspectable Containers, 217
5.6.3 Inheritance Structure of Sequence ADTs, 218
5.7 Exercises, 219
6.1 The Tree Abstract Data Type, 229
6.1.1 Terminology and Basic Properties, 229
6.1.2 Tree Methods, 233
6.1.3 A Tree Interface in Java, 235
6.2 Basic Algorithms on Trees, 236
6.2.1 Assumptions, 236
6.2.2 Depth and Height, 237
6.2.3 Preorder Traversal, 240
6.2.4 Postorder Traversal, 243
6.3 Binary Trees, 246
6.3.1 The Binary Tree ADT, 247
6.3.2 A Binary Tree Interface in Java, 247
6.3.3 Properties of Binary Trees, 249
6.3.4 Traversals of a Binary Tree, 251
Preorder Traversal of a Binary Tree, 251
Postorder Traversal of a Binary Tree, 251
Inorder Traversal of a Binary Tree, 252
Using Inorder Traversal for Tree Drawing, 255
A Unified Tree Traversal Framework, 255
The Euler Tour Traversal of a Binary Tree, 256
6.3.5 The Template Method Pattern, 258
Euler Tour with the Template Method Pattern, 258
Template Method Examples, 259
Java Implementation, 260
6.4 Data Structures for Representing Trees, 263
6.4.1 A Vector-Based Structure for Binary Trees, 263
6.4.2 A Linked Structure for Binary Trees, 265
6.4.3 A Linked Structure for General Trees, 271
6.4.4 Representing General Trees with Binary Trees, 272
6.5 Exercises, 274
7.1 The Priority Queue Abstract Data Type, 287
7.1.1 Keys, Priorities, and Total Order Relations, 287
Comparing Keys with Total Orders, 288
7.1.2 Sorting with a Priority Queue, 289
7.1.3 Methods of a Priority Queue, 290
7.1.4 Compositions and Comparators, 291
The Composition Pattern, 291
The Comparator Pattern, 292
7.2 Implementing a Priority Queue with a Sequence, 295
7.2.1 Implementation with an Unsorted Sequence, 295
7.2.2 Implementation with a Sorted Sequence, 296
Comparing the Two Implementations, 296
7.2.3 Selection-Sort and Insertion-Sort, 298
Selection-Sort, 298
Insertion-Sort, 299
7.3 Heaps, 301
7.3.1 The Heap Data Structure, 301
7.3.2 Implementing a Priority Queue with a Heap, 304
The Vector Representation of a Heap, 305
Insertion, 306
Up-Heap Bubbling after an Insertion, 306
Removal, 308
Down-Heap Bubbling after a Removal, 308
Analysis, 310
7.3.3 Java Implementation, 311
7.3.4 Heap-Sort, 314
Implementing Heap-Sort In-Place, 314
7.3.5 Bottom-Up Heap Construction *, 316
7.4 The Locator Design Pattern *, 319
7.4.1 Locator-Based Priority Queue Methods, 321
Extending the Priority Queue ADT, 321
7.4.2 Implementing Locator-Based Priority Queue Methods, 323
7.5 Exercises, 326
8.1 The Dictionary Abstract Data Type, 335
8.1.1 The Dictionary ADT, 336
Equality Testers, 338
8.1.2 Dictionaries in the java.util Package, 338
Testing for Equality in a java.util.Map, 338
Using null as an Element and Sentinel, 339
Corresponding Methods, 339
8.2 Log Files, 340
Analysis of the Log File Data Structure, 340
8.3 Hash Tables, 341
8.3.1 Bucket Arrays, 342
Analysis of the Bucket Array Structure, 342
8.3.2 Hash Functions, 343
8.3.3 Hash Codes, 343
Hash Codes in Java, 344
Casting to an Integer, 344
Summing Components, 344
Polynomial Hash Codes, 345
Cyclic Shift Hash Codes, 346
8.3.4 Compression Maps, 346
The Division Method, 347
The MAD Method, 348
8.3.5 Collision-Handling Schemes, 348
Separate Chaining, 349
Open Addressing, 351
Linear Probing, 351
Quadratic Probing, 352
Double Hashing, 352
8.3.6 A Java Hash Table Implementation, 353
8.3.7 Load Factors and Rehashing, 356
8.4 The Ordered Dictionary ADT, 357
8.5 Look-Up Tables, 358
8.5.1 Binary Search, 358
8.6 Skip Lists, 362
8.6.1 Searching, 364
8.6.2 Update Operations, 365
Insertion, 365
Removal, 367
Maintaining the Top-most Level, 368
8.6.3 A Probabilistic Analysis of Skip Lists *, 368
8.7 Supporting Locators in a Dictionary *, 370
Locator-Based Dictionary Methods, 370
Key-Based Containers, 371
Implementing Locator-Based Dictionary Methods, 372
8.8 Exercises, 373
9.1 Binary Search Trees, 382
9.1.1 Searching, 383
Analysis of Binary Tree Searching, 384
9.1.2 Update Operations, 385
Insertion, 385
Removal, 386
Best-case versus Worst-case, 388
9.1.3 Java Implementation, 388
9.1.4 Performance, 392
9.2 AVL Trees, 393
Definition, 393
9.2.1 Update Operations, 395
Insertion, 395
Removal, 399
9.2.2 Java Implementation, 400
9.2.3 Performance, 403
9.3 Multi-Way Search Trees, 404
Definition, 404
Searching in a Multi-Way Tree, 406
Data Structures for Multi-Way Search Trees, 406
9.4 (2,4) Trees, 408
9.4.1 Update Operations, 410
Insertion, 410
Analysis of Insertion in a $(2,4)$ Tree, 412
Removal, 413
9.4.2 Performance, 415
9.5 Red-Black Trees, 416
9.5.1 Update Operations, 418
Insertion, 418
Removal, 421
9.5.2 Java Implementation, 430
9.5.3 Performance, 433
9.6 External Searching *, 434
9.6.1 $(a,b)$ Trees, 435
Update Operations, 436
9.6.2 B-Trees, 438
9.7 Exercises, 439
10.1 Merge-Sort, 448
10.1.1 Divide-and-Conquer, 449
Using Divide-and-Conquer for Sorting, 449
Merging Two Sorted Sequences, 455
The Running Time of Merge-Sort, 457
10.1.2 A Java Implementation of Merge-Sort, 458
10.1.3 Merge-Sort and Recurrence Relations *, 460
10.2 The Set ADT, 461
10.2.1 A Simple Set Implementation, 462
Generic Merging as a Template Method Pattern, 464
Performance of Generic Merging, 466
10.3 Quick-Sort, 467
High-Level Description of Quick-Sort, 467
10.3.1 In-Place Quick-Sort, 472
Running Time of Quick-Sort, 475
10.3.2 Randomized Quick-Sort, 476
10.4 A Lower Bound on Comparison-Based Sorting, 478
10.5, Bucket-Sort and Radix-Sort480
10.5.1 Bucket-Sort, 480
Stable Sorting, 481
10.5.2, Radix-Sort481
10.6 Comparison of Sorting Algorithms, 483
10.7 Selection, 484
10.7.1 Prune-and-Search, 485
10.7.2 Randomized Quick-Select, 485
10.7.3 Analyzing Randomized Quick-Select *, 486
10.8 Exercises, 488
11 Text Processing, 495
11.1 String Operations, 497
11.1.1 The Java String Class, 498
11.1.2 The Java StringBuffer Class, 499
11.2 Pattern Matching Algorithms, 500
11.2.1 Brute Force, 500
Brute-Force Pattern Matching, 500
Performance, 501
11.2.2 The Boyer-Moore Algorithm, 502
11.2.3 The Knuth-Morris-Pratt Algorithm, 507
The Failure Function, 507
Performance, 509
Constructing the KMP Failure Function, 510
11.3 Tries, 512
11.3.1 Standard Tries, 512
11.3.2 Compressed Tries, 516
11.3.3 Suffix Tries, 518
Saving Space, 518
Construction, 518
Using a Suffix Trie, 519
Performance, 521
11.3.4 Search Engines, 522
Inverted Files, 522
11.4 Text Compression, 523
11.4.1 The Huffman Coding Algorithm, 524
11.4.2 The Greedy Method, 525
11.5 Text Similarity Testing, 526
11.5.1 The Longest Common Subsequence Problem, 526
Problem Definition, 526
11.5.2 Dynamic Programming, 527
11.5.3 Applying Dynamic Programming to the LCS Problem, 527
The LCS Algorithm, 529
Performance, 529
11.6 Exercises, 531
12 Graphs, 537
12.1 The Graph Abstract Data Type, 539
12.1.1 Graph Methods, 544
General Methods, 545
Methods Dealing with Directed Edges, 545
Methods for Updating Graphs, 546
12.2 Data Structures for Graphs, 547
12.2.1 The Edge List Structure, 547
Vertex Objects, 547
Edge Objects, 548
The Edge List, 548
Performance, 550
12.2.2 The Adjacency List Structure, 551
The Adjacency List, 551
Performance, 553
12.2.3 The Adjacency Matrix Structure, 554
Performance, 556
12.3 Graph Traversal, 557
12.3.1 Depth-First Search, 557
The Decorator Pattern, 561
A Generic DFS Implementation in Java, 562
Using the Template Method Pattern for DFS, 562
12.3.2 Breadth-First Search, 567
Comparing BFS and DFS, 570
12.4 Directed Graphs, 570
Reachability, 570
12.4.1 Traversing a Digraph, 572
Testing for Strong Connectivity, 574
Directed Breadth-First Search, 574
12.4.2 Transitive Closure, 574
Performance of the Floyd-Warshall Algorithm, 577
12.4.3 Directed Acyclic Graphs, 577
12.4.4 Application: Garbage Collection in Java *, 581
The Mark-Sweep Algorithm, 582
Performing DFS In-place, 583
12.5 Weighted Graphs, 584
12.6 Shortest Paths, 585
12.6.1 Dijkstra's Algorithm, 586
A Greedy Method for Finding Shortest Paths, 586
Edge Relaxation, 586
Why It Works, 589
The Running Time of Dijkstra's Algorithm, 591
An Alternative Implementation for Dijkstra's Algorithm, 592
Comparing the Two Implementations, 592
Programming Dijkstra's Algorithm in Java, 592
12.7 Minimum Spanning Trees, 596
Problem Definition, 596
A Crucial Fact about Minimum Spanning Trees, 597
12.7.1 Kruskal's Algorithm, 598
The Running Time of Kruskal's Algorithm, 601
12.7.2 The Prim- Jarnik Algorithm, 602
A Comparison of the Above MST Algorithms, 605
12.8 Exercises, 606
Logarithms and Exponents, 617
Integer Functions and Relations, 618
Summations, 619
Basic Probability, 621
Useful Mathematical Techniques, 623
Sections marked with a star (*) are optional.