Amazon no longer offers textbook rentals. We do!

Data Structures and Problem Solving Using Java

by: Weiss, Mark Allen

Data Structures and Problem Solving Using Java

by: Weiss, Mark Allen

ISBN 13:
9780201748352
ISBN 10:
0201748355
Edition: 2nd
Format: Hardcover
Copyright: 01/01/2002
Publisher: Addison Wesley
Newer Edition

Rent

Sorry, this item is currently unavailable.

Note: Supplemental materials are not guaranteed with Rental or Used book purchases.

Extend or Purchase Your Rental at Any Time

Need to keep your rental past your due date? At any time before your due date you can extend or purchase your rental through your account.

Summary

Data Structures and Problem Solving Using Java&&3/e& provides a practical introduction to data structures from a viewpoint of abstract thinking and problem solving, and incorporates the enhancements of Java 5.0.& It includes coverage of generic programming, and content on the design of generic collection classes. This book is appropriate for readers who are familiar with basic Java programming concepts or are new to the language and want to learn how it treats data structures concepts.

PART I: TOUR OF JAVA

Primitive Java

(24)

The General Environment

(1)

The First Program

(1)

Comments

(1)

main

(1)

Terminal Output

(1)

Primitive Types

(2)

The Primitive Types

(1)

Constants

(1)

Declaration and Initialization of Primitive Types

(1)

Terminal Input and Output

(1)

Basic Operators

(3)

Assignment Operators

(1)

Binary Arithmetic Operators

(1)

Unary Operators

(1)

Type Conversions

(1)

Conditional Statements

(7)

Relational and Equality Operators

(1)

Logical Operators

(1)

The if Statement

(1)

The while Statement

(1)

The for Statement

(1)

The do Statement

(1)

break and continue

(1)

The switch Statement

(1)

The Conditional Operator

(1)

Methods

(9)

Overloading of Method Names

(1)

Storage Classes

(1)

Summary

(1)

Objects of the Game

(2)

Common Errors

(1)

On the Internet

(1)

Exercises

(2)

References

(2)

Reference Types

(34)

What Is a Reference?

(3)

Basics of Objects and References

(5)

The Dot Operator (.)

(1)

Declaration of Objects

(1)

Garbage Collection

(1)

The Meaning of =

(1)

Parameter Passing

(1)

The Meaning of ==

(1)

No Operator Overloading for Objects

(1)

Strings

(2)

Basics of String Manipulation

(1)

String Concatenation

(1)

Comparing Strings

(1)

Other String Methods

(1)

Converting Other Types of Strings

(1)

Arrays

(10)

Declaration, Assignment, and Methods

(2)

Dynamic Array Expansion

(3)

ArrayList

(2)

Multidimensional Arrays

(1)

Command-line Arguments

(2)

Exception Handling

(3)

Processing Exceptions

(1)

The finally Clause

(2)

Common Exceptions

(1)

The throw and throws Clauses

(1)

Input and Output

(11)

Basic Stream Operations

(1)

The StringTokenizer Type

(1)

Sequential Files

(2)

Summary

(2)

Objects of the Game

(1)

Common Errors

(1)

On the Internet

(1)

Exercises

(1)

References

(1)

Objects and Classes

(28)

What Is Object-Oriented Programming?

(2)

A Simple Example

(2)

Javadoc

(3)

Basic Methods

(3)

Constructors

(1)

Mutators and Accessors

(2)

Output and toString

(1)

equals

(1)

main

(1)

Static Fields and Methods

(1)

Additional Constructs

(5)

The this Reference

(1)

The this Shorthand for Constructors

(1)

The instanceof Operator

(1)

Instance Members vs. Static Members

(1)

Static Fields and Methods

(1)

Static Initializers

(2)

Packages

(4)

The import Directive

(2)

The package Statement

(1)

The CLASSPATH Environment Variable

(1)

Package Visibility Rules

(1)

A Design Pattern: Composite (Pair)

(9)

Summary

(2)

Objects of the Game

(1)

Common Errors

(1)

On the Internet

(1)

Exercises

(3)

References

(1)

Inheritance

(58)

What Is Inheritance?

(13)

Creating New Classes

(5)

Type Compatibility

(1)

Dynamic Binding and Polymorphism

(1)

Inheritance Hierarchies

(1)

