part one Tour of Java 3
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
key concepts 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 the dot operator(.) 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 String methods 36
2.3.5 converting other types to 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 42
2.4.4 multidimensional arrays 45
2.4.5 command-line arguments 45
2.4.6 enhanced for loop 46
2.5 exception handling 47
2.5.1 processing exceptions 48
2.5.2 the finally clause 48
2.5.3 common exceptions 49
2.5.4 the throw and throws clauses 51
2.6 input and output 51
2.6.1 basic stream operations 52
2.6.2 the Scanner type 53
2.6.3 sequential files 56
summary 59
key concepts 60
common errors 61
on the internet 62
exercises 62
references 68
Chapter 3 objects and classes 69
3.1 what is object-oriented programming? 69
3.2 a simple example 71
3.3 javadoc 73
3.4 basic methods 76
3.4.1 constructors 76
3.4.2 mutators and accessors 76
3.4.3 output and toString 78
3.4.4 equals 78
3.4.5 main 78
3.5 example:using java.math.BigInteger 78
3.6 additional constructs 79
3.6.1 the this reference 81
3.6.2 the this shorthand for constructors 82
3.6.3 the instanceof operator 82
3.6.4 instance members versus static members 83
3.6.5 static fields and methods 83
3.6.6 static initializers 86
3.7 example:implementing a BigRational class 86
3.8 packages 90
3.8.1 the import directive 91
3.8.2 the package statement 93
3.8.3 the CLASSPATH environment variable 94
3.8.4 package visibility rules 95
3.9 a design pattern:composite(pair) 95
summary 96
key concepts 97
common errors 100
on the internet 100
exercises 101
references 107
Chapter 4 inheritance 109
4.1 what is inheritance? 110
4.1.1 creating new classes 110
4.1.2 type compatibility 115
4.1.3 dynamic dispatch and polymorphism 116
4.1.4 inheritance hierarchies 117
4.1.5 visibility rules 117
4.1.6 the constructor and super 118
4.1.7 final methods and classes 119
4.1.8 overriding a method 121
4.1.9 type compatibility revisited 121
4.1.10 compatibility of array types 124
4.1.11 covariant return types 124
4.2 designing hierarchies 125
4.2.1 abstract methods and classes 126
4.2.2 designing for the future 130
4.3 multiple inheritance 131
4.4 the interface 134
4.4.1 specifying an interface 134
4.4.2 implementing an interface 135
4.4.3 multiple interfaces 135
4.4.4 interfaces are abstract classes 136
4.5 fundamental inheritance in java 136
4.5.1 the Object class 136
4.5.2 the hierarchy of exceptions 137
4.5.3 i/o:the decorator pattern 138
4.6 implementing generic components using inheritance 142
4.6.1 using Object for genericity 142
4.6.2 wrappers for primitive types 143
4.6.3 autoboxing/unboxing 145
4.6.4 adapters:changing an interface 146
4.6.5 using interface types for genericity 147
4.7 implementing generic components using java 5 generics 150
4.7.1 simple generic classes and interfaces 150
4.7.2 wildcards with bounds 151
4.7.3 generic static methods 152
4.7.4 type bounds 153
4.7.5 type erasure 154
4.7.6 restrictions on generics 154
4.8 the functor(function objects) 157
4.8.1 nested classes 161
4.8.2 local classes 161
4.8.3 anonymous classes 163
4.8.4 nested classes and generics 164
4.9 dynamic dispatch details 164
summary 168
key concepts 168
common errors 171
on the internet 171
exercises 173
references 183
part two Algorithms and Building BlocksChapter 5 algorithm analysis 187
5.1 what is algorithm analysis? 188
5.2 examples of algorithm running times 192
5.3 the maximum contiguous subsequence sum problem 193
5.3.1 the obvious O(N3)algorithm 194
5.3.2 an improved O(N2)algorithm 197
5.3.3 a linear algorithm 197
5.4 general big-oh rules 201
5.5 the logarithm 205
5.6 static searching problem 207
5.6.1 sequential search 207
5.6.2 binary search 208
5.6.3 interpolation search 211
5.7 checking an algorithm analysis 212
5.8 limitations of big-oh analysis 213
summary 214
key concepts 214
common errors 215
on the internet 216
exercises 216
references 227
Chapter 6 the collections api 229
6.1 introduction 230
6.2 the iterator pattern 231
6.2.1 basic iterator design 232
6.2.2 inheritance-based iterators and factories 234
6.3 collections api:containers and iterators 236
6.3.1 the Collecti on interface 237
6.3.2 Iterator interface 240
6.4 generic algorithms 242
6.4.1 Comparator function objects 243
6.4.2 the Collections class 243
6.4.3 binary search 246
6.4.4 sorting 246
6.5 the List interface 248
6.5.1 the ListIterator interface 249
6.5.2 LinkedList class 251
6.5.3 running time for Lists 253
6.5.4 removing from and adding to the middle of a List 256
6.6 stacks and queues 258
6.6.1 stacks 258
6.6.2 stacks and computer languages 259
6.6.3 queues 260
6.6.4 stacks and queues in the collections api 261
6.7 sets 261
6.7.1 the TreeSet class 263
6.7.2 the HashSet class 264
6.8 maps 268
6.9 priority queues 274
6.10 views in the collections api 277
6.10.1 the subList method for Lists 277
6.10.2 the headSet,subSet,and tailSet methods for SortedSets 277
summary 278
key concepts 279
common errors 280
on the internet 281
exercises 281
references 292
Chapter 7 recursion 293
7.1 what is recursion? 294
7.2 background:proofs by mathematical induction 295
7.3 basic recursion 297
7.3.1 printing numbers in any base 299
7.3.2 why it works 301
7.3.3 how it works 302
7.3.4 too much recursion can be dangerous 304
7.3.5 preview of trees 305
7.3.6 additional examples 306
7.4 numerical applications 311
7.4.1 modular arithmetic 311
7.4.2 modular exponentiation 312
7.4.3 greatest common divisor and multiplicative inverses 314
7.4.4 the rsa cryptosystem 317
7.5 divide-and-conquer algorithms 319
7.5.1 the maximum contiguous subsequence sum problem 320
7.5.2 analysis of a basic divide-and-conquer recurrence 323
7.5.3 a general upper bound for divide-and-conquer running times 327
7.6 dynamic programming 329
7.7 backtracking 333
summary 336
key concepts 338
common errors 339
on the internet 339
exercises 340
references 348
Chapter 8 sorting algorithms 351
8.1 why is sorting important? 352
8.2 preliminaries 353
8.3 analysis of the insertion sort and other simple sorts 353
8.4 shellsort 357
8.4.1 performance of shellsort 358
8.5 mergesort 361
8.5.1 linear-time merging of sorted arrays 361
8.5.2 the mergesort algorithm 363
8.6 quicksort 364
8.6.1 the quicksort algorithm 367
8.6.2 analysis of quicksort 369
8.6.3 picking the pivot 372
8.6.4 a partitioning strategy 374
8.6.5 keys equal to the pivot 376
8.6.6 median-of-three partitioning 376
8.6.7 small arrays 377
8.6.8 java quicksort routine 378
8.7 quickselect 380
8.8 a lower bound for sorting 381
summary 383
key concepts 384
common errors 385
on the internet 385
exercises 385
references 391
Chapter 9 randomization 393
9.1 why do we need random numbers? 393
9.2 random number generators 394
9.3 nonuniform randam numbers 402
9.4 generating a random permutation 404
9.5 randomized algorithms 406
9.6 randomized primality testing 409
summary 412
key concepts 412
common errors 413
on the internet 414
exercises 414
references 417
part three Applications 421
Chapter 10 fun and games 421
10.1 word search puzzles 421
10.1.1 theory 422
10.1.2 java implementation 423
10.2 the game of tic-tac-toe 427
10.2.1 alpha-beta pruning 428
10.2.2 transposition tables 431
10.2.3 computer chess 435
summary 438
key concepts 438
common errors 438
on the internet 438
exercises 439
references 441
Chapter 11 stacks and compilers 443
11.1 balanced-symbol checker 443
11.1.1 basic algorithm 444
11.1.2 implementation 445
11.2 a simple calculator 454
11.2.1 postfix machines 456
11.2.2 infix to postfix conversion 457
11.2.3 implementation 459
11.2.4 expression trees 468
summary 469
key concepts 470
common errors 470
on the internet 471
exercises 471
references 472
Chapter 12 utilities 473
12.1 file compression 474
12.1.1 prefix codes 475
12.1.2 huffman's algorithm 477
12.1.3 implementation 479
12.2 a cross-reference generator 495
12.2.1 basic ideas 495
12.2.2 iava implementation 495
summary 499
key concepts 500
common errors 500
on the internet 500
exercises 500
references 506
Chapter 13 simulation 507
13.1 the josephus problem 507
13.1.1 the simple solution 509
13.1.2 a more efficient algorithm 509
13.2 event-driven simulation 513
13.2.1 basic ideas 513
13.2.2 example:a call bank simulation 514
summary 522
key concepts 522
common errors 523
on the internet 523
exercises 523
Chapter 14 graphs and paths 527
14.1 definitions 528
14.1.1 representation 530
14.2 unweighted shortest-path problem 539
14.2.1 theory 539
14.2.2 java implementation 545
14.3 positive-weighted,shortest-path problem 545
14.3.1 theory:dijkstra's algorithm 546
14.3.2 java implementation 550
14.4 negative-weighted,shortest-path problem 552
14.4.1 theory 552
14.4.2 java implementation 553
14.5 path problems in acyclic graphs 555
14.5.1 topological sorting 555
14.5.2 theory of the acyclic shortest-path algorithm 557
14.5.3 java implementation 557
14.5.4 an application:critical-path analysis 560
summary 562
key concepts 563
common errors 564
on the internet 565
exercises 565
references 569
part four ImplementationsChapter 15 inner classes and implementation of ArrayList 573
15.1 iterators and nested classes 574
15.2 iterators and inner classes 576
15.3 the AbstractCollection class 580
15.4 StringBuilder 584
15.5 implementation of ArrayList with an iterator 585
summary 590
key concepts 591
common errors 591
on the internet 591
exercises 591
Chapter 16 stacks and queues 595
16.1 dynamic array implementations 595
16.1.1 stacks 596
16.1.2 queues 600
16.2 linked list implementations 605
16.2.1 stacks 606
16.2.2 queues 609
16.3 comparison of the two methods 613
16.4 the java.util.Stack class 613
16.5 double-ended queues 615
summary 615
key concepts 615
common errors 615
on the internet 616
exercises 616
Chapter 17 linked lists 619
17.1 basic ideas 619
17.1.1 header nodes 621
17.1.2 iterator classes 622
17.2 java implementation 624
17.3 doubly linked lists and circularly linked lists 630
17.4 sorted linked lists 633
17.5 implementing the collections api LinkedList class 635
summary 646
key concepts 646
common errors 647
on the internet 647
exercises 647
Chapter 18 trees 651
18.1 general trees 651
18.1.1 definitions 652
18.1.2 implementation 653
18.1.3 an application:file systems 654
18.2 binary trees 658
18.3 recursion and trees 665
18.4 tree traversal:iterator classes 667
18.4.1 postorder traversal 671
18.4.2 inorder traversal 675
18.4.3 preorder traversal 675
18.4.4 level-order traversals 678
summary 679
key concepts 680
common errors 681
on the internet 682
exercises 682
Chapter 19 binary search trees 687
19.1 basic ideas 687
19.1.1 the operations 688
19.1.2 java implementation 690
19.2 order statistics 697
19.2.1 java implementation 698
19.3 analysis of binary search tree operations 702
19.4 avl trees 706
19.4.1 properties 707
19.4.2 single rotation 709
19.4.3 double rotation 712
19.4.4 summary of avl insertion 714
19.5 red-black trees 715
19.5.1 bottom-up insertion 716
19.5.2 top-down red-black trees 718
19.5.3 java implementation 719
19.5.4 top-down deletion 726
19.6 aa-trees 728
19.6.1 insertion 730
19.6.2 deletion 732
19.6.3 java implementation 733
19.7 implementing the collections api TreeSet and TreeMap classes 738
19.8 b-trees 756
summary 762
key concepts 763
common errors 764
on the internet 764
exercises 765
references 769
Chapter 20 hash tables 773
20.1 basic ideas 774
20.2 hash function 775
20.2.1 headCode in java.lang.String 777
20.3 linear probing 779
20.3.1 naive analysis of linear probing 780
20.3.2 what really happens:primary clustering 781
20.3.3 analysis of the find operation 782
20.4 quadratic probing 784
20.4.1 java implementation 788
20.4.2 analysis of quadratic probing 797
20.5 separate chaining hashing 797
20.6 hash tables versus binary search trees 798
20.7 hashing applications 800
summary 800
key concepts 801
common errors 802
on the internet 802
exercises 802
references 805
Chapter 21 a priority queue:the binary heap 807
21.1 basic ideas 808
21.1.1 structure property 808
21.1.2 heap-order property 810
21.1.3 allowed operations 811
21.2 implementation of the basic operations 814
21.2.1 insertion 814
21.2.2 the del eteMin operation 816
21.3 the buildHeap operation:linear-time heap construction 818
21.4 advanced operations:decreaseKey and merge 823
21.5 internal sorting:heapsort 823
21.6 external sorting 826
21.6.1 why we need new algorithms 826
21.6.2 model for external sorting 827
21.6.3 the simple algorithm 827
21.6.4 multiway merge 829
21.6.5 polyphase merge 830
21.6.6 replacement selection 832
summary 833
key concepts 834
common errors 834
on the internet 835
exercises 835
references 839
part five Advanced Data StructuresChapter 22 splay trees 843
22.1 self-adjustment and amortized analysis 844
22.1.1 amortized time bounds 845
22.1.2 a simple self-adjusting strategy(that does not work) 845
22.2 the basic bottom-up splay tree 847
22.3 basic splay tree operations 850
22.4 analysis of bottom-up splaying 851
22.4.1 proof of the splaying bound 854
22.5 top-down splay trees 857
22.6 implementation of top-down splay trees 860
22.7 comparison of the splay tree with other search trees 865
summary 866
key concepts 866
common errors 867
on the internet 867
exercises 867
references 868
Chapter 23 merging priority queues 871
23.1 the skew heap 871
23.1.1 merging is fundamental 872
23.1.2 simplistic merging of heap-ordered trees 872
23.1.3 the skew heap:a simple modification 873
23.1.4 analysis of the skew heap 874
23.2 the pairing heap 876
23.2.1 pairing heap operations 877
23.2.2 implementation of the pairing heap 878
23.2.3 application:dijkstra's shortest weighted path algorithm 884
summary 888
key concepts 888
common errors 888
on the internet 889
exercises 889
references 890
Chapter 24 the disjoint set class 893
24.1 equivalence relations 894
24.2 dynamic equivalence and applications 894
24.2.1 application:generating mazes 895
24.2.2 application:minimum spanning trees 898
24.2.3 application:the nearest common ancestor problem 901
24.3 the quick-find algorithm 904
24.4 the quick-union algorithm 905
24.4.1 smart union algorithms 907
24.4.2 path compression 909
24.5 java implementation 910
24.6 worst case for union-by-rank and path compression 913
24.6.1 analysis of the union/find algorithm 914
summary 921
key concepts 921
common errors 922
on the internet 922
exercises 923
references 925
appendix A operators 927
appendix B graphical user interfaces 929
B.1 the abstract window toolkit and swing 930
B.2 basic objects in swing 931
B.2.1 Component 932
B.2.2 Container 933
B.2.3 top-level containers 933
B.2.4 JPanel 934
B.2.5 important i/o components 936
B.3 basic principles 940
B.3.1 layout managers 941
B.3.2 graphics 945
B.3.3 events 947
B.3.4 event handling:adapters and anonymous inner classes 949
B.3.5 summary:putting the pieces together 951
B.3.6 is this everything i need to know about swing? 952
summary 953
key concepts 953
common errors 955
on the internet 956
exercises 956
references 957
appendix C bitwise operators 959
index 963