Data Structures and Algorithms in Java


   
book cover
  
• Table of Contents
• Index
Data Structures and Algorithms in Java
By Peter Drake
Publisher: Prentice Hall
Pub Date: December 19, 2005
Print ISBN-10: 0-13-146914-2
Print ISBN-13: 978-0-13-146914-3
eText ISBN-10: 0-13-174690-1
eText ISBN-13: 978-0-13-174690-9
Pages: 592
 


An abundance of unique, interesting examples, use of the Unified Modeling Language throughout, and the newest Java 1.5 features characterize this text. Drake provides a concise and engaging introduction to Java and object-oriented programming, assuming  familiarity with the basic control structures of Java or C and only a pre-calculus level of mathematics.



   
book cover
  
• Table of Contents
• Index
Data Structures and Algorithms in Java
By Peter Drake
Publisher: Prentice Hall
Pub Date: December 19, 2005
Print ISBN-10: 0-13-146914-2
Print ISBN-13: 978-0-13-146914-3
eText ISBN-10: 0-13-174690-1
eText ISBN-13: 978-0-13-174690-9
Pages: 592
 


   Copyright
   Prefacexi
      Intended Audiencexi
    Part I:  Object-Oriented Programming1
      Chapter 1.  Encapsulation3
      Section 1.1.  Software Development3
      Section 1.2.  Classes and Objects9
      Section 1.3.  Using Objects18
      Summary32
      Vocabulary32
      Problems34
      Projects35
      Chapter 2.  Polymorphism37
      Section 2.1.  Reference Types37
      Section 2.2.  Arrays44
      Section 2.3.  Interfaces55
      Section 2.4.  Overloading59
      Summary61
      Vocabulary61
      Problems62
      Projects62
      Chapter 3.  Inheritance67
      Section 3.1.  Extending a Class67
      Section 3.2.  The Object Class77
      Section 3.3.  Packages and Access Levels79
      Summary82
      Vocabulary83
      Problems84
      Projects84
    Part II:  Linear Structures85
      Chapter 4.  Stacks and Queues87
      Section 4.1.  The Stack Interface87
      Section 4.2.  The Call Stack97
      Section 4.3.  Exceptions100
      Section 4.4.  The Queue Interface108
      Summary114
      Vocabulary114
      Problems115
      Projects116
      Chapter 5.  Array-Based Structures119
      Section 5.1.  Shrinking and Stretching Arrays119
      Section 5.2.  Implementing Stacks and Queues127
      Section 5.3.  The List Interface133
      Section 5.4.  Iterators139
      Section 5.5.  The Java Collections Framework: A First Look151
      Summary153
      Vocabulary154
      Problems154
      Projects155
      Chapter 6.  Linked Structures157
      Section 6.1.  List Nodes157
      Section 6.2.  Stacks and Queues161
      Section 6.3.  The LinkedList Class168
      Section 6.4.  The Java Collections Framework Revisited176
      Summary178
      Vocabulary178
      Problems179
      Projects179
    Part III:  Algorithms181
      Chapter 7.  Analysis of Algorithms183
      Section 7.1.  Timing183
      Section 7.2.  Asymptotic Notation186
      Section 7.3.  Counting Steps192
      Section 7.4.  Best, Worst, and Average Case197
      Section 7.5.  Amortized Analysis199
      Summary202
      Vocabulary202
      Problems203
      Projects203
      Chapter 8.  Searching and Sorting205
      Section 8.1.  Linear Search206
      Section 8.2.  Binary Search207
      Section 8.3.  Insertion Sort211
      Section 8.4.  The Comparable Interface214
      Section 8.5.  Sorting Linked Lists218
      Summary219
      Vocabulary221
      Problems221
      Projects221
      Chapter 9.  Recursion223
      Section 9.1.  Thinking Recursively223
      Section 9.2.  Analyzing Recursive Algorithms231
      Section 9.3.  Merge Sort235
      Section 9.4.  Quicksort239
      Section 9.5.  Avoiding Recursion244
      Summary248
      Vocabulary249
      Problems250
      Projects251
    Part IV:  Trees and Sets253
      Chapter 10.  Trees255
      Section 10.1.  Binary Trees255
      Section 10.2.  Tree Traversal265
      Section 10.3.  General Trees270
      Summary280
      Vocabulary280
      Problems281
      Projects282
      Chapter 11.  Sets283
      Section 11.1.  The Set Interface283
      Section 11.2.  Ordered Lists291
      Section 11.3.  Binary Search Trees296
      Section 11.4.  Hash Tables305
      Section 11.5.  The Java Collections Framework Again316
      Summary318
      Vocabulary319
      Problems320
      Projects321
    Part V:  Advanced Topics323
      Chapter 12.  Advanced Linear Structures325
      Section 12.1.  Bit Vectors325
      Section 12.2.  Sparse Arrays335
      Section 12.3.  Contiguous Representation of Multidimensional Arrays337
      Section 12.4.  Advanced Searching and Sorting343
      Summary347
      Vocabulary348
      Problems348
      Projects349
      Chapter 13.  Strings351
      Section 13.1.  Strings and StringBuilders351
      Section 13.2.  String Matching355
      Summary366
      Vocabulary367
      Problems367
      Projects368
      Chapter 14.  Advanced Trees369
      Section 14.1.  Heaps369
      Section 14.2.  Disjoint Set Clusters377
      Section 14.3.  Digital Search Trees383
      Section 14.4.  Red-Black Trees389
      Summary404
      Vocabulary405
      Problems406
      Projects406
      Chapter 15.  Graphs407
      Section 15.1.  Terminology408
      Section 15.2.  Representation413
      Section 15.3.  Graph Traversal419
      Section 15.4.  Topological Sorting422
      Section 15.5.  Shortest Paths427
      Section 15.6.  Minimum Spanning Trees432
      Summary437
      Vocabulary437
      Problems439
      Projects439
      Chapter 16.  Memory Management443
      Section 16.1.  Explicit Memory Management443
      Section 16.2.  Automatic Memory Management454
      Summary463
      Vocabulary464
      Problems465
      Projects465
      Chapter 17.  Out to the Disk467
      Section 17.1.  Interacting with Files467
      Section 17.2.  Compression477
      Section 17.3.  External Sorting488
      Section 17.4.  B-Trees494
      Summary514
      Vocabulary514
      Problems515
      Projects515
    Part VI:  Appendices517
      Appendix A.  Review of Java519
      Section A.1.  The First Program519
      Section A.2.  Variables and Types521
      Section A.3.  Loops524
      Section A.4.  Interacting with the User526
      Section A.5.  Branching527
      Section A.6.  Methods and Breaking Out529
      Section A.7.  Constants531
      Section A.8.  Operators533
      Section A.9.  Debugging537
      Section A.10.  Coding Conventions538
      Appendix B.  Unified Modeling Language543
      Section B.1.  Class Diagrams543
      Section B.2.  Instance Diagrams547
      Appendix C.  Summation Formulae551
      Section C.1.  Sum Notation551
      Section C.2.  Sum of Constants552
      Section C.3.  Sum of First n Integers553
      Section C.4.  Sums of Halves and Doubles554
      Section C.5.  Upper Limit on Sum of a Function554
      Section C.6.  Constant Factors555
      Appendix D.  Further Reading557
      Section D.1.  Data Structures and Algorithms557
      Section D.2.  Java557
      Section D.3.  Games558
   Index