Visibility Rules

(1)

The Constructor and super

(1)

final Methods and Classes

(1)

Overriding a Method

100

(1)

Type Compatibility Revisited

101

(2)

Designing Hierarchies

103

(6)

Abstract Methods and Classes

107

(2)

Multiple Inheritance

109

(1)

The Interface

110

(3)

Specifying an Interface

110

(1)

Implementing an Interface

111

(1)

Multiple Interfaces

112

(1)

Interfaces are Abstract Classes

112

(1)

Fundamental Inheritance in Java

113

(5)

The Object Class

113

(1)

The Hierarchy of Exceptions

113

(1)

I/O: The Decorator Pattern

113

(5)

Implementing Generic Components

118

(7)

Using Object for Genericity

119

(1)

Wrappers for Primitive Types

120

(1)

Adapters: Changing an Interface

120

(3)

Using Interface Types for Genericity

123

(2)

The Functor (Function Objects)

125

(6)

Nested Classes

128

(1)

Local Classes

129

(1)

Anonymous Classes

130

(1)

Dynamic Binding Details

131

(16)

Summary

135

(1)

Objects of the Game

136

(2)

Common Errors

138

(1)

On the Internet

138

(2)

Exercises

140

(4)

References

144

(3)

PART II: ALGORITHMS AND BUILDING BLOCKS

Algorithm Analysis

147

(36)

What Is Algorithm Analysis?

148

(3)

Examples of Algorithm Running Times

151

(2)

The Maximum Contiguous Subsequence Sum Problem

153

(7)

The Obvious O(N3) Algorithm

154

(3)

An Improved O(N2) Algorithm

157

(1)

A Linear Algorithm

158

(2)

General Big-Oh Rules

160

(4)

The Logarithm

164

(3)

Static Searching Problem

167

(4)

Sequential Search

167

(1)

Binary Search

168

(2)

Interpolation Search

170

(1)

Checking an Algorithm Analysis

171

(2)

Limitations of Big-Oh Analysis

173

(10)

Summary

174

(1)

Objects of the Game

174

(1)

Common Errors

175

(1)

On the Internet

175

(1)

Exercises

176

(5)

References

181

(2)

The Collections API

183

(48)

Introduction

184

(1)

The Iterator Pattern

185

(5)

Basic Iterator Design

186

(2)

Inheritance-based Iterators and Factories

188

(2)

Collections API: Containers and Iterators

190

(5)

The Collection Interface

190

(3)

Iterator Interface

193

(2)

Generic Algorithms

195

(4)

Comparator Function Objects

195

(1)

The Collections Class

195

(3)

Binary Search

198

(1)

Sorting

199

(1)

The List Interface

199

(6)

The ListIterator Interface

201

(1)

LinkedList Class

202

(3)

Stacks and Queues

205

(4)

Stacks

205

(1)

Stacks and Computer Languages

206

(2)

Queues

208

(1)

Stacks and Queues in the Collections API

208

(1)

Sets

209

(7)

The TreeSet Class

210

(1)

The HashSet Class

211

(5)

Maps

216

(4)

Priority Queues

220

(11)

Summary

224

(1)

Objects of the Game

225

(1)

Common Errors

226

(1)

On the Internet

226

(1)

Exercises

227

(3)

References

230

(1)

Recursion

231

(52)

What Is Recursion?

232

(1)

Background: Proofs by Mathematical Induction

233

(2)

Basic Recursion

235

(13)

Printing Numbers in Any Base

237

(2)

Why It Works

239

(2)

How It Works

241

(1)

Too Much Recursion Can Be Dangerous

242

(1)

Preview of Trees

243

(1)

Additional Examples

244

(4)

Numerical Applications

248

(9)

Modular Arithmetic

250

(1)

Modular Exponentiation

250

(2)

Greatest Common Divisor and Multiplicative Inverses

252

(2)

The RSA Cryptosystem

254

(3)

Divide-and-Conquer Algorithms

257

(10)

The Maximum Contiguous Subsequence Sum Problem

258

(2)

Analysis of a Basic Divide-and-Conquer Recurrence

260

(5)

A General Upper Bound for Divide-and-Conquer Running Times

265

(2)

Dynamic Programming

267

(5)

Backtracking

272

(11)

Summary

276

(1)

Objects of the Game

276

(1)

