Data structures & problem solving using Java

Cover......Page 1
Contents......Page 20
Part one: Tour of Java......Page 38
 Chapter 1 primitive java......Page 40
  1.1 The general environment......Page 41
  1.2 The first program......Page 42
  1.3 Primitive types......Page 43
  1.4 Basic operators......Page 45
  1.5 Conditional statements......Page 48
  1.6 Methods......Page 55
  Key concepts......Page 57
  Common errors......Page 59
  Exercises......Page 60
  References......Page 62
  2.1 What is a reference?......Page 64
  2.2 Basics of objects and references......Page 67
  2.3 Strings......Page 72
  2.4 Arrays......Page 74
  2.5 Exception handling......Page 84
  2.6 Input and output......Page 88
  Summary......Page 96
  Key concepts......Page 97
  Common errors......Page 98
  Exercises......Page 99
  References......Page 105
  3.1 What is object-oriented programming?......Page 106
  3.2 A simple example......Page 108
  3.3 Javadoc......Page 110
  3.4 Basic methods......Page 113
  3.5 Example: using java.math.BigInteger......Page 115
  3.6 Additional constructs......Page 116
  3.7 Example: implementing a BigRational class......Page 123
  3.8 Packages......Page 127
  3.9 A design pattern: composite (pair)......Page 132
  Summary......Page 133
  Key concepts......Page 134
  On the internet......Page 137
  Exercises......Page 138
  References......Page 144
 Chapter 4 inheritance......Page 146
  4.1 What is inheritance?......Page 147
  4.2 Designing hierarchies......Page 162
  4.3 Multiple inheritance......Page 168
  4.4 The interface......Page 171
  4.5 Fundamental inheritance in java......Page 173
  4.6 Implementing generic components using inheritance......Page 179
  4.7 Implementing generic components using java 5 generics......Page 187
  4.8 The functor (function objects)......Page 194
  4.9 Dynamic dispatch details......Page 201
  Key concepts......Page 205
  On the internet......Page 208
  Exercises......Page 210
  References......Page 220
Part two: Algorithms and Building Blocks......Page 222
 Chapter 5 algorithm analysis......Page 224
  5.1 What is algorithm analysis?......Page 225
  5.2 Examples of algorithm running times......Page 229
  5.3 The maximum contiguous subsequence sum problem......Page 230
  5.4 General big-oh rules......Page 238
  5.5 The logarithm......Page 242
  5.6 Static searching problem......Page 244
  5.7 Checking an algorithm analysis......Page 249
  5.8 Limitations of big-oh analysis......Page 250
  Key concepts......Page 251
  Common errors......Page 252
  Exercises......Page 253
  References......Page 264
 Chapter 6 the collections api......Page 266
  6.1 Introduction......Page 267
  6.2 The iterator pattern......Page 268
  6.3 Collections api: containers and iterators......Page 273
  6.4 Generic algorithms......Page 279
  6.5 The List interface......Page 285
  6.6 Stacks and queues......Page 295
  6.7 Sets......Page 298
  6.8 Maps......Page 305
  6.9 Priority queues......Page 311
  6.10 Views in the collections api......Page 314
  Summary......Page 315
  Key concepts......Page 316
  Common errors......Page 317
  Exercises......Page 318
  References......Page 329
 Chapter 7 recursion......Page 330
  7.1 What is recursion?......Page 331
  7.2 Background: proofs by mathematical induction......Page 332
  7.3 Basic recursion......Page 334
  7.4 Numerical applications......Page 348
  7.5 Divide-and-conquer algorithms......Page 356
  7.6 Dynamic programming......Page 366
  7.7 Backtracking......Page 370
  Summary......Page 373
  Key concepts......Page 375
  On the internet......Page 376
  Exercises......Page 377
  References......Page 385
 Chapter 8 sorting algorithms......Page 388
  8.1 Why is sorting important?......Page 389
  8.3 Analysis of the insertion sort and other simple sorts......Page 390
  8.4 Shellsort......Page 394
  8.5 Mergesort......Page 398
  8.6 Quicksort......Page 401
  8.7 Quickselect......Page 417
  8.8 A lower bound for sorting......Page 418
  Summary......Page 420
  Key concepts......Page 421
  Exercises......Page 422
  References......Page 428
  9.1 Why do we need random numbers?......Page 430
  9.2 Random number generators......Page 431
  9.3 Nonuniform random numbers......Page 439
  9.4 Generating a random permutation......Page 441
  9.5 Randomized algorithms......Page 443
  9.6 Randomized primality testing......Page 446
  Key concepts......Page 449
  Common errors......Page 450
  Exercises......Page 451
  References......Page 454
Part three: Applications......Page 456
  10.1 Word search puzzles......Page 458
  10.2 The game of tic-tac-toe......Page 464
  On the internet......Page 475
  Exercises......Page 476
  References......Page 478
  11.1 Balanced-symbol checker......Page 480
  11.2 A simple calculator......Page 491
  Summary......Page 506
  Common errors......Page 507
  Exercises......Page 508
  References......Page 509
 Chapter 12 utilities......Page 510
  12.1 File compression......Page 511
  12.2 A cross-reference generator......Page 532
  Summary......Page 536
  Exercises......Page 537
  References......Page 543
  13.1 The josephus problem......Page 544
  13.2 Event-driven simulation......Page 550
  Key concepts......Page 559
  Exercises......Page 560
 Chapter 14 graphs and paths......Page 564
  14.1 Definitions......Page 565
  14.2 Unweighted shortest-path problem......Page 576
  14.3 Positive-weighted, shortest-path problem......Page 582
  14.4 Negative-weighted, shortest-path problem......Page 589
  14.5 Path problems in acyclic graphs......Page 592
  Summary......Page 599
  Key concepts......Page 600
  Common errors......Page 601
  Exercises......Page 602
  References......Page 606
