Contents

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 7
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 10
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: References 27

2.1 What Is a Reference? 27
2.2 Basics of Objects and References 29
2.2.1 The Dot Operator (.) 30
2.2.2 Declaration of Objects 30
2.2.3 Garbage Collection 31
2.2.4 The Meaning of = 31
2.2.5 Parameter Passing 32
2.2.6 The Meaning of == 33
2.2.7 Operator Overloading for Objects 33
2.3 Strings 33
2.3.1 Basics of String Manipulation 34
2.3.2 String Concatenation 34
2.3.3 Comparing Strings 35
2.3.4 Other String Methods 35
2.3.5 Converting between Strings and Primitive Types 35
2.4 Arrays 36
2.4.1 Declaration, Assignment, and Methods 36
2.4.2 Dynamic Array Expansion 39
2.4.3 Multidimensional Arrays 41
2.4.4 Command-line Arguments 41
2.5 Exception Handling 42
2.5.1 Processing Exceptions 42
2.5.2 The finally Clause 43
2.5.3 Common Exceptions 43
2.5.4 The throw and throws Clauses 44
2.6 Input and Output 45
2.6.1 Basic Stream Operations 46
2.6.2 The StringTokenizer Object 46
2.6.3 Sequential Files 47
Summary 49
Objects of the Game 49
Common Errors 51
On the Internet 51
Exercises 51
References 52

CHAPTER 3: Objects and Classes 53

3.1 What Is Object-oriented Programming? 53
3.2 A Simple Example 55
3.3 Javadoc 57
3.4 Basic Methods 58
3.4.1 Constructors 58
3.4.2 Mutators and Accessors 60
3.4.3 Output and toString 60
3.4.4 equals 62
3.4.5 static Methods 62
3.4.6 main 62
3.5 Packages 62
3.5.1 The import Directive 63
3.5.2 The package Statement 64
3.5.3 The CLASSPATH Environment Variable 65
3.5.4 Package-friendly Visibility Rules 66
3.5.5 Separate Compilation 66
3.6 Additional Constructs 66
3.6.1 The this Reference 66
3.6.2 The this Shorthand for Constructors 67
3.6.3 The instanceof Operator 68
3.6.4 Static Fields 68
3.6.5 Static Initializers 69
Summary 70
Objects of the Game 70
Common Errors 71
On the Internet 72
Exercises 72
References 74

CHAPTER 4: Inheritance 75

4.1 What Is Inheritance? 75
4.2 Basic Java Syntax 78
4.2.1 Visibility Rules 79
4.2.2 The Constructor and super 79
4.2.3 final Methods and Classes 80
4.2.4 Overriding a Method 81
4.2.5 Abstract Methods and Classes 82
4.3 Example: Expanding the Shape Class 84
4.3.1 Digression: An Introduction to Sorting 86
4.4 Multiple Inheritance 90
4.5 The Interface 90
4.5.1 Specifying an Interface 91
4.5.2 Implementing an Interface 91
4.5.3 Multiple Interfaces 94
4.6 Implementing Generic Components 94
Summary 97
Objects of the Game 98
Common Errors 99
On the Internet 100
Exercises 100
References 102

Part II: Algorithms and Building Blocks

CHAPTER 5: Algorithm Analysis 107

5.1 What Is Algorithm Analysis? 107
5.2 Examples of Algorithm Running Times 111
5.3 The Maximum Contiguous Subsequence Sum Problem 113
5.3.1 The Obvious O(N 3) Algorithm 114
5.3.2 An Improved O(N 2) Algorithm 117
5.3.3 A Linear Algorithm 118
5.4 General Big-Oh Rules 121
5.5 The Logarithm 124
5.6 Static Searching Problem 127
5.6.1 Sequential Search 127
5.6.2 Binary Search 128
5.6.3 Interpolation Search 129
5.7 Checking an Algorithm Analysis 131
5.8 Limitations of Big-Oh Analysis 133
Summary 133
Objects of the Game 134
Common Errors 134
On the Internet 135
Exercises 135
References 139

CHAPTER 6: Data Structures 143

6.1 Why Do We Need Data Structures? 143
6.2 Stacks 145
6.2.1 Stacks and Computer Languages 147
6.3 Queues 148
6.4 Linked Lists 150
6.5 General Trees 155
6.6 Binary Search Trees 157
6.7 Hash Tables 161
6.8 Priority Queues 163
Summary 166
Objects of the Game 167
Common Errors 168
On the Internet 168
Exercises 169
References 172