Common Errors

277

(1)

On the Internet

278

(1)

Exercises

278

(4)

References

282

(1)

Sorting Algorithms

283

(40)

Why Is Sorting Important?

284

(1)

Preliminaries

285

(1)

Analysis of the Insertion Sort and Other Simple Sorts

285

(4)

Shellsort

289

(4)

Performance of Shellsort

290

(3)

Mergesort

293

(2)

Linear-Time Merging of Sorted Arrays

293

(2)

The Mergesort Algorithm

295

(1)

Quicksort

295

(16)

The Quicksort Algorithm

296

(3)

Analysis of Quicksort

299

(4)

Picking the Pivot

303

(1)

A Partitioning Strategy

304

(3)

Keys Equal to the Pivot

307

(1)

Median-of-Three Partitioning

307

(1)

Small Arrays

308

(1)

Java Quicksort Routine

309

(2)

Quickselect

311

(1)

A Lower Bound for Sorting

312

(11)

Summary

314

(1)

Objects of the Game

315

(1)

Common Errors

315

(1)

On the Internet

316

(1)

Exercises

316

(4)

References

320

(3)

Randomization

323

(24)

Why Do We Need Random Numbers?

323

(1)

Random Number Generators

324

(6)

Nonuniform Random Numbers

330

(3)

Generating a Random Permutation

333

(1)

Randomized Algorithms

334

(3)

Randomized Primality Testing

337

(10)

Summary

340

(1)

Objects of the Game

340

(1)

Common Errors

341

(1)

On the Internet

342

(1)

Exercises

342

(2)

References

344

(3)

PART III: APPLICATIONS

Fun and Games

347

(22)

Word Search Puzzles

347

(3)

Theory

348

(2)

Java Implementation

350

(1)

The Game of Tic-Tac-Toe

350

(19)

Alpha-Beta Pruning

353

(6)

Transposition Tables

359

(3)

Computer Chess

362

(2)

Summary

364

(1)

Objects of the Game

364

(1)

Common Errors

364

(1)

On the Internet

365

(1)

Exercises

365

(2)

References

367

(2)

Stacks and Compilers

369

(30)

Balanced-Symbol Checker

369

(11)

Basic Algorithm

370

(1)

Implementation

371

(9)

A Simple Calculator

380

(19)

Postfix Machines

382

(1)

Infix to Postfix Conversion

383

(3)

Implementation

386

(5)

Expression Trees

391

(4)

Summary

395

(1)

Objects of the Game

396

(1)

Common Errors

396

(1)

On the Internet

397

(1)

Exercises

397

(1)

References

398

(1)

Utilities

399

(30)

File Compression

399

(21)

Prefix Codes

401

(2)

Huffman's Algorithm

403

(2)

Implementation

405

(15)

A Cross-Reference Generator

420

(9)

Basic Ideas

420

(1)

Java Implementation

420

(4)

Summary

424

(1)

Objects of the Game

425

(1)

Common Errors

425

(1)

On the Internet

425

(1)

Exercises

425

(3)

References

428

(1)

Simulation

429

(18)

The Josephus Problem

429

(6)

The Simple Solution

431

(1)

A More Efficient Algorithm

431

(4)

Event-Driven Simulation

435

(12)

Basic Ideas

435

(1)

Example: A Modem Bank Simulation

436

(8)

Summary

444

(1)

Objects of the Game

444

(1)

Common Errors

444

(1)

On the Internet

444

(1)

Exercises

445

(2)

Graphs and Paths

447

(46)

Definitions

448

(11)

Representation

449

(10)

Unweighted Shortest-Path Problem

459

(8)

Theory

462

(4)

Java Implementation

466

(1)

Positive-Weighted, Shortest-Path Problem

467

(4)

Theory: Dijkstra's Algorithm

467

(2)

Java Implementation

469

(2)

Negative-Weighted, Shortest-Path Problem

471

(3)

Theory

473

(1)

Java Implementation

474

(1)

Path Problems in Acyclic Graphs

474

(19)

Topological Sorting

474

(2)

Theory of the Acyclic Shortest-Path Algorithm

476

(2)

Java Implementation

478

(2)

An Application: Critical-Path Analysis

480

(3)

Summary

483

(1)

Objects of the Game

483

(2)

Common Errors

485

(1)

