Data Structures and Algorithms in Java

This new book provides a concise and engaging introduction to Java and object-oriented programming with an abundance of original examples, use of Unified Modeling Language throughout, and coverage of the new Java 1.5. Addressing critical concepts up front, the book's five-part structure covers object-oriented programming, linear structures, algorithms, trees and collections, and advanced topics. KEY FEATURES: Data Structures and Algorithms in Java takes a practical approach to real-world programming and introduces readers to the process of crafting programs by working through the development of projects, often providing multiple versions of the code and consideration for alternate designs. The book features the extensive use of games as examples; a gradual development of classes analogous to the Java Collections Framework; complete, working code in the book and online; and strong pedagogy including extended examples in most chapters along with exercises, problems and projects. For readers and professionals with a familiarity with the basic control structures of Java or C and a precalculus level of mathematics who want to expand their knowledge to Java data structures and algorithms. Ideal for a second undergraduate course in computer science.

Peter Drake is Assistant Professor of Computer Science at Lewis &

Clark College in Portland, Oregon. He holds a BA in English from

Willamette University, an MS in Computer Science from Oregon State

University, and a PhD in Computer Science and Cognitive Science from

Indiana University. His research involves writing programs to play

the ancient Chinese game of Go.

Note: Each chapter concludes with a summary, vocabulary, problems, and projects.

Part I: Object-Oriented Programming

1 Encapsulation. Software Development. Classes and Objects. Using Objects.

2 Polymorphism. Reference Types. Arrays. Interfaces. Overloading.

3 Inheritance. Extending a Class. The Object Class. Packages and Access Levels.

Part II: Linear Structures  

4 Stacks and Queues. The Stack Interface. The Call Stack. Exceptions. The Queue Interface.

5 Array-Based Structures. Shrinking and Stretching Arrays. Implementing Stacks and Queues. The List Interface. Iterators. The Java Collections Framework: A First Look.

6 Linked Structures. List Nodes. Stacks and Queues. The LinkedList Class. The Java Collections Framework Revisited  

Part III: Algorithms  

7 Analysis of Algorithms. Timing. Asymptotic Notation. Counting Steps. Best, Worst, and Average Case. Amortized Analysis.

8 Searching and Sorting. Linear Search. Binary Search. Insertion Sort. The Comparable Interface. Sorting Linked Lists.

9 Recursion. Thinking Recursively. Analyzing Recursive Algorithms. Merge Sort. Quicksort. Avoiding Recursion.   

Part IV: Trees and Sets  

10 Trees. Binary Trees. Tree Traversal. General Trees

11 Sets. The Set Interface. Ordered Lists. Binary Search Trees. Hash Tables. The Java Collections Framework Again. 

Part V: Advanced Topics  

12 Advanced Linear Structures. Bit Vectors. Sparse Arrays. Contiguous Representation of Multidimensional Arrays. Advanced Searching and Sorting

13 Strings. Strings and StringBuilders. String Matching.

14 Advanced Trees. Heaps. Disjoint Set Clusters. Digital Search Trees. Red-Black Trees.

15 Graphs. Terminology. Representation. Graph Traversal. Topological Sorting. Shortest Paths. Minimum Spanning Trees.

16 Memory Management. Explicit Memory Management. Automatic Memory Management.

17 Out to the Disk. Interacting With Files. Compression. External Sorting. B-Trees.

Review of Java   

Unified Modeling Language   

Summation Formulae  

Further Reading