| Chapter 1 | Review of Java | 1 |
| 1.1 | Object-Oriented Programming | 1 |
| 1.2 | The Java Programming Language | 1 |
| 1.3 | Variables and Objects | 1 |
| 1.4 | Primitive Types | 3 |
| 1.5 | Flow Control | 4 |
| 1.6 | Classes | 7 |
| 1.7 | Modifiers | 9 |
| 1.8 | The String Class | 10 |
| 1.9 | The Math Class | 13 |
| Chapter 2 | Review of Arrays | 23 |
| 2.1 | Properties of Arrays | 23 |
| 2.2 | Duplicating an Array | 24 |
| 2.3 | The Arrays Class | 25 |
| 2.4 | The Sequential Search Algorithm | 28 |
| 2.5 | The Binary Search Algorithm | 31 |
| 2.6 | The Vector Class | 33 |
| Chapter 3 | Advanced Java | 53 |
| 3.1 | Inheritance | 53 |
| 3.2 | Polymorphism | 54 |
| 3.3 | Type Conversion | 55 |
| 3.4 | The Object Class | 58 |
| 3.5 | Abstract Classes | 60 |
| 3.6 | Interfaces | 63 |
| 3.7 | Packages | 66 |
| 3.8 | Exception Handling | 67 |
| Chapter 4 | Recursion | 73 |
| 4.1 | The Basis and Recursive Parts of Recursion | 74 |
| 4.2 | Tracing a Recursive Call | 75 |
| 4.3 | The Recursive Binary Search Algorithm | 75 |
| 4.4 | Binomial Coefficients | 78 |
| 4.5 | The Euclidean Algorithm | 79 |
| 4.6 | Inductive Proof of Correctness | 79 |
| 4.7 | Complexity Analysis of Recursive Algorithms | 80 |
| 4.8 | Dynamic Programming | 81 |
| 4.9 | The Towers of Hanoi | 82 |
| 4.10 | Mutual Recursion | 83 |
| Chapter 5 | Collections | 94 |
| 5.1 | The Java Collections Framework | 94 |
| 5.2 | The Collection Interface | 95 |
| 5.3 | The AbstractCollection Class | 95 |
| 5.4 | A Bag Class | 96 |
| 5.5 | The Iterator Interface | 103 |
| Chapter 6 | Stacks | 109 |
| 6.1 | The Java Stack Class | 109 |
| 6.2 | Applications of Stacks | 112 |
| 6.3 | Removing Recursion | 115 |
| Chapter 7 | Queues | 123 |
| 7.1 | A Framework for Queues | 123 |
| 7.2 | A Contiguous Implementation | 126 |
| 7.3 | A Linked Implementation | 129 |
| 7.4 | Simulation with Queues | 130 |
| Chapter 8 | Lists | 144 |
| 8.1 | The java.util.List Interface | 144 |
| 8.2 | Implementations of the java.util.List Interface | 146 |
| 8.3 | The AbstractList and AbstractSequentialList Classes | 146 |
| 8.4 | List Iterators | 148 |
| 8.5 | The ArrayList Class | 149 |
| 8.6 | The LinkedList Class | 150 |
| 8.7 | Independent List Iterators | 160 |
| Chapter 9 | Trees | 166 |
| 9.1 | Tree Definitions | 167 |
| 9.2 | Decision Trees and Transition Diagrams | 169 |
| 9.3 | Ordered Trees | 172 |
| 9.4 | Tree Traversal Algorithms for Ordered Trees | 172 |
| Chapter 10 | Binary Trees | 181 |
| 10.1 | Definitions | 181 |
| 10.2 | Counting Binary Trees | 182 |
| 10.3 | Full Binary Trees | 183 |
| 10.4 | Identity, Equality, and Isomorphism | 184 |
| 10.5 | Complete Binary Trees | 186 |
| 10.6 | Binary Tree Traversal Algorithms | 187 |
| 10.7 | Expression Trees | 190 |
| 10.8 | A BinaryTree Class | 192 |
| 10.9 | Implementations of the Traversal Algorithms | 196 |
| 10.10 | Forests | 199 |
| Chapter 11 | Search Trees | 210 |
| 11.1 | Multiway Search Trees | 210 |
| 11.2 | B-Trees | 212 |
| 11.3 | Binary Search Trees | 214 |
| 11.4 | Performance Characteristics of Binary Search Trees | 216 |
| 11.5 | AVL Trees | 216 |
| 11.6 | An AVLTree Class | 217 |
| Chapter 12 | Heaps and Priority Queues | 225 |
| 12.1 | Heaps | 225 |
| 12.2 | The Natural Mapping | 225 |
| 12.3 | Insertion into a Heap | 226 |
| 12.4 | Removal from a Heap | 227 |
| 12.5 | A PriorityQueue Class | 228 |
| 12.6 | The Java Comparator Interface | 229 |
| 12.7 | A Direct Implementation | 231 |
| Chapter 13 | Sorting | 243 |
| 13.1 | The Java Arrays.sort() Method | 243 |
| 13.2 | The Bubble Sort | 244 |
| 13.3 | The Selection Sort | 245 |
| 13.4 | The Insertion Sort | 246 |
| 13.5 | The Shell Sort | 247 |
| 13.6 | The Merge Sort | 249 |
| 13.7 | The Quick Sort | 252 |
| 13.8 | The Heap Sort | 254 |
| 13.9 | The Speed Limit for Comparison Sorts | 258 |
| 13.10 | The Radix Sort | 259 |
| 13.11 | The Bucket Sort | 261 |
| Chapter 14 | Tables | 275 |
| 14.1 | The Java Map Interface | 275 |
| 14.2 | The HashMap Class | 276 |
| 14.3 | Java Hash Codes | 277 |
| 14.4 | Hash Tables | 278 |
| 14.5 | Hash Table Performance | 280 |
| 14.6 | Collision Resolution Algorithms | 280 |
| 14.7 | Separate Chaining | 283 |
| 14.8 | Applications | 284 |
| 14.9 | The TreeMap Class | 286 |
| Chapter 15 | Sets | 293 |
| 15.1 | Mathematical Sets | 293 |
| 15.2 | The Java Set Interface | 294 |
| 15.3 | The Java AbstractSet Class | 294 |
| 15.4 | The Java HashSet Class | 295 |
| 15.5 | The Java TreeSet Class | 297 |
| Chapter 16 | Graphs | 301 |
| 16.1 | Simple Graphs | 301 |
| 16.2 | Graph Terminology | 301 |
| 16.3 | Paths and Cycles | 302 |
| 16.4 | Isomorphic Graphs | 304 |
| 16.5 | The Adjacency Matrix for a Graph | 306 |
| 16.6 | The Incidence Matrix for a Graph | 306 |
| 16.7 | The Adjacency List for a Graph | 307 |
| 16.8 | Digraphs | 308 |
| 16.9 | Paths in a Digraph | 310 |
| 16.10 | Weighted Digraphs and Graphs | 310 |
| 16.11 | Euler and Hamiltonian Paths and Cycles | 311 |
| 16.12 | Dijkstra's Algorithm | 312 |
| 16.13 | Graph Traversal Algorithms | 316 |
| Appendix A | Essential Mathematics | 333 |
| A.1 | The Floor and Ceiling Function | 333 |
| A.2 | Logarithms | 333 |
| A.3 | Complexity Classes | 335 |
| A.4 | The First Principle of Mathematical Induction | 336 |
| A.5 | The Second Principle of Mathematical Induction | 337 |
| A.6 | Geometric Series | 338 |
| A.7 | Summation Formulas | 339 |
| A.8 | Harmonic Numbers | 339 |
| A.9 | Stirling's Formula | 341 |
| A.10 | The Fibonacci Numbers | 342 |
| A.11 | The Golden Mean | 342 |
| A.12 | The Euclidean Algorithm | 343 |
| A.13 | The Catalan Numbers | 344 |
| Appendix B | From C++ to Java | 353 |
| Appendix C | Java Development Environments | 356 |
| C.1 | The Windows Command Prompt | 356 |
| C.2 | Visual Cafe from Webgain | 356 |
| Appendix D | References | 361 |
| Index | 365 |
Format: Textbook Paperback, 1st ed., 3
