About the Book
Data Structures and Problem Solving
Using Java, Second Edition provides a practical introduction to data structures
and algorithms from the viewpoint of abstract thinking and problem solving,
as well as the use of Java.
This text has a clear separation of
the interface and implementation to promote abstract thinking. Java allows
the programmer to write the interface and implementation separately, to
place them in separate files and compile separately, and to hide the implementation
details. This book goes a step further: the interface and implementation
are discussed in separate parts of the book. Part I (Tour of Java), Part
II (Algorithms and Building Blocks), and Part III (Applications) lay the
groundwork by discussing basic concepts and tools and providing some practical
examples, but implementation of data structures is not shown until Part
IV (Implementations). Class interfaces are written and used before the
implementation is known, forcing the reader to think about the functionality
and potential efficiency of the various data structures (e.g., hash tables
are written well before the hash table is implemented).
Features
-
Complete chapter covering Design Patterns
(Chapter 5).
-
Significantly revised material on Inheritance,
with a Person hierarchy, a simplified Shape example, a discussion of the
Object class, and inheritance details (single dispatch).
-
Code in Part II is completely rewritten with
the Collections API in mind, illustrating both generic interfaces and Collections
interfaces.
-
Code in Part III rewritten to use the Java
1.2 Collections.
-
Generic data structures are rewritten to be
made simpler, such as:
-
linked list classes are rewritten to move
code out of the iterator
-
search tree and hash table classes are rewritten
to avoid WasFound
-
priority queue is rewritten to avoid Toss
-
disjoint sets class has error checking
-
An optional, simplified Collections implementation
is illustrated at the end of each chapter in Part IV
-
Takes a unique approach by separating the
interface of a data structure (Part 2) from their implementations (Part
4), to motivate abstract thinking and problem solving. Students use the
data structures in Part 3 (Applications).
-
Provides an introduction to Java in Part I
for readers without previous experience using Java.
Related
Books
Data Structures - Programming
Courses (Data Structures)
Table of Contents
I. TOUR OF JAVA.
1. Primitive Java.
The General Environment.
The First Program.
Primitive Types.
Basic Operators.
Conditional Statements.
Methods.
2. Reference Types.
What Is a Reference.
Basics of Objects and References.
Strings.
Arrays.
Exception Handling.
Input and Output.
3. Objects and Classes.
What Is Object-oriented Programming?
A Simple Example.
Javadoc.
Basic Methods.
Additional Constructs.
Packages.
A Design Pattern: Composite (Pair).
4. Inheritance.
What Is Inheritance?
Designing Hierarchies.
Multiple Inheritance.
The Interface.
Fundamental Inheritance in Java.
Implementing Generic Components.
The Functor (Function Objects).
Dynamic Binding Details.
II. ALGORITHMS AND BUILDING BLOCKS.
5. Algorithm Analysis.
What Is Algorithm Analysis?
Examples of Algorithm Running Times.
The Maximum Contiguous Subsequence
Sum Problem.
General Big-Oh Rules.
The Logarithm.
Static Searching Problem.
Checking an Algorithm Analysis.
Limitations of Big-Oh Analysis.
6. The Collections API.
Introduction.
The Iterator Pattern.
Collections API: Containers and Iterators.
Generic Algorithms.
The List Interface.
Stacks and Queues.
Sets.
Maps.
Priority Queues.
7. Recursion.
What Is Recursion?
Background: Proofs by Mathematical
Induction.
Basic Recursion.
Numerical Applications.
Divide-and-Conquer Algorithms.
Dynamic Programming.
Backtracking Algorithms.
8. Sorting Algorithms.
Why Is Sorting Important?
Preliminaries.
Analysis of the Insertion Sort and
Other Simple Sorts.
Shellsort.
Mergesort.
Quicksort.
Quickselect.
A Lower Bound for Sorting.
9. Randomization.
Why Do We Need Random Numbers?
Random-number Generators.
Nonuniform Random Numbers.
Generating a Random Permutation.
Randomized Algorithms.
Randomized Primality Testing.
III. APPLICATIONS.
10. Fun and Games.
Word Search Puzzles.
The Game of Tic-Tac-Toe.
11. Stacks and Compilers.
Balanced-Symbol Checker.
A Simple Calculator.
12. Utilities.
File Compression.
A Cross-reference Generator.
13. Simulation.
The Josephus Problem.
Event-driven Simulation.
14. Graphs and Paths.
Definitions.
Unweighted Shortest-path Problem.
Positive-weighted, Shortest-path Problem.
Negative-weighted, Shortest-path Problem.
Path Problems in Acyclic Graphs.
IV. IMPLEMENTATIONS.
15. Inner Classes and ArrayList
Implementation.
Iterators and Nested Classes.
Iterators and Inner Classes.
The AbstractCollection Class.
Implementation of ArrayList with an
Iterator.
16. Stacks and Queues.
Dynamic Array Implementations.
Linked-list Implementations.
Comparison of the Two Methods.
The java.util.Stack Class.
Double-Ended Queues.
17. Linked Lists.
Basic Ideas.
Java Implementation.
Doubly Linked Lists and Circular Linked
Lists.
Sorted Linked Lists.
Implementing the Collections API LinkedList
Class.
18. Trees.
General Trees.
Binary Trees.
Recursion and Trees.
Tree Traversal: Iterator Classes.
19. Binary Search Trees.
Basic Ideas.
Order Statistics.
Analysis of Binary Search Tree Operations.
AVL Trees.
Red-Black Trees.
AA-Trees.
Implementing the Collections API TreeSet
and TreeMap Classes.
B-Trees.
20. Hash Tables.
Basic Ideas.
Hash Function.
Linear Probing.
Quadratic Probing.
Separate Chaining Hashing.
Hash Tables Versus Binary Search Trees.
Hashing Applications.
21. A Priority Queue: The Binary
Heap.
Basic Ideas.
Implementation of the Basic Operations.
The buildHeap Operation: Linear-Time
Heap Construction.
Advanced Operations: decreaseKey and
merge.
Internal Sorting: Heapsort.
External Sorting.
V. ADVANCED DATA STRUCTURES.
22. Splay Trees.
Self-Adjustment and Amortized Analysis.
The Basic Bottom-Up Splay Tree.
Basic Splay Tree Operations.
Analysis of Bottom-Up Splaying.
Top-Down Splay Trees.
Implementation of Top-Down Splay Trees.
Comparison of the Splay Tree with
Other Search Trees.
23. Merging Priority Queues.
The Skew Heap.
The Pairing Heap.
24. The Disjoint Set Class.
Equivalence Relations.
Dynamic Equivalence and Two Applications.
The Quick-Find Algorithm.
The Quick-Union Algorithm.
Java Implementation.
Worst Case for Union-by-Rank and Path
Compression.
APPENDICES.
A. Operators.
B. Graphical User Interfaces. |