On the Internet

485

(1)

Exercises

485

(4)

References

489

(4)

PART IV: IMPLEMENTATIONS

Inner Classes and Implementation of ArrayList

493

(20)

Iterators and Nested Classes

493

(2)

Iterators and Inner Classes

495

(5)

The AbstractCollection Class

500

(1)

Implementation of ArrayList with an Iterator

500

(13)

Summary

508

(1)

Objects of the Game

508

(1)

Common Error

508

(1)

On the Internet

509

(1)

Exercises

509

(4)

Stacks and Queues

513

(24)

Dynamic Array Implementations

513

(11)

Stacks

514

(4)

Queues

518

(6)

Linked List Implementations

524

(6)

Stacks

524

(1)

Queues

525

(5)

Comparison of the Two Methods

530

(1)

The java.util.Stack Class

531

(2)

Double-Ended Queues

533

(4)

Summary

534

(1)

Objects of the Game

534

(1)

Common Errors

534

(1)

On the Internet

534

(1)

Exercises

535

(2)

Linked Lists

537

(32)

Basic Ideas

537

(5)

Header Nodes

539

(2)

Iterator Classes

541

(1)

Java Implementation

542

(6)

Doubly Linked Lists and Circularly Linked Lists

548

(3)

Sorted Linked Lists

551

(1)

Implementing the Collections API LinkedList Class

551

(18)

Summary

563

(1)

Objects of the Game

563

(1)

Common Errors

563

(1)

On the Internet

563

(1)

Exercises

564

(5)

Trees

569

(34)

General Trees

569

(7)

Definitions

570

(1)

Implementation

571

(1)

An Application: File Systems

572

(4)

Binary Trees

576

(6)

Recursion and Trees

582

(3)

Tree Traversal: Iterator Classes

585

(18)

Postorder Traversal

589

(3)

Inorder Traversal

592

(1)

Preorder Traversal

592

(4)

Level-Order Traversals

596

(1)

Summary

597

(1)

Objects of the Game

598

(1)

Common Errors

599

(1)

On the Internet

599

(1)

Exercises

600

(3)

Binary Search Trees

603

(80)

Basic Ideas

603

(10)

The Operations

604

(2)

Java Implementation

606

(7)

Order Statistics

613

(5)

Java Implementation

614

(4)

Analysis of Binary Search Tree Operations

618

(3)

AVL Trees

621

(9)

Properties

622

(2)

Single Rotation

624

(3)

Double Rotation

627

(3)

Summary of AVL Insertion

630

(1)

Red-Black Trees

630

(14)

Bottom-Up Insertion

631

(3)

Top-Down Red-Black Trees

634

(2)

Java Implementation

636

(5)

Top-Down Deletion

641

(3)

AA-Trees

644

(10)

Insertion

646

(2)

Deletion

648

(1)

Java Implementation

649

(5)

Implementing the Collections API TreeSet and TreeMap Classes

654

(9)

B-Trees

663

(20)

Summary

675

(1)

Objects of the Game

676

(1)

Common Errors

677

(1)

On the Internet

677

(1)

Exercises

678

(2)

References

680

(3)

Hash Tables

683

(32)

Basic Ideas

684

(1)

Hash Function

685

(2)

Linear Probing

687

(6)

Naive Analysis of Linear Probing

689

(1)

What Really Happens: Primary Clustering

690

(1)

Analysis of the find Operation

691

(2)

Quadratic Probing

693

(13)

Java Implementation

697

(6)

Analysis of Quadratic Probing

703

(3)

Separate Chaining Hashing

706

(1)

Hash Tables Versus Binary Search Trees

707

(1)

Hashing Applications

707

(8)

Summary

708

(1)

Objects of the Game

708

(1)

Common Errors

709

(1)

On the Internet

710

(1)

Exercises

710

(2)

References

712

(3)

A Priority Queue: The Binary Heap

715

(36)

Basic Ideas

716

(5)

Structure Property

716

(2)

Heap-Order Property

718

(1)

Allowed Operations

718

(3)

Implementation of the Basic Operations

721

(5)

The insert Operation

722

(1)

The deleteMin Operation

723

(3)

The buildHeap Operation: Linear-Time Heap Construction

726

(5)

Advanced Operations: decreaseKey and merge

731

(1)

Internal Sorting: Heapsort

