Data Structures and Problem Solving using JAVA

Part I: Tour of Java

CHAPTER 1: Primitive Java

The General Environment
The First Program
Primitive Types
Basic Operators
Conditional Statements
Methods
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 2: Reference Types

What Is a Reference?
Basics of Objects and References
Strings
Arrays
Exception Handling
Input and Output
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 3: Objects and Classes

What Is Object-oriented Programming?
A Simple Example
Javadoc
Basic Methods
Additional Constructs
Packages
A Design Pattern: Composite (Pair)
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 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
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

Part II: Algorithms and Building Blocks

CHAPTER 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
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 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
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 7: Recursion

What Is Recursion?
Background: Proofs by Mathematical Induction
Basic Recursion
Numerical Applications
Divide-and-Conquer Algorithms
Dynamic Programming
Backtracking
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 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
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 9: Randomization

Why Do We Need Random Numbers?
Random-number Generators
Nonuniform Random Numbers
Generating a Random Permutation
Randomized Algorithms
Randomized Primality Testing
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

Part III: Applications

CHAPTER 10: Fun and Games

Word Search Puzzles
The Game of Tic-Tac-Toe
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 11: Stacks and Compilers

Balanced-Symbol Checker
A Simple Calculator
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 12: Utilities

File Compression
A Cross-Reference Generator
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 13: Simulation

The Josephus Problem
Event-driven Simulation
Summary
Objects of the Game
Common Errors
On the Internet
Exercises

CHAPTER 14: Graphs and Paths

Definitions
Unweighted Shortest-Path Problem
Positive-Weighted, Shortest-Path Problem
Negative-Weighted, Shortest-Path Problem
Path Problems in Acyclic Graphs
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

Part IV: Implementations

CHAPTER 15: Inner Classes and Implementation of ArrayList

Iterators and Nested Classes
Iterators and Inner Classes
The AbstractCollection Class
Implementation of ArrayList with an Iterator
Summary
Objects of the Game
Common Errors
On the Internet
Exercises

CHAPTER 16: Stacks and Queues

Dynamic Array Implementations
Linked List Implementations
Comparison of the Two Methods
The java.util.Stack Class
Double-Ended Queues
Summary
Objects of the Game
Common Errors
On the Internet
Exercises

CHAPTER 17: Linked Lists

Basic Ideas
Java Implementation
Doubly Linked Lists and Circular Linked Lists
Sorted Linked Lists
Implementing the Collections API LinkedList Class
Summary
Objects of the Game
Common Errors
On the Internet
Exercises

CHAPTER 18: Trees

General Trees
Binary Trees
Recursion and Trees
Tree Traversal: Iterator Classes
Summary
Objects of the Game
Common Errors
On the Internet
Exercises

CHAPTER 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
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 20: Hash Tables

Basic Ideas
Hash Function
Linear Probing
Quadratic Probing
Separate Chaining Hashing
Hash Tables Versus Binary Search Trees
Hashing Applications
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 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
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

Part V: Advanced Data Structures

CHAPTER 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
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 23: Merging Priority Queues

The Skew Heap
The Pairing Heap
Summary
Objects of the Game
Common Errors
On the Internet
Exercises
References

CHAPTER 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
Summary
Objects of the Game
Common Error
On the Internet
Exercises
References

Appendix A: Operators

Appendix B: Graphical User Interfaces

Appendix C: Bitwise Operators