Data Structures and Algorithms in Java

by Drake, Peter

• ISBN13: 9780131469143
• ISBN10: 0131469142
• Edition: 1st
• Format: Paperback
• Copyright: 2005-12-19
• Publisher: Pearson

Summary

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. 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.

Author Biography

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.

Table of Contents

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

Object-Oriented Programming

Encapsulation

Software Development

Classes and Objects

Using Objects

Polymorphism

Reference Types

Arrays

Interfaces

Overloading

Inheritance

Extending a Class

The Object Class

Packages and Access Levels

Linear Structures

Stacks and Queues

The Stack Interface

The Call Stack

Exceptions

The Queue Interface

Array-Based Structures

Shrinking and Stretching Arrays

Implementing Stacks and Queues

The List Interface

Iterators

The Java Collections Framework: A First Look

Linked Structures

List Nodes

Stacks and Queues

The LinkedList Class

The Java Collections Framework Revisited

Algorithms

Analysis of Algorithms

Timing

Asymptotic Notation

Counting Steps

Best, Worst, and Average Case

Amortized Analysis

Searching and Sorting

Linear Search

Binary Search

Insertion Sort

The Comparable Interface

Sorting Linked Lists

Recursion

Thinking Recursively

Analyzing Recursive Algorithms

Merge Sort

Quicksort

Avoiding Recursion

Trees and Sets

Trees

Binary Trees

Tree Traversal

General Trees

Sets

The Set Interface

Ordered Lists

Binary Search Trees

Hash Tables

The Java Collections Framework Again

Advanced Topics

Advanced Linear Structures

Bit Vectors

Sparse Arrays

Contiguous Representation of Multidimensional Arrays

Advanced Searching and Sorting

Strings

Strings and StringBuilders

String Matching

Advanced Trees

Heaps

Disjoint Set Clusters

Digital Search Trees

Red-Black Trees

Graphs

Terminology

Representation

Graph Traversal

Topological Sorting

Shortest Paths

Minimum Spanning Trees

Memory Management

Explicit Memory Management

Automatic Memory Management

Out to the Disk

Interacting With Files

Compression

External Sorting

B-Trees

Review of Java Unified Modeling Language Summation Formulae

Further Reading

Table of Contents provided by Publisher. All Rights Reserved.