731

(3)

External Sorting

734

(17)

Why We Need New Algorithms

734

(1)

Model for External Sorting

735

(1)

The Simple Algorithm

735

(2)

Multiway Merge

737

(1)

Polyphase Merge

738

(2)

Replacement Selection

740

(1)

Summary

741

(1)

Objects of the Game

741

(1)

Common Errors

742

(1)

On the Internet

742

(1)

Exercises

743

(4)

References

747

(4)

PART V: ADVANCED DATA STRUCTURES

Splay Trees

751

(28)

Self-Adjustment and Amortized Analysis

752

(3)

Amortized Time Bounds

753

(1)

A Simple Self-Adjusting Strategy (That Does Not Work)

753

(2)

The Basic Bottom-Up Splay Tree

755

(3)

Basic Splay Tree Operations

758

(1)

Analysis of Bottom-Up Splaying

759

(6)

Proof of the Splaying Bound

762

(3)

Top-Down Splay Trees

765

(3)

Implementation of Top-Down Splay Trees

768

(3)

Comparison of the Splay Tree with Other Search Trees

771

(8)

Summary

773

(1)

Objects of the Game

773

(3)

Common Errors

776

(1)

On the Internet

776

(1)

Exercises

776

(1)

References

777

(2)

Merging Priority Queues

779

(22)

The Skew Heap

779

(5)

Merging Is Fundamental

780

(1)

Simplistic Merging of Heap-Ordered Trees

780

(1)

The Skew Heap: A Simple Modification

781

(1)

Analysis of the Skew Heap

782

(2)

The Pairing Heap

784

(17)

Pairing Heap Operations

785

(1)

Implementation of the Pairing Heap

786

(5)

Application: Dijkstra's Shortest Weighted Path Algorithm

791

(5)

Summary

796

(1)

Objects of the Game

796

(1)

Common Errors

796

(1)

On the Internet

797

(1)

Exercises

797

(1)

References

798

(3)

The Disjoint Set Class

801

(70)

Equivalence Relations

802

(1)

Dynamic Equivalence and Applications

802

(11)

Application: Generating Mazes

803

(3)

Application: Minimum Spanning Trees

806

(3)

Application: The Nearest Common Ancestor Problem

809

(4)

The Quick-Find Algorithm

813

(1)

The Quick-Union Algorithm

814

(4)

Smart Union Algorithms

815

(2)

Path Compression

817

(1)

Java Implementation

818

(3)

Worst Case for Union-by-Rank and Path Compression

821

(14)

Analysis of the Union/Find Algorithm

822

(6)

Summary

828

(1)

Objects of the Game

829

(1)

Common Errors

830

(1)

On the Internet

830

(1)

Exercises

830

(3)

References

833

(2)

APPENDICES

Appendix A Operators

835

(2)

Appendix B Graphical User Interfaces

837

(30)

B.1 The Abstract Window Toolkit and Swing

838

(1)

B.2 Basic Objects in Swing

839

(1)

B.2.1 Component

839

(2)

B.2.2 Container

841

(1)

B.2.3 Top-level Containers

841

(1)

B.2.4 JPanel

842

(1)

B.2.5 Important I/O Components

843

(5)

B.3 Basic Principles

848

(1)

B.3.1 Layout Managers

848

(4)

B.3.2 Graphics

852

(1)

B.3.3 Events

853

(3)

B.3.4 Event Handling: Adapters and Anonymous Inner Classes

856

(3)

B.3.5 Summary: Putting the Pieces Together

859

(1)

B.3.6 Is This Everything I Need To Know About Swing?

860

(1)

Summary

860

(1)

Objects of the Game

861

(2)

Common Errors

863

(1)

On the Internet

863

(1)

Exercises

863

(2)

Reference

865

(2)

Appendix C Bitwise Operators

867

(4)

Index

871

Amazon no longer offers textbook rentals. We do!

Data Structures and Problem Solving Using Java

Data Structures and Problem Solving Using Java

9780201748352

0201748355

Summary

Table of Contents

Supplemental Materials

Write a Review

Amazon no longer offers textbook rentals. We do!

Data Structures and Problem Solving Using Java

Data Structures and Problem Solving Using Java

9780201748352

0201748355

Summary

Table of Contents

Supplemental Materials

Write a Review

Related Products