Data structures and problem solving using Java

Features

• Contains extensive sample code using Java 1.1, which is available over the Internet and has been tested and reviewed by a professional programmer for accuracy.
• Provides an introduction to Java in Part I and also covers Graphical User Interfaces (GUI's) in an appendix.
• Includes pedagogical aids such as margin notes and comprehensive end-of-chapter material to help readers grasp challenging concepts.
• Offers flexibility in topic coverage by minimizing dependencies among the different chapters.

Table of 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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