CHAPTER 7: Recursion 173

7.1 What Is Recursion? 173
7.2 Background: Proofs by Mathematical Induction 174
7.3 Basic Recursion 177
7.3.1 Printing Numbers in Any Base 179
7.3.2 Why It Works 180
7.3.3 How It Works 182
7.3.4 Too Much Recursion Can Be Dangerous 183
7.3.5 Additional Examples 185
7.4 Numerical Applications 189
7.4.1 Modular Arithmetic 190
7.4.2 Modular Exponentiation 190
7.4.3 Greatest Common Divisor and Multiplicative Inverses 192
7.4.4 The RSA Cryptosystem 194
7.5 Divide-and-Conquer Algorithms 197
7.5.1 The Maximum Contiguous Subsequence Sum Problem 197
7.5.2 Analysis of a Basic Divide-and-Conquer Recurrence 199
7.5.3 A General Upper Bound for Divide-and-Conquer Running Times 204
7.6 Dynamic Programming 207
7.7 Backtracking Algorithms 211
Summary 214
Objects of the Game 215
Common Errors 217
On the Internet 217
Exercises 218
References 221

CHAPTER 8: Sorting Algorithms 223

8.1 Why Is Sorting Important? 223
8.2 Preliminaries 225
8.3 Analysis of the Insertion Sort and Other Simple Sorts 225
8.4 Shellsort 227
8.4.1 Performance of Shellsort 229
8.5 Mergesort 231
8.5.1 Linear-time Merging of Sorted Arrays 231
8.5.2 The Mergesort Algorithm 234
8.6 Quicksort 235
8.6.1 The Quicksort Algorithm 235
8.6.2 Analysis of Quicksort 236
8.6.3 Picking the Pivot 240
8.6.4 A Partitioning Strategy 241
8.6.5 Keys Equal to the Pivot 244
8.6.6 Median-of-three Partitioning 244
8.6.7 Small Arrays 245
8.6.8 Java Quicksort Routine 246
8.7 Quickselect 248
8.8 A Lower Bound for Sorting 250
Summary 251
Objects of the Game 251
Common Errors 252
On the Internet 252
Exercises 253
References 256

CHAPTER 9: Randomization 259

9.1 Why Do We Need Random Numbers? 259
9.2 Random-number Generators 260
9.3 Nonuniform Random Numbers 265
9.4 Generating a Random Permutation 268
9.5 Randomized Algorithms 269
9.6 Randomized Primality Testing 271
Summary 275
Objects of the Game 275
Common Errors 276
On the Internet 277
Exercises 277
References 279

Part III: Applications

CHAPTER 10: Fun and Games 283

10.1 Word Search Puzzles 283
10.1.1 Theory 283
10.1.2 Java Implementation 288
10.2 The Game of Tic-Tac-Toe 292
10.2.1 Alpha-beta Pruning 292
10.2.2 Transposition Tables 293
10.2.3 Computer Chess 298
Summary 299
Objects of the Game 299
Common Errors 300
On the Internet 300
Exercises 300
References 302

CHAPTER 11: Stacks and Compilers 303

11.1 Balanced-symbol Checker 303
11.1.1 Basic Algorithm 303
11.1.2 Implementation 306
11.2 A Simple Calculator 313
11.2.1 Postfix Machines 314
11.2.2 Infix to Postfix Conversion 316
11.2.3 Implementation 318
11.2.4 Expression Trees 326
Summary 327
Objects of the Game 327
Common Errors 328
On the Internet 328
Exercises 329
References 330

CHAPTER 12: Utilities 331

12.1 File Compression 331
12.1.1 Prefix Codes 332
12.1.2 Huffman's Algorithm 334
12.1.3 The Encoding Phase 337
12.1.4 Decoding Phase 337
12.1.5 Practical Considerations 338
12.2 A Cross-reference Generator 338
12.2.1 Basic Ideas 339
12.2.2 Java Implementation 339
Summary 343
Objects of the Game 345
Common Errors 345
On the Internet 345
Exercises 345
References 348

CHAPTER 13: Simulation 349

13.1 The Josephus Problem 349
13.1.1 The Simple Solution 350
13.1.2 A More Efficient Algorithm 352
13.2 Event-driven Simulation 354
13.2.1 Basic Ideas 354
13.2.2 Example: A Modem Bank Simulation 356
Summary 363
Objects of the Game 363
Common Errors 364
On the Internet 364
Exercises 364

CHAPTER 14: Graphs and Paths 367

