Data Structures and Algorithms in Java

ISBN: 0131469142
EAN: 2147483647

Year: 2004
Pages: 216

Authors: Peter Drake

BUY ON AMAZON

Part I: Object-Oriented Programming

Encapsulation

• Encapsulation
• Software Development
• Classes and Objects
• Using Objects
• Summary
• Vocabulary
• Problems
• Projects

Polymorphism

• Polymorphism
• Reference Types
• Arrays
• Interfaces
• Overloading
• Summary
• Vocabulary
• Problems
• Projects

Inheritance

• Inheritance
• Extending a Class
• The Object Class
• Packages and Access Levels
• Summary
• Vocabulary
• Problems
• Projects

Part II: Linear Structures

Stacks and Queues

• Stacks and Queues
• The Stack Interface
• The Call Stack
• Exceptions
• The Queue Interface
• Summary
• Vocabulary
• Problems
• Projects

Array-Based Structures

• Array-Based Structures
• Shrinking and Stretching Arrays
• Implementing Stacks and Queues
• The List Interface
• Iterators
• The Java Collections Framework: A First Look
• Summary
• Vocabulary
• Problems
• Projects

Linked Structures

• Linked Structures
• List Nodes
• Stacks and Queues
• The LinkedList Class
• The Java Collections Framework Revisited
• Summary
• Vocabulary
• Problems
• Projects

Part III: Algorithms

Analysis of Algorithms

• Analysis of Algorithms
• Timing
• Asymptotic Notation
• Counting Steps
• Best, Worst, and Average Case
• Amortized Analysis
• Summary
• Vocabulary
• Problems
• Projects

Searching and Sorting

• Searching and Sorting
• Linear Search
• Binary Search
• Insertion Sort
• The Comparable Interface
• Sorting Linked Lists
• Summary
• Vocabulary
• Problems
• Projects

Recursion

• Recursion
• Thinking Recursively
• Analyzing Recursive Algorithms
• Merge Sort
• Quicksort
• Avoiding Recursion
• Summary
• Vocabulary
• Problems
• Projects

Part IV: Trees and Sets

Trees

• Trees
• Binary Trees
• Tree Traversal
• General Trees
• Summary
• Vocabulary
• Problems
• Projects

Sets

• Sets
• The Set Interface
• Ordered Lists
• Binary Search Trees
• Hash Tables
• The Java Collections Framework Again
• Summary
• Vocabulary
• Problems
• Projects

Part V: Advanced Topics

Advanced Linear Structures

• Advanced Linear Structures
• Bit Vectors
• Sparse Arrays
• Contiguous Representation of Multidimensional Arrays
• Advanced Searching and Sorting
• Summary
• Vocabulary
• Problems
• Projects

Strings

• Strings
• Strings and StringBuilders
• String Matching
• Summary
• Vocabulary
• Problems
• Projects

Advanced Trees

• Advanced Trees
• Heaps
• Disjoint Set Clusters
• Digital Search Trees
• Red-Black Trees
• Summary
• Vocabulary
• Problems
• Projects

Graphs

• Graphs
• Terminology
• Representation
• Graph Traversal
• Topological Sorting
• Shortest Paths
• Minimum Spanning Trees
• Summary
• Vocabulary
• Problems
• Projects

Memory Management

• Memory Management
• Explicit Memory Management
• Summary
• Vocabulary
• Problems
• Projects

Out to the Disk

• Out to the Disk
• Interacting with Files
• Compression
• External Sorting
• B-Trees
• Summary
• Vocabulary
• Problems
• Projects

Part VI: Appendices

A. Review of Java

• A. Review of Java
• A.1. The First Program
• A.2. Variables and Types
• A.3. Loops
• A.4. Interacting with the User
• A.5. Branching
• A.6. Methods and Breaking Out
• A.7. Constants
• A.8. Operators
• A.9. Debugging
• A.10. Coding Conventions

B. Unified Modeling Language

• B. Unified Modeling Language
• B.1. Class Diagrams
• B.2. Instance Diagrams

C. Summation Formulae

• C. Summation Formulae
• C.1. Sum Notation
• C.2. Sum of Constants
• C.3. Sum of First n Integers
• C.4. Sums of Halves and Doubles
• C.5. Upper Limit on Sum of a Function
• C.6. Constant Factors

D. Further Reading

• D.1. Data Structures and Algorithms
• D.2. Java
• D.3. Games

Index