PART I: TOUR OF JAVA
 CHAPTER 1   Primitive Java 3
 1.1 The General Environment 4
 1.2 The First Program 5
 1.2.1  Comments 5
 1.2.2   main 6
 1.2.3  Terminal Output 6
 1.3 Primitive Types 6
 1.3.1  The Primitive Types 6
 1.3.2  Constants 7
 1.3.3  Declaration and Initialization of Primitive Types
 1.3.4  Terminal Input and Output 8
 1.4 Basic Operators 8
 1.4.1  Assignment Operators 9
 1.4.2  Binary Arithmetic Operators 10
 1.4.3  Unary Operators l0
 1.4.4  Type Conversions 10
 1.5 Conditional Statements 11
 1.5.1  Relational and Equality Operators 11
 1.5.2  Logical Operators 12
 1.5.3  The if Statement 13
 1.5.4  The while Statement 14
 1.5.5  The for Statement 14
 1.5.6  The do Statement 15
 1.5.7  break and continue 16
 1.5.8  The switch Statement 17
 1.5.9  The Conditional Operator 17
 1.6 Methods 18
 1.6.1  Overloading of Method Names 19
 1.6.2  Storage Classes 20
 Summary 20
 Objects of the Game 20
 Common Errors 22
 On the Internet 23
 Exercises 23
 References 25
 CHAPTER 2   Reference Types 27
 2.1 What Is a Reference? 27
 2.2 Basics of Objects and References 30
 2.2.1  TheDotOperator(.) 30
 2.2.2  Declaration of Objects 30
 2.2.3  Garbage Collection 31
 2.2.4  The Meaning of= 32
 2.2.5  Parameter Passing 33
 2.2.6  The Meaning of== 33
 2.2.7  No Operator Overloading for Objects 34
 2.3 Strings 35
 2.3.1  Basics of String Manipulation 35
 2.3.2  String Concatenation 35
 2.3.3  Comparing Strings 36
 2.3.4  Other Stri no Methods 36
 2.3.5  Converting Other Types of Strings 37
 2.4 Arrays 37
 2.4.1  Declaration, Assignment, and Methods 38
 2.4.2  Dynamic Array Expansion 40
 2.4.3   ArrayList 43
 2.4.4  Multidimensional Arrays 45
 2.4.5  Command-line Arguments 45
 2.5 Exception Handling 47
 2.5.1  Processing Exceptions 47
 2.5.2  The finally Clause 47
 2.5.3  Common Exceptions 49
 2.5.4  The throw and throws Clauses 50
 2.6 Input and Output 50
 2.6.1  Basic Stream Operations 51
 2.6.2  The 5tringl0kenizer Type 52
 2.6.3  Sequential Files 53
 Summary 55
 Objects of the Game 57
 Common Errors 58
 On the Internet 59
 Exercises 59
 References 60
 CHAPTER 3    Objects and Classes 61
 3.1 What Is Object-Oriented Programming? 61
 3.2 A Simple Example 63
 3.3 Javadoc 65
 3.4 Basic Methods 68
 3.4.1  Constructors 68
 3.4.2  Mutators and Accessors 68
 3.4.3  OutputandtOString 70
 3.4.4  equals 70
 3.4.5  main 70
 3.4.6  Static Fields and Methods 71
 3.5 Additional Constructs 71
 3.5.1  The this Reference 71
 3.5.2  The this Shorthand for Constructors 72
 3.5.3  The i nstance0f Operator 72
 3.5.4  Instance Members vs. Static Members 73
 3.5.5  Static Fields and Methods 73
 3.5.6  Static Initializers 74
 3.6 Packages 76
 3.6.1  The import Directive 76
 3.6.2  The package Statement 78
 3.6.3  The CLASSPATH Environment Variable 78
 3.6.4  Package Visibility Rules 79
 3.7 A Design Pattern: Composite (Pair) 80
 Summary 81
 Objects of the Game 83
 Common Errors 84
 On the Internet 85
 Exercises 85
 References 88
 CHAPTER 4   Inheritance 89
 4.1 What Is Inheritance? 90
 4.1.1  Creating New Classes 90
 4.1.2  Type Compatibility 95
 4.1.3  Dynamic Binding and Polymorphism 96
 4.1.4  Inheritance Hierarchies 97
 4.1.5  Visibility Rules 97
 4.1.6  The Constructor and super 98
 4.1.7  fi nal Methods and Classes 99
 4.1.8  Overriding a Method 100
 4.1.9  Type Compatibility Revisited 101
 4.2 Designing Hierarchies 103
 4.2.1  Abstract Methods and Classes 107
 4.3 Multiple Inheritance 109
 4.4 The Interface 110
 4.4.1  Specifying an Interface 110
 4.4.2  Implementing an Interface 111
 4.4.3  Multiple Interfaces 112
 4.4.4  Interfaces are Abstract Classes 112
 4.5 Fundamental Inheritance in Java 113
 4.5.1  The Object Class 113
 4.5.2  The Hierarchy of Exceptions 113
 4.5.3  I/O: The Decorator Pattern 113
 4.6 Implementing Generic Components 118
 4.6.1  Using Object for Genericity 119
 4.6.2  Wrappers for Primitive Types 120
 4.6.3  Adapters: Changing an Interface 120
 4.6.4  Using Interface Types for Genericity 123
 4.7 The Functor (Function Objects) 125
 4.7.1  Nested Classes 128
 4.7.2  Local Classes 129
 4.7.3  Anonymous Classes 130
 4.8 Dynamic Binding Details 131
 Summary 135
 Objects of the Game 136
 Common Errors 138
 On the Internet 138
 Exercises 140
 References 144
 PART II: ALGORITHMS AND BUILDING BLOCKS
 CHAPTER 5 Algorithm Analysis 147
 5.1 What Is Algorithm Analysis? 148
 5.2 Examples of Algorithm Running Times 151
 5.3 The Maximum Contiguous Subsequence Sum Problem 153
 5.3.1  The Obvious O(N 3) Algorithm 154
 5.3.2  An Improved O(N 2) Algorithm 157
 5.3.3  A Linear Algorithm 158
 5.4 General Big-Oh Rules 160
 5.5 The Logarithm 164
 5.6 Static Searching Problem 167
 5.6.1  Sequential Search 167
 5.6.2  Binary Search 168
 5.6.3  Interpolation Search 170
 5.7 Checking an Algorithm Analysis 171
 5.8 Limitations of Big-Oh Analysis 173
 Summary 174
 Objects of the Game 174
 Common Errors 175
 On the Internet 175
 Exercises 176
 References 181
 CHAPTER 6  The Collections APl 183
 6.1 Introduction 184
 6.2 The Iterator Pattern 185
 6.2.1  Basic Iterator Design 186
 6.2.2  Inheritance-based Iterators and Factories 188
 6.3 Collections API: Containers and Iterators 190
 6.3.1  The Collection Interface 190
 6.3.2  Iterator Interface 193
 6.4 Generic Algorithms 195
 6.4.1  C0mparator Function Objects 195
 6.4.2  The Collections Class 195
 6.4.3  Binary Search 198
 6.4.4  Sorting 199
 6.5 The List Interface 199
 6.5.1  The Listlterat0r Interface 201
 6.5.2  kinkedLiist Class 202
 6.6 Stacks and Queues 205
 6.6.1  Stacks 205
 6.6.2  Stacks and Computer Languages 206
 6.6.3  Queues 208
 6.6.4  Stacks and Queues in the Collections API 208
 6.7 Sets 209
 6.7.1  ThelreeSet Class 210
 6.7.2  The HashSet Class 211
 6.8 Maps 216
 6.9 Priority Queues 220
 Summary 224
 Objects of the Game 225
 Common Errors 226
 On the Internet 226
 Exercises 227
 References 230
 CHAPTER 7  Recursion 231
 7.1 What Is Recursion? 232
 7.2 Background: Proofs by Mathematical Induction 233
 7.3 Basic Recursion 235
 7.3.1  Printing Numbers in Any Base 237
 7.3.2  Why It Works 239
 7.3.3  How It Works 241
 7.3.4  Too Much Recursion Can Be Dangerous 242
 7.3.5  Preview of Trees 243
 7.3.6  Additional Examples 244
 7.4 Numerical Applications 248
 7.4.1  Modular Arithmetic 250
 7.4.2  Modular Exponentiation 250
 7.4.3  Greatest Common Divisor and Multiplicative Inverses 252
 7.4.4  The RSA Cryptosystem 254
 7.5 Divide-and-Conquer Algorithms 257
 7.5.1  The Maximum Contiguous Subsequence Sum Problem 258
 7.5.2  Analysis of a Basic Divide-and-Conquer Recurrence 260
 7.5.3  A General Upper Bound for Divide-and-Conquer Running
 Times 265
 7.6 Dynamic Programming 267
 7.7 Backtracking 272
 Summary 276
 Objects of the Game 276
 Common Errors 277
 On the Internet 278
 Exercises 278
 References 282
 CHAPTER 8  Sorting Algorithms 283
 8.1 Why Is Sorting Important? 284
 8.2 Preliminaries 285
 8.3 Analysis of the Insertion Sort and Other Simple Sorts 285
 8.4 Shellsort 289
 8.4.1  Performance of Shellsort 290
 8.5 Mergesort 293
 8.5.1  Linear-Time Merging of Sorted Arrays 293
 8.5.2  The Mergesort Algorithm 295
 8.6 Quicksort 295
 8.6.1  The Quicksort Algorithm 296
 8.6.2  Analysis of Quicksort 299
 8.6.3  Picking the Pivot 303
 8.6.4  A Partitioning Strategy 304
 8.6.5  Keys Equal to the Pivot 307
 8.6.6  Median-of-Three Partitioning 307
 8.6.7  Small Arrays 308
 8.6.8  Java Quicksort Routine 309
 8.7 Quickselect 311
 8.8 A Lower Bound for Sorting 312
 Summary 314
 Objects of the Game 315
 Common Errors 315
 On the Internet 316
 Exercises 316
 References 320
 CHAPTER 9  Randomization 323
 9.1 Why Do We Need Random Numbers? 323
 9.2 Random Number Generators 324
 9.3 Nonuniform Random Numbers 330
 9.4 Generating a Random Permutation 333
 9.5 Randomized Algorithms 334
 9.6 Randomized Primality Testing 337
 Summary 340
 Objects of the Game 340
 Common Errors 341
 On the Internet 342
 Exercises 342
 References 344
 PART III: APPLICATIONS
 CHAPTER 10 Fun and Games 347
 10.1 Word Search Puzzles 347
 10.1.1 Theory 348
 10.1.2 Java Implementation 350
 10.2 The Game of Tic-Tac-Toe 350
 10.2.1 Alpha-Beta Pruning 353
 10.2.2 Transposition Tables 359
 10.2.3 Computer Chess 362
 Summary 364
 Objects of the Game 364
 Common Errors 364
 On the Internet 365
 Exercises 365
 References 367
 CHAPTER 11  Stacks and Compilers 369
 11.1 Balanced-Symbol Checker 369
 11.1.1 Basic Algorithm 370
 11.1.2 Implementation 371
 11.2 A Simple Calculator 380
 11.2.1 Postfix Machines 382
 11.2.2 Infix to Postfix Conversion 383
 11.2.3 Implementation 386
 11.2.4 Expression Trees 391
 Summary 395
 Objects of the Game 396
 Common Errors 396
 On the Internet 397
 Exercises 397
 References 398
 CHAPTER 12  Utilities 399
 12.1 File Compression 399
 12.1.1 Prefix Codes 401
 12.1.2 Huffman's Algorithm 403
 12.1.3 Implementation 405
 12.2 A Cross-Reference Generator 420
 12.2.1 Basic Ideas 420
 12.2.2 Java Implementation 420
 Summary 424
 Objects of the Game 425
 Common Errors 425
 On the Internet 425
 Exercises 425
 References 428
 CHAPTER 13 Simulation 429
 13.1 The Josephus Problem 429
 13.1.1 The Simple Solution 431
 13.1.2 A More Efficient Algorithm 431
 13.2 Event-Driven Simulation 435
 13.2.1 Basic Ideas 435
 13.2.2 Example: A Modem Bank Simulation 436
 Summary 444
 Objects of the Game 444
 Common Errors 444
 On the Internet 444
 Exercises 445
 CHATPTER 14 Graphs and Paths 447
 14.1 Definitions 448
 14.1.1 Represent. ation 449
 14.2 Unweighted Shortest-Path Problem 459
 14.2.1 Theory 462
 14.2.2 Java Implementation 466
 14.3 Positive-Weighted, Shortest-Path Problem 467
 14.3.1 Theory: Dijkstra's Algorithm 467
 14.3.2 Java Implementation 469
 14.4 Negative-Weighted, Shortest-Path Problem 471
 14.4.1 Theory 473
 14.4.2 Java Implementation 474
 14.5 Path Problems in Acyclic Graphs 474
 14.5.1 Topological Sorting 474
 14.5.2 Theory of the Acyclic Shortest-Path Algorithm 476
 14.5.3 Java Implementation 478
 14.5.4 An Application: Critical-PathAnalysis 480
 Summary 483
 Objects of the Game 483
 Common Errors 485
 On the Internet 485
 Exercises 485
 References 489
 PART IV: IMPLEMENTATIONS
 CHATPTER 15 Inner Classes and Implementation of ArrayList 493
 15.1 Iterators and Nested Classes 493
 15.2 Iterators and Inner Classes 495
 15.3 The abstractCOllection Class 500
 15.4 Implementation of ArrayList with an Iterator 500
 Summary 508
 ~ 13 ~
 Objects of the Game 508
 Common Error 508
 On the Internet 509
 Exercises 509
 CHATPTER  16 Stacks andOueues 513
 16.1 Dynamic Array Implementations 513
 16.1.1 Stacks 514
 16.1.2 Queues 518
 16.2 Linked List Implementations 524
 16.2.1 Stacks 524
 16.2.2 Queues 525
 16.3 Comparison of the Two Methods 530
 16.4 The java.uti1 .Stack Class 531
 16.5 Double-Ended Queues 533
 Summary 534
 Objects of the Game 534
 Common Errors 534
 On the Internet 534
 Exercises 535
 CHAPTER 17 Linked Lists 537
 17.1 Basic Ideas 537
 17.1.1 Header Nodes 539
 17.1.2 IteratorClasses 541
 17.2 Java Implementation 542
 17.3 Doubly Linked Lists and Circularly Linked Lists 548
 17.4 Sorted Linked Lists 551
 17.5 Implementing the Collections API linkedlist Class 551
 Summary 563
 Objects of the Game 563
 Common Errors 563
 On the Internet 563
 Exercises 564
 CHAPTER 18 Trees 569
 18.1 General Trees 569
 18.1.1 Definitions 570
 18.1.2 Implementation 571
 18.1.3 An Application: File Systems 572
 18.2 Binary Trees 576
 18.3 Recursion and Trees 582
 18.4 Tree Traversal: Iterator Classes 585
 18.4.1 Postorder Traversal 589
 18.4.2 InorderTraversal 592
 18.4.3 Preorder Traversal 592
 18.4.4 Level-OrderTraversals 596
 Summary 597
 Objects of the Game 598
 Common Errors 599
 On the Internet 599
 Exercises 600
 CHATPTER 19 Binary Search Trees 603
 19.1 Basic Ideas 603
 19.1.1 The Operations 604
 19.1.2 Java Implementation 606
 19.2 Order Statistics 613
 19.2.1 Java Implementation 614
 19.3 Analysis of Binary Search Tree Operations 618
 19.4 AVL Trees 621
 19.4.1 Properties 622
 19.4.2 Single Rotation 624
 19.4.3 Double Rotation 627
 19.4.4 Summary of AVL Insertion 630
 19.5 Red-Black Trees 630
 19.5.1 Bottom-Up Insertion 631
 19.5.2 Top-Down Red-Black Trees 634
 19.5.3 Java Implementation 636
 19.5.4 Top-DownDeletion 641
 19.6 AA-Trees 644
 19.6.1 Insertion 646
 19.6.2 Deletion 648
 19.6.3 Java Implementation 649
 19.7 Implementing the Collections API lreeSet and IreeYap
 Classes 654
 19.8 B-Trees 663
 Summary 675
 Objects of the Game 676
 Common Errors 677
 On the Internet 677
 Exercises 678
 References 680
 CHAPTER 20 Hash Tables 683
 20.1 Basic Ideas 684
 20.2 Hash Function 685
 20.3 Linear Probing 687
 20.3.1 Naive Analysis of Linear Probing 689
 20.3.2 What Really Happens: Primary Clustering 690
 20.3.3 Analysis of the find Operation 691
 20.4 Quadratic Probing 693
 20.4.1 Java Implementation 697
 20.4.2 Analysis of Quadratic Probing 703
 20.5 Separate Chaining Hashing 706
 20.6 Hash Tables Versus Binary Search Trees 707
 20.7 Hashing Applications 707
 Summary 708
 Objects of the Game 708
 Common Errors 709
 On the Internet 710
 Exercises 710
 References 712
 CHATPTER 21 A Priority Queue: The Binary Heap 715
 21.1 Basic Ideas 716
 21.1.1 Structure Property 716
 21.1.2 Heap-Order Property 718
 21.1.3 Allowed Operations  718
 21.2 Implementation of the Basic Operations 721
 21.2.1 The insert Operation 722
 21.2.2 The del eteMin Operation 723
 21.3 The build.ap Operation: Linear-Time Heap Construction 726
 21.4 Advanced Operations: decreaseKey and merge 731
 21.5 Internal Sorting: Heapsort 731
 21.6 External Sorting 734
 21.6.1 Why We Need New Algorithms 734
 21.6.2 Model for External Sorting 735
 21.6.3 The Simple Algorithm 735
 21.6.4 MultiwayMerge 737
 21.6.5 Polyphase Merge 738
 21.6.6 Replacement Selection 740
 Summary 741
 Objects of the Game 741
 Common Errors 742
 On the Internet 742
 Exercises 743
 References 747
 PART V: ADVANCED DATA STRUCTURES
 CHATPTER 22 Splay Trees 751
 22.1 Self-Adjustment and Amortized Analysis 752
 22.1.1 Amortized Time Bounds 753
 22.1.2 A Simple Self-Adjusting Strategy (That Does Not
 Work) 753
 22.2 The Basic Bottom-Up Splay Tree 755
 22.3 Basic Splay Tree Operations 758
 22.4 Analysis of Bottom-Up Splaying 759
 22.4.1 Proof of the Splaying Bound 762
 22.5 Top-Down Splay Trees 765
 22.6 Implementation of Top-Down Splay Trees 768
 22.7 Comparison of the Splay Tree with Other Search Trees 771
 Summary 773
 Objects of the Game 773
 Common Errors 776
 On the Internet 776
 Exercises 776
 References 777
 CHATPTER 23 Merging Priority Queues 779
 23.1 The Skew Heap 779
 23.1.1 Merging Is Fundamental 780
 23.1.2 Simplistic Merging of Heap-Ordered Trees 780
 23.1.3 The Skew Heap: A Simple Modification 781
 23.1.4 Analysis of the Skew Heap 782
 23.2 The Pairing Heap 784
 23.2.1 Pairing Heap Operations 785
 23.2.2 Implementation of the Pairing Heap 786
 23.2.3 Application: Dijkstra's Shortest Weighted Path
 Algorithm 791
 Summary 796
 Objects of the Game 796
 Common Errors 796
 On the Internet 797
 Exercises 797
 References 798
 CHAPTER 24 The Oisjoint Set Class 801
 24.1 Equivalence Relations 802
 24.2 Dynamic Equivalence and Applications 802
 24.2.1 Application: Generating Mazes 803
 24.2.2 Application: Minimum Spanning Trees 806
 24.2.3 Application: The Nearest Common Ancestor Problem 809
 24.3 The Quick-Find Algorithm 813
 24.4 The Quick-Union Algorithm 814
 24.4.1 Smart Union Algorithms 815
 24.4.2 Path Compression 817
 24.5 Java Implementation 818
 24.6 Worst Case for Union-by-Rank and Path Compression 821
 24.6.1 Analysis of the Union/Find Algorithm 822
 Summary 828
 Objects of the Game 829
 Common Errors 830
 On the Internet 830
 Exercises 830
 References 833
 APPENDICES
 APPENDIX A Operators 835
 APPENDIX B Graphical User Interfaces 837
 B.1 The Abstract Window Toolkit and Swing 838
 B.2 Basic Objects in Swing 839
 B.2.1  Component 839
 B.2.2  Container 841
 B.2.3  Top-level Containers 841
 B.2.4  jPanel 842
 B.2.5  Important I/O Components 843
 B.3 Basic Principles 848
 B.3.1  Layout Managers 848
 B.3.2  Graphics 852
 B.3.3  Events 853
 B.3.4  Event Handling: Adapters and Anonymous Inner
 Classes 856
 B.3.5  Summary: Putting the Pieces Together 859
 B.3.6  Is This Everything I Need To Know About Swing? 860
 Summary 860
 Objects of the Game 861
 Common Errors 863
 On the Internet 863
 Exercises 863
 Reference 865
 APPENDIX C BitwiseOperators 867
 Index 871