14.1 Definitions 367
14.1.1 Representation 369
14.2 Unweighted Shortest-path Problem 379
14.2.1 Theory 382
14.2.2 Java Implementation 386
14.3 Positive-weighted, Shortest-path Problem 387
14.3.1 Theory: Dijkstra's Algorithm 387
14.3.2 Java Implementation 390
14.4 Negative-weighted, Shortest-path Problem 393
14.4.1 Theory 393
14.4.2 Java Implementation 395
14.5 Path Problems in Acyclic Graphs 395
14.5.1 Topological Sorting 396
14.5.2 Theory of the Acyclic Shortest-path Algorithm 398
14.5.3 Java Implementation 399
14.5.4 An Application: Critical-path Analysis 399
Summary 403
Objects of the Game 403
Common Errors 405
On the Internet 405
Exercises 405
References 408

Part IV: Implementations

CHAPTER 15: Stacks and Queues 411

15.1 Dynamic Array Implementations 411
15.1.1 Stacks 411
15.1.2 Queues 416
15.2 Linked-list Implementations 421
15.2.1 Stacks 422
15.2.2 Queues 426
15.3 Comparison of the Two Methods 428
15.4 Double-ended Queues 428
Summary 429
Objects of the Game 430
Common Errors 430
On the Internet 430
Exercises 430

CHAPTER 16: Linked Lists 433

16.1 Basic Ideas 433
16.1.1 Header Nodes 435
16.1.2 Iterator Classes 436
16.2 Java Implementation 437
16.3 Doubly Linked Lists and Circular Linked Lists 445
16.4 Sorted Linked Lists 447
Summary 450
Objects of the Game 450
Common Errors 450
On the Internet 451
Exercises 451

CHAPTER 17: Trees 455

17.1 General Trees 455
17.1.1 Definitions 455
17.1.2 Implementation 457
17.1.3 An Application: File Systems 459
17.2 Binary Trees 463
17.3 Recursion and Trees 468
17.4 Tree Traversal: Iterator Classes 471
17.4.1 Postorder Traversal 474
17.4.2 Inorder Traversal 477
17.4.3 Preorder Traversal 477
17.4.4 Level-order Traversals 481
Summary 483
Objects of the Game 483
Common Errors 484
On the Internet 484
Exercises 485

CHAPTER 18: Binary Search Trees 489

18.1 Basic Ideas 489
18.1.1 The Operations 490
18.1.2 Java Implementation 494
18.2 Order Statistics 500
18.2.1 Java Implementation 500
18.3 Analysis of Binary Search Tree Operations 504
18.4 AVL Trees 508
18.4.1 Properties 509
18.4.2 Single Rotation 511
18.4.3 Double Rotation 512
18.4.4 Summary of AVL Insertion 515
18.5 Red-Black Trees 517
18.5.1 Bottom-up Insertion 518
18.5.2 Top-down Red-Black Trees 520
18.5.3 Java Implementation 522
18.5.4 Top-down Deletion 526
18.6 AA-Trees 530
18.6.1 Insertion 532
18.6.2 Deletion 536
18.6.3 Java Implementation 537
18.7 B-Trees 540
Summary 545
Objects of the Game 546
Common Errors 547
On the Internet 547
Exercises 548
References 550

CHAPTER 19: Hash Tables 553

19.1 Basic Ideas 553
19.2 Hash Function 554
19.3 Linear Probing 557
19.3.1 Naive Analysis of Linear Probing 558
19.3.2 What Really Happens: Primary Clustering 560
19.3.3 Analysis of the find Operation 560
19.4 Quadratic Probing 562
19.4.1 Java Implementation 568
19.4.2 Analysis of Quadratic Probing 572
19.5 Separate Chaining Hashing 573
Summary 573
Objects of the Game 575
Common Errors 575
On the Internet 576
Exercises 576
References 578

CHAPTER 20: A Priority Queue: The Binary Heap 581

20.1 Basic Ideas 581
20.1.1 Structure Property 582
20.1.2 Heap-order Property 584
20.1.3 Allowed Operations 584
20.2 Implementation of the Basic Operations 588
20.2.1 insert 588
20.2.2 deleteMin 591
20.3 fixHeap: Linear Time Heap Construction 593
20.4 Advanced Operations: decreaseKey and merge 598
20.5 Internal Sorting: Heapsort 598
20.6 External Sorting 601
20.6.1 Why We Need New Algorithms 601
20.6.2 Model for External Sorting 602
20.6.3 The Simple Algorithm 602
20.6.4 Multiway Merge 604
20.6.5 Polyphase Merge 604
20.6.6 Replacement Selection 607
Summary 608
Objects of the Game 608
Common Errors 609
On the Internet 610
Exercises 610
References 612