Part four: Implementations......Page 608
 Chapter 15 inner classes and implementation of ArrayList......Page 610
  15.1 Iterators and nested classes......Page 611
  15.2 Iterators and inner classes......Page 613
  15.3 The AbstractCollection class......Page 617
  15.4 StringBuilder......Page 621
  15.5 Implementation of ArrayList with an iterator......Page 622
  Summary......Page 627
  Exercises......Page 628
  16.1 Dynamic array implementations......Page 632
  16.2 Linked list implementations......Page 642
  16.4 The java.util.Stack class......Page 650
  Common errors......Page 652
  Exercises......Page 653
  17.1 Basic ideas......Page 656
  17.2 Java implementation......Page 661
  17.3 Doubly linked lists and circularly linked lists......Page 667
  17.4 Sorted linked lists......Page 670
  17.5 Implementing the collections api LinkedList class......Page 672
  Key concepts......Page 683
  Exercises......Page 684
  18.1 General trees......Page 688
  18.2 Binary trees......Page 695
  18.3 Recursion and trees......Page 702
  18.4 Tree traversal: iterator classes......Page 704
  Summary......Page 716
  Key concepts......Page 717
  Common errors......Page 718
  Exercises......Page 719
  19.1 Basic ideas......Page 724
  19.2 Order statistics......Page 734
  19.3 Analysis of binary search tree operations......Page 739
  19.4 Avl trees......Page 743
  19.5 Red–black trees......Page 752
  19.6 Aa-trees......Page 765
  19.7 Implementing the collections api TreeSet and TreeMap classes......Page 775
  19.8 B-trees......Page 793
  Summary......Page 799
  Key concepts......Page 800
  On the internet......Page 801
  Exercises......Page 802
  References......Page 806
 Chapter 20 hash tables......Page 810
  20.1 Basic ideas......Page 811
  20.2 Hash function......Page 812
  20.3 Linear probing......Page 816
  20.4 Quadratic probing......Page 821
  20.5 Separate chaining hashing......Page 834
  20.6 Hash tables versus binary search trees......Page 835
  Summary......Page 837
  Key concepts......Page 838
  Exercises......Page 839
  References......Page 842
 Chapter 21 a priority queue: the binary heap......Page 844
  21.1 Basic ideas......Page 845
  21.2 Implementation of the basic operations......Page 851
  21.3 The buildHeap operation: linear-time heap construction......Page 855
  21.5 Internal sorting: heapsort......Page 860
  21.6 External sorting......Page 863
  Summary......Page 870
  Common errors......Page 871
  Exercises......Page 872
  References......Page 876
Part five: Advanced Data Structures......Page 878
 Chapter 22 splay trees......Page 880
  22.1 Self-adjustment and amortized analysis......Page 881
  22.2 The basic bottom-up splay tree......Page 884
  22.3 Basic splay tree operations......Page 887
  22.4 Analysis of bottom-up splaying......Page 888
  22.5 Top-down splay trees......Page 894
  22.6 Implementation of top-down splay trees......Page 897
  22.7 Comparison of the splay tree with other search trees......Page 902
  Key concepts......Page 903
  Exercises......Page 904
  References......Page 905
  23.1 The skew heap......Page 908
  23.2 The pairing heap......Page 913
  Common errors......Page 925
  Exercises......Page 926
  References......Page 927
 Chapter 24 the disjoint set class......Page 930
  24.2 Dynamic equivalence and applications......Page 931
  24.3 The quick-find algorithm......Page 941
  24.4 The quick-union algorithm......Page 942
  24.5 Java implementation......Page 947
  24.6 Worst case for union-by-rank and path compression......Page 950
  Key concepts......Page 958
  On the internet......Page 959
  Exercises......Page 960
  References......Page 962
Appendix A: operators......Page 964
Appendix B: graphical user interfaces......Page 966
 B.1 The abstract window toolkit and swing......Page 967
 B.2 Basic objects in swing......Page 968
  B.2.1 Component......Page 969
  B.2.3 Top-level containers......Page 970
  B.2.4 JPanel......Page 971
  B.2.5 Important i/o components......Page 973
 B.3 Basic principles......Page 977
  B.3.1 Layout managers......Page 978
  B.3.2 Graphics......Page 982
  B.3.3 Events......Page 984
  B.3.4 Event handling: adapters and anonymous inner classes......Page 986
  B.3.5 Summary: putting the pieces together......Page 988
  B.3.6 Is this everything i need to know about swing?......Page 989
 Key concepts......Page 990
 Common errors......Page 992
 Exercises......Page 993
 References......Page 994
Appendix C: bitwise operators......Page 996
 A......Page 1000
 B......Page 1002
 C......Page 1003
 D......Page 1006
 F......Page 1007
 G......Page 1008
 H......Page 1009
 I......Page 1010
 J......Page 1011
 L......Page 1012
 M......Page 1013
 O......Page 1014
 P......Page 1015
 Q......Page 1016
 R......Page 1017
 S......Page 1018
 T......Page 1020
 V......Page 1021
 Z......Page 1022