Part V: Advanced Data Structures

CHAPTER 21: Splay Trees 617

21.1 Self-adjustment and Amortized Analysis 617
21.1.1 Amortized Time Bounds 618
21.1.2 A Simple Self-adjusting Strategy (That Does Not Work) 619
21.2 The Basic Bottom-up Splay Tree 621
21.3 Basic Splay Tree Operations 623
21.4 Analysis of Bottom-up Splaying 624
21.4.1 Proof of the Splaying Bound 627
21.5 Top-down Splay Trees 630
21.6 Implementation of Top-down Splay Trees 633
21.7 Comparison of the Splay Tree with Other Search Trees 636
Summary 640
Objects of the Game 640
Common Errors 640
On the Internet 641
Exercises 641
References 642

CHAPTER 22: Merging Priority Queues 643

22.1 The Skew Heap 643
22.1.1 Merging Is Fundamental 643
22.1.2 Simplistic Merging of Heap-ordered Trees 644
22.1.3 The Skew Heap: A Simple Modification 645
22.1.4 Analysis of the Skew Heap 646
22.2 The Pairing Heap 648
22.2.1 Pairing Heap Operations and Theory 649
22.2.2 Implementation of the Pairing Heap 651
22.2.3 Application: Dijkstra's Shortest Weighted Path Algorithm 660
Summary 660
Objects of the Game 661
Common Errors 661
On the Internet 661
Exercises 661
References 662

CHAPTER 23: The Disjoint Set Class 665

23.1 Equivalence Relations 665
23.2 Dynamic Equivalence and Two Applications 666
23.2.1 Application #1: Minimum Spanning Trees 667
23.2.2 Application #2: The Nearest Common Ancestor Problem 669
23.3 The Quick-find Algorithm 672
23.4 The Quick-union Algorithm 674
23.4.1 Smart Union Algorithms 676
23.4.2 Path Compression 677
23.5 Java Implementation 679
23.6 Worst Case for Union-by-rank and Path Compression 681
23.6.1 Analysis of the Union/Find Algorithm 682
Summary 689
Objects of the Game 689
Common Error 690
On the Internet 690
Exercises 690
References 692

APPENDICES

APPENDIX A: Java Platforms 697

A.1 Setting the Environment 697
A.1.1 Unix Instructions 698
A.1.2 Windows 95/NT Instructions 699
A.2 Sun's JDK 700
A.3 Visual Development Environments 700
A.3.1 Symantec Cafe 701
A.3.2 Microsoft Visual J++ 707

APPENDIX B: Operators 713

APPENDIX C: Some Library Routines 715

C.1 Classes in Package java.lang 715
C.1.1 Character 715
C.1.2 Integer 716
C.1.3 Object 717
C.1.4 String 718
C.1.5 StringBuffer 719
C.1.6 System 721
C.1.7 Thread 723
C.1.8 Throwable 723
C.2 Classes in Package java.io 724
C.2.1 BufferedReader 724
C.2.2 File 725
C.2.3 FileReader 726
C.2.4 InputStreamReader 726
C.2.5 PushbackReader 727
C.3 Classes in Package java.util 727
C.3.1 Random 728
C.3.2 StringTokenizer 728
C.3.3 Vector 730
On the Internet 730

APPENDIX D: Graphical User Interfaces 731

D.1 The Abstract Window Toolkit 731
D.2 Basic Objects in the AWT 732
D.2.1 Component 733
D.2.2 Container 734
D.2.3 Top-level Windows 734
D.2.4 Panel 736
D.2.5 Important I/O Components 736
D.3 Basic AWT Principles 741
D.3.1 Layout Managers 741
D.3.2 Graphics 745
D.3.3 Events 747
D.3.4 Summary: Putting the Pieces Together 750
D.4 Animations and Threads 750
D.5 Applets 753
D.5.1 Hypertext Markup Language 753
D.5.2 Parameters 756
D.5.3 Applet Limitations 756
D.5.4 Making an Application an Applet 758
D.5.5 Applets with Animation 760
Summary 762
Objects of the Game 762
Common Errors 764
On the Internet 765
Exercises 766
Reference 768

Index 769

Last Modified: 09:43pm EDT, October 